tween the measurements and the sepa-
ration of the measurers proved enor-
mously difficult.”
Ito and Vidick’s proof relies on dis-
guising the questioner’s intent by ask-
ing multiple questions, thus reducing
the likelihood of cheating. That strat-
egy stems from an earlier proof of the
classical version of their result by Ba-
bai, Fortnow, and Lund in 1991. Their
proof demonstrates that quantum en-
tanglement would not allow multiple
provers to trick the verifier with an in-
correct answer.

Vidick feels the breakthrough insight was, as he puts it, to “stop trying to show that the provers will not be able to use their entanglement to cheat.” Instead, they focused their efforts on assessing the entangled provers as a whole. This process involved coming up with a complex set of tools that allowed them to analyze and perform reductions directly with entangled provers, rather than trying to extrapolate results by relating entangled provers to classical provers.

That result has proved an impor-
tant conceptual breakthrough in the
world of quantum interactive proofs.
“A major consequence of our work
is that it provides a technique to im-
munize proof systems against the use
of entanglement,” says Vidick. “This
is surprising because we know that
sometimes entanglement allows for a
large amount of cheating. So it wasn’t
expected that any classical protocol
could be generically resistant against
entanglement-based cheating.”
Looking ahead, Vidick sees plenty
of implications for his work in other re-
search areas. He is particularly excited
about the intersection of multi-prover
interactive proofs with the world of
mathematics, especially functional
analysis. He points to Grothendieck’s
inequality as one example of where
he thinks his work could lead to deep
extensions, as well as new approxima-
tion algorithms for classical problems
in learning theory, such as principal
component analysis.

While this proof opens up a number of promising new research avenues, the implications for practical computer science applications remain less clear.

“Even if we had quantum computers, it’s unlikely that anyone would be able to build one of these systems,”

ito and vidick’s proof
relies on disguising
the questioner’s
intent by asking
multiple questions,
thus reducing the
likelihood of cheating.

says Lance Fortnow, professor and chair of the School of Computer Science at Georgia Tech and author of The Golden Ticket, a newly available book on the well-known P vs. NP problem. The computational problems involved would simply be too daunting.

Fortnow believes, however, that the finding may have indirect applications for the larger world of quantum computing. “This result may give us new insights into the limits of quantum entanglement for the purpose of communication between two parties,” he says. “It (quantum entanglement) may be even less useful than we expected.” Those implications aside, both quantum and classical interactive proof systems serve primarily as theoretical models for studying complexity theory, particularly around questions of computational efficiency and theoretical cryptography.

“One of the main reasons we study
them is because, as theorists, we are
drawn to models and notions that we
consider to have fundamental impor-
tance from a mathematical viewpoint,”
says Watrous. “The applications would
be indirect.”
Vidick agrees that multi-prover
interactive proofs hold interest pri-
marily for theoretical researchers like
himself, although he does see a bright
future for more limited applications of
quantum cryptography, such as quan-
tum key distribution. “Quantum cryp-
to is really much more powerful than
classical crypto, and moreover typical-
ly requires only very simple quantum
mechanical equipment—much easier
to get than a universal quantum com-
puter,” says Vidick.

The current generation of quan-
tum protocols relies on single-prover
interactive proofs, however—without
the messy problem of entanglement.
“Entanglement is hard to generate and
even more to keep coherently,” says
Vidick. While there are a few quantum
key distribution protocols that rely
on entanglement (for example, Ekert
1991), these protocols work by measur-
ing two separated but entangled parti-
cles nearly instantaneously—currently
a technical impossibility. “I would bet
it will be done within 10 years,” he says,
“but this doesn’t mean the use of en-
tanglement will be practical.”
From Watrous’ perspective, the im-
plications may be largely theoretical, but
nonetheless potentially far-reaching.
“We are still close to the beginning in
terms of understanding this model.”

 

Further Reading

László Babai, Lance Fortnow, Carsten Lund. non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity, 1, 1 (1991), 3–40.

A.K. Ekert

Quantum Cryptography Based on Bell’s Theorem, Physical Review Letters, vol. 67, no. 6, 5 August 1991, pp. 661–663.

Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for nEXP sound against entangled provers, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, September 2012. arXiv:1207.0550v2

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. 2010. QIP = PSPACE. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC ‘ 10). ACM, new York, n Y, USA, 573– 582. DOI= 10.1145/1806689.1806768 http:// doi.acm.org/10.1145/1806689.1806768

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick 2011. Entangled Games Are hard to Approximate. SIAM J. Comput. 40, 3 (June 2011), 848-877. DOI= 10.1137/090751293 http://dx.doi.org/10.1137/090751293

Assaf Naor, Oded Regev, Thomas Vidick 2012. Efficient Rounding for the noncommutative Grothendieck Inequality, to appear in Proceedings of the 45nd ACM Symposium on Theory of Computing (STOC ‘ 13). arXiv:1210.7656v1

Alex Wright is a writer and information architect based in brooklyn, ny.