Science | DOI: 10.1145/2447976.2447982
Researchers are making headway with one of quantum computing’s
major theoretical problems: multi-prover interactive proofs.
As a young computer sci- ence master’s student at he University of Paris, Or- say, Thomas Vidick began his first research project
on the problem that has consumed him
ever since: quantum entanglement.
Seven years and one Ph.D. later, Vidick—now a post-doctoral researcher at
the Massachusetts Institute of Technology (MIT)—has finally published
the culmination of that work. “It took
us a while,” he says.
In October 2012, Vidick and co-au-thor Tsuyoshi Ito, a researcher at NEC
Labs in Princeton, N.J., revealed their
long-sought-after result: demonstrating that an important theoretical security protocol, known as a multi-prover
interactive proof, could work in a quantum computing environment.
PhotograPh by PefostuDIo5 / shutterstock.com
The proof marks the closure of a
major unsolved question in computer
science—one with important implications for the study of computational
complexity and for quantum computing in general.
“It’s an outstanding result,” says Professor John Watrous of the University
of Waterloo, echoing the view of many
theoreticians working in the quantum
computing field. For the rest of us nonspecialists, however, appreciating why
this research matters requires a basic
understanding of two conceptually
multi-prover interactive proof systems limit the ability of independent provers to cheat.
challenging topics: interactive proof
systems, and quantum mechanics.
For the past two decades, interactive
proof systems have emerged as a well-
established technique in modern cryp-
tography and computer security, by
providing a mechanism that allows one
machine to confirm another’s identity. In
the classic interactive proof, a “verifier”
with limited computational abilities que-
ries a “prover” that is assumed to have un-
limited computing power, but uncertain
motives. The verifier issues a challenge
to assess the prover’s trustworthiness by
posing a series of questions, such as ask-
ing whether a particular formula can be
satisfied. The verifier may then repeat
the protocol as many times as necessary
to accept or reject the proof.