Multiprover Interactive Proof System Gains Power by Exploiting Quantum Entanglement

A big question for researchers in quantum computing is, where does quantum physics give us an advantage? CQT researcher Joe Fitzsimons and his collaborator Thomas Vidick from Caltech have added to the list. Specifically, they give an example of a “multiprover interactive proof system" that gains power by exploiting quantum entanglement.

"Until recently people didn't know if the entanglement would help or hurt in such systems," says Joe, who presented the work at the 6th Innovations in Theoretical Computer Science (ITCS) conference in Israel in January. "The finding that entanglement can help is kind of unexpected," he says.

Thomas presented the work at the 18th conference on Quantum Information Processing (QIP) in Sydney, Australia, also in January, delivering a plenary talk on the paper.

Quantum benefits

There are famous examples of quantum algorithms that solve certain problems faster than classical programs, notably Shor's algorithm for factoring large numbers and Grover's algorithm for search an unsorted list. But it's not always a given that harnessing quantum phenomena will make life easier.

Thomas and Joe considered what happens when you mix quantum entanglement into something known as an interactive proof.

The concept of interactive proofs comes from classical computer science. The idea is that you have someone smarter than you (or a powerful computer) that you can ask questions to try to decide whether a statement, a proof, is true. Computer scientists have long known that you can check a wider range of statements with access to this kind of help than you can without, and that if you add more helpers – multiple provers – you can verify even more still.

What's newer is thinking about how quantum information changes the picture. If you can ask your questions using quantum bits, can you verify proofs of more difficult statements? What if you are dealing with provers that share quantum entanglement?

Some of the answers have been hashed out over the past few years. For example, in 2009 CQT's Rahul Jain and his collaborators showed that being able to use quantum communication doesn't expand the set of problems having efficient interactive proofs (neatly summed up, in the language of complexity classes, as QIP=IP). More recently, reseachers proved a similar equivalence for proofs in systems with many entangled provers.

But researchers have yet to clarify how going from many provers to many entangled provers changes what it's possible to check. Joe and Thomas delved into this problem.

Sound and complete

A key assumption of interactive proofs is that you don't take the honesty of the prover for granted. Proofs are typically qualified in terms of being 'sound' and 'complete'. Sound means that even a malicious prover can't trick the verifier into believing a statement is correct when it isn't. Complete means there's a good chance the verifier will be convinced that their statement is correct when it is.

In the classical case, it's assumed the provers can't communicate with each other. With access to multiple provers, the verifier gets the advantage of being able to cross-check their answers against each other, making it possible to achieve sound and complete proofs for a wider range of problems.

But what if the provers share entanglement? “Previously the focus had been on whether the presence of entanglement meant they could cheat and hence less could be proved unambiguously," says Joe. “Our paper shows for the first time that entanglement shared between non-communicating parties allows them to prove to a verifier more than they could prove without entanglement."

They showed this for something known as the local Hamiltonian problem, which checks the ground-state energy of a system of quantum particles. In their example the advantage is earned by applying an error-correcting code to five entangled provers, which is similar to cross-checking in the classical case

Researchers in this field like best to be able to make statements about whole classes of problems, but an example makes a good start. “The computer science community seem to be taking the result quite seriously," says Joe.

Joe is a Research Assistant Professor at CQT and faculty member at the Singapore University of Technology and Design. Thomas is Assistant Professor of Computing and Mathematical Sciences at Caltech's Institute for Quantum Information and Matter. He also holds a visiting appointment with CQT's computer science group.