Nnews
Science | DOI: 10.1145/2447976.2447982
Proving Grounds
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.