Communications of the ACM
Technical Perspective: On Proofs, Entanglement, and Games
What is a proof? Philosophers and mathematicians have pondered this question for centuries. Theoretical computer science offers a rigorous handle on this deep question. One can think of a proof as a two-player game: an all-powerful though un-trusted prover who provides a proof of the statement, and a computationally weak verifier who needs only to verify it. In fact, NP problems can be presented exactly in this verifier-prover language. Viewing proofs as games turned out to be remarkably fruitful. For example, interactive proofs were invented, resembling Socratic dialogues; these are games in which the prover and verifier exchange (possibly randomized) messages. And, why just one prover? In multi-prover interactive proofs (MIP) several non-communicating provers are involved. This gave birth to beautiful concepts such as zero knowledge and probabilistically checkable proofs (PCPs) with immense impact not only theoretically but also in practice, for example, in digital currency.
The following paper studies quantum interactive proofs. Here the provers are allowed to share an entangled quantum state; this resembles sharing a random bit string, except quantum states have those funny, stronger-than-classical correlations; a prototypical example is the Einstein-Podolsky-Rosen (EPR) state, which was said by Einstein to allow "spooky action at a distance." Can quantum correlations be used to prove stronger statements?
No entries found