# 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.”

Read MoreMath – Science News