Sign In

Communications of the ACM

Research highlights

Technical Perspective: On Proofs, Entanglement, and Games

question mark inside qubit icon, illustration

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

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.