A quantum strategy could verify the solutions to unsolvable problems — in theory

Computer scientists’ daydreams have revealed the power of quantum mechanics.

Imagine meeting omniscient beings who claim to have the solution to a complex problem that no computer could ever solve. You’d probably be at a loss to check the answer. But now, computer scientists report that quantum mechanics provides a way to quickly verify the solutions to an incredibly broad class of problems, including some that are impossible to solve in the first place.

Although the result doesn’t have obvious practical applications, its theoretical ramifications have had a ripple effect, answering unsolved questions in physics and mathematics, scientists report in a paper posted January 13 at arXiv.org. “It has so many implications for all these areas. It’s a huge deal no matter how you look at it,” says theoretical computer scientist Scott Aaronson of the University of Texas at Austin, who was not involved with the new study.

In computer science, some problems are difficult to solve but have solutions that are easy to check. So researchers classify questions according to how hard it is for computers to verify purported answers.

On its own, a computer can go only so far in verifying solutions. But scientists have a few tricks up their sleeves. They concoct scenarios where a “prover” — a computer or person who claims to have a solution to a problem — is peppered with questions by the person who is attempting to check the solution, the “verifier.”

Imagine, for example, that you have a friend who claims to have deduced how to tell the difference between Pepsi and Coke, even though you can’t distinguish between the two. To confirm this claim, you — the verifier — might prepare a cup of either Pepsi or Coke and query your friend — the prover — on which one it is. If your friend consistently gives the right answer to such questions, you’d be convinced that the cola-identification quandary had been solved.

Known as an interactive proof, this strategy can reveal additional information that would allow computer scientists to verify solutions to problems that are too difficult for a computer to convince the scientists of independently. Still more powerful interactive proofs involve multiple provers. That scenario is a bit like a police interrogation of two suspects, isolated in separate rooms, who can’t coordinate their answers to trick an investigator.

The class of problems that can be verified in this way is “big, but not ridiculously big,” says study coauthor Thomas Vidick, a theoretical computer scientist at Caltech. To check the solutions to an even larger variety of problems, scientists can imagine adding another twist: The provers share a quantum connection called entanglement, which causes two seemingly independent objects to behave in correlated ways (SN: 4/25/18).

Until now, it was not known how many problems were verifiable with quantum entanglement. The new result reveals that it’s “an unbelievably huge number of problems,” says Aaronson.

That huge group is called recursively enumerable, or RE, problems. “It contains all problems that are solvable by computers and then some,” says coauthor Henry Yuen, a computer scientist at the University of Toronto. “That’s a crazy thing.” It’s the “and then some” that is really mind-boggling. No computer would be able to solve those problems outright, but if two entangled omniscient beings had a solution, they could convince you it was correct. Of course, enacting the verification technique in the real world is made implausible by the lack of omniscient beings to offer up the answers.

The result is summed up in the succinct equality, MIP* = RE, where MIP* stands for Multi-prover Interactive Proof with quantum entanglement. Every problem in RE is also in MIP*, and vice versa.

Although not yet peer-reviewed, the study is being taken very seriously, says computer scientist Lance Fortnow of the Illinois Institute of Technology in Chicago. “I would bet that it’s probably correct…. There’s no reason to think it’s wrong.”

And the result is a triple threat: It solved three problems at once. In addition to revealing that MIP* equals RE, it simultaneously answered two other open questions, one in physics and one in math. The first is a quantum physics puzzle called Tsirelson’s problem, which asks whether the types of quantum correlations that could be produced using an infinite amount of entanglement could be approximated with a very large, but finite amount of entanglement. The answer, the study reveals, is no: Sometimes you can’t even come close to replicating infinite entanglement with finite entanglement.

In mathematics, the study settles Connes’ embedding conjecture, a long-standing idea that is mathematically equivalent to Tsirelson’s problem. It likewise deals with the question of whether a finite approximation can necessarily replicate something truly infinite. Again, the answer is no.

“It’s an incredible achievement; it’s just really exciting,” says mathematician William Slofstra of the University of Waterloo in Canada. “It’s a fulfillment of something we’ve wanted for a long time.”