Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
October 29 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
Quantum Entanglement and Notions of Mathematical Proof
- Speaker:
Richard E. Cleve (University of Waterloo)
- Abstract:
Quantum computers are information processing devices that can
manipulate quantum states. They can apparently perform interesting
computing feats exponentially faster than any existing classical
computer. For example, they can factorize integers in polynomial time,
whereas no such classical algorithm is known and the security of many
cryptosystems is based on the presumed hardness of this problem.
In this talk, we will focus on another remarkable property of quantum
states: that two physically-separated quantum systems can exist in an
"entangled" state, where in some sense neither system separately has a
definite state. We will show that the existence of entangled states
raises questions about the soundness of some mathematical proof systems.
Namely, previous results about the soundness and completeness of
multi-prover interactive proof systems are incorrect when the
possibility of entanglement is taken into account.
We will also comment about the expressive power of multi-prover
interactive proof systems, which is understood in the classical case
(where there is no entanglement), but an open question in the quantum
setting.
No prior knowledge of quantum information will be assumed for this talk.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar