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