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.