âThe verifier can send the prover questions,â Wright said, âand maybe at the end of the conversation the verifier can become more convinced.â

In 1985 a trio of computer scientists proved that such interactive proofs can be used to verify solutions to problems that are more complicated than the problems in NP. Their work created a new class of problems called IP, for âinteractive polynomialâ time. The same method used to verify the coloring of two blocks can be used to verify solutions to much more complicated questions.

The second major advance took place in the same decade. It follows the logic of a police investigation. If you have two suspects you believe committed a crime, youâre not going to question them together. Instead, youâll interrogate them in separate rooms and check each personâs answers against the otherâs. By questioning them separately, youâll be able to reveal more of the truth than if you had only one suspect to interrogate.

âItâs impossible for (two suspects) to form some sort of distributed, consistent story because they simply donât know what answers the other is giving,â Wright said.

In 1988 four computer scientists proved that if you ask two computers to separately solve the same problem â and you interrogate them separately about their answers â you can verify a class of problems thatâs even larger than IP: a class called MIP, for multi-prover interactive proofs.

With a multi-prover interactive approach, for example, itâs possible to verify three-colorings for a sequence of graphs that increase in size much faster than the graphs in NP. In NP, graph sizes increase at a linear rate â the number of vertices might grow from 1 to 2 to 3 to 4 and so on â so that the size of a graph is never hugely disproportionate to the amount of time needed to verify its three-coloring. But in MIP, the number of vertices in a graph grows exponentially â from 2^{1} to 2^{2} to 2^{3} to 2^{4} and so on.

As a result, the graphs are too big even to fit in the verifying computerâs memory, so it canât check three-colorings by running through the list of vertices. But itâs still possible to verify a three-coloring by asking the two provers separate but related questions.

In MIP, the verifier has enough memory to run a program that allows it to determine whether two vertices in the graph are connected by an edge. The verifier can then ask each prover to state the color of one of the two connected vertices â and it can cross-reference the proversâ answers to make sure the three-coloring works.

The expansion of hard-to-solve-but-easy-to-verify problems from NP to IP to MIP involved classical computers. Quantum computers work very differently. For decades itâs been unclear how they change the picture â do they make it harder or easier to verify solutions?

The new work by Natarajan and Wright provides the answer.

## Quantum Cheats

Quantum computers perform calculations by manipulating quantum bits, or âqubits.â These have the strange property that they can be entangled with one another. When two qubits â or even large systems of qubits â are entangled, it means that their physical properties play off each other in a certain way.

In their new work, Natarajan and Wright consider a scenario involving two separate quantum computers that share entangled qubits.

This kind of setup would seem to work against verification. The power of a multi-prover interactive proof comes precisely from the fact that you can question two provers separately and cross-check their answers. If the proversâ answers are consistent, then itâs likely theyâre correct. But two provers sharing an entangled state would seem to have more power to consistently assert incorrect answers.

And indeed, when the scenario of two entangled quantum computers was first put forward in 2003, computer scientists assumed entanglement would reduce verification power. âThe obvious reaction of everyone, including me, is that now youâre giving more power to the provers,â Vidick said. âThey can use entanglement to correlate their answers.â

Despite that initial pessimism, Vidick spent several years trying to prove the opposite. In 2012, he and Tsuyoshi Ito proved that itâs still possible to verify all the problems in MIP with entangled quantum computers.

Natarajan and Wright have now proved that the situation is even better than that: A wider class of problems can be verified with entanglement than without it. Itâs possible to turn the connections between entangled quantum computers to the verifierâs advantage.

To see how, remember the procedure in MIP for verifying three-colorings of graphs whose sizes grow exponentially. The verifier doesnât have enough memory to store the whole graph, but it does have enough memory to identify two connected vertices, and to ask the provers the colors of those vertices.

With the class of problems Natarajan and Wright consider â called NEEXP for nondeterministic doubly exponential time â the graph sizes grow even faster than they do in MIP. Graphs in NEEXP grow at a âdoubly exponentialâ rate. Instead of increasing at a rate of powers of two â 2^{1}, 2^{2}, 2^{3}, 2^{4} and so on â the number of vertices in the graph increases at a rate of powers of powers of two â $latex 2^{2^1}, 2^{2^2}, 2^{2^3}, 2^{2^4}$Â and so on. As a result, the graphs quickly become so big that the verifier canât even identify a single pair of connected vertices.

âTo label a vertex would take 2* ^{n}* bits, which is exponentially more bits than the verifier has in its working memory,â Natarajan said.

But Natarajan and Wright prove that itâs possible to verify a three-coloring of a doubly-exponential-size graph even without being able to identify which vertices to ask the provers about. This is because you can make the provers come up with the questions themselves.

The idea of asking computers to interrogate their own solutions sounds, to computer scientists, as advisable as asking suspects in a crime to interrogate themselves â surely a foolish proposition. Except Natarajan and Wright prove that itâs not. The reason is entanglement.

âEntangled states are a shared resource,â Wright said. âOur entire protocol is figuring out how to use this shared resource to generate connected questions.â

If the quantum computers are entangled, then their choices of vertices will be correlated, producing just the right set of questions to verify a three-coloring.

At the same time, the verifier doesnât want the two quantum computers to be so intertwined that their answers to those questions are correlated (which would be the equivalent of two suspects in a crime coordinating their false alibis). Another strange quantum feature handles this concern. In quantum mechanics, the uncertainty principle prevents us from knowing a particleâs position and momentum simultaneously â if you measure one property, you destroy information about the other. The uncertainty principle strictly limits what you can know about any two âcomplementaryâ properties of a quantum system.

Natarajan and Wright take advantage of this in their work. To compute the color of a vertex, they have the two quantum computers make complementary measurements. Each computer computes the color of its own vertex, and in doing so, it destroys any information about the otherâs vertex. In other words, entanglement allows the computers to generate correlated questions, but the uncertainty principle prevents them from colluding when answering them.

âYou have to force the provers to forget, and thatâs the main thing (Natarajan and Wright) do in their paper,â Vidick said. âThey force the prover to erase information by making a measurement.â

Their work has almost existential implications. Before this new paper, there was a much lower limit on the amount of knowledge we could possess with complete confidence. If we were presented with an answer to a problem in NEEXP, weâd have no choice but to take it on faith. But Natarajan and Wright have burst past that limit, making it possible to verify answers to a far more expansive universe of computational problems.

And now that they have, itâs unclear where the limit of verification power lies.

âIt could go much further,â said Lance Fortnow, a computer scientist at the Georgia Institute of Technology. âThey leave open the possibility that you could take another step.â

nn","settings":{"socialLinks":({"type":"facebook","label":"Facebook","url":"https://www.facebook.com/QuantaNews","__typename":"SocialMediaLink"},{"type":"twitter","label":"Twitter","url":"https://twitter.com/QuantaMagazine","__typename":"SocialMediaLink"},{"type":"youtube","label":"YouTube","url":"http://youtube.com/c/QuantamagazineOrgNews","__typename":"SocialMediaLink"},{"type":"rss","label":"RSS","url":"https://api.quantamagazine.org/feed/","__typename":"SocialMediaLink"},{"type":"instagram","label":"Instagram","url":"https://instagram.com/quantamag","__typename":"SocialMediaLink"}),"newsletterAction":"https://quantamagazine.us1.list-manage.com/subscribe/post?u=0d6ddf7dc1a0b7297c8e06618&id=f0cb61321c","newsletterUrl":"http://us1.campaign-archive2.com/home/?u=0d6ddf7dc1a0b7297c8e06618&id=f0cb61321c","commentsHeader":"

n","itunesSubscribe":"https://itunes.apple.com/us/podcast/quanta-science-podcast/id1021340531?mt=2&ls=1","androidSubscribe":"https://subscribeonandroid.com/www.quantamagazine.org/feed/podcast/","trackingScripts":"rnrnrnrnrn","popularSearches":({"term":"math","label":"Mathematics","__typename":"PopularSearch"},{"term":"physics","label":"Physics","__typename":"PopularSearch"},{"term":"black holes","label":"Black Holes","__typename":"PopularSearch"},{"term":"evolution","label":"Evolution","__typename":"PopularSearch"}),"searchTopics":({"type":"Tag","label":"Podcasts","tag":{"name":"podcast","slug":"podcast","term_id":"552","__typename":"Term"},"category":{"name":null,"slug":null,"term_id":null,"__typename":"Term"},"__typename":"SearchTopic"},{"type":"Tag","label":"Columns","tag":{"name":"Quantized Columns","slug":"quantized","term_id":"551","__typename":"Term"},"category":{"name":null,"slug":null,"term_id":null,"__typename":"Term"},"__typename":"SearchTopic"},{"type":"Series","label":"Series","tag":{"name":null,"slug":null,"term_id":null,"__typename":"Term"},"category":{"name":null,"slug":null,"term_id":null,"__typename":"Term"},"__typename":"SearchTopic"},{"type":"Category","label":"Interviews","tag":{"name":"Q&A","slug":"qa","term_id":"567","__typename":"Term"},"category":{"name":"Q&A","slug":"qa","term_id":"176","__typename":"Term"},"__typename":"SearchTopic"},{"type":"Category","label":"Multimedia","tag":{"name":null,"slug":null,"term_id":null,"__typename":"Term"},"category":{"name":"Multimedia","slug":"multimedia","term_id":"43","__typename":"Term"},"__typename":"SearchTopic"},{"type":"Category","label":"Puzzles","tag":{"name":"puzzles","slug":"puzzles","term_id":"542","__typename":"Term"},"category":{"name":"Puzzles","slug":"puzzles","term_id":"546","__typename":"Term"},"__typename":"SearchTopic"},{"type":"Category","label":"Blog Posts","tag":{"name":null,"slug":null,"term_id":null,"__typename":"Term"},"category":{"name":"Abstractions blog","slug":"abstractions","term_id":"619","__typename":"Term"},"__typename":"SearchTopic"}),"searchSections":({"name":"Mathematics","slug":"mathematics","term_id":"188","__typename":"Term"},{"name":"Physics","slug":"physics","term_id":"189","__typename":"Term"},{"name":"Biology","slug":"biology","term_id":"191","__typename":"Term"},{"name":"Computer Science","slug":"computer-science","term_id":"190","__typename":"Term"}),"adBehavior":"everywhere","adUrl":"https://www.amazon.com/dp/0262536358/","adAlt":"The Prime Number Conspiracy - The Biggest Ideas in Math from Quanta – Available now!","adImageHome":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/01/Ad_Default_250x342_2x_math_3.jpg","adImageArticle":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/01/Ad_Article_320x600_math.jpg","adImageTablet":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/01/Ad_Tablet_890x250_2x_math.jpg","adImageMobile":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/01/Ad_Mobile_250x200_2x_Math.jpg"},"theme":{"page":{"accent":"#ff8600","text":"#1a1a1a","background":"white"},"header":{"type":"default","gradient":{"color":"white"},"solid":{"primary":"#1a1a1a","secondary":"#999999","hover":"#ff8600"},"transparent":{"primary":"white","secondary":"white","hover":"#ff8600"}}},"redirect":null,"fallbackImage":{"alt":"","caption":"","url":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default.gif","width":1200,"height":600,"sizes":{"thumbnail":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-520x260.gif","square_small":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-160x160.gif","square_large":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-520x520.gif","medium":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default.gif","medium_large":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-768x384.gif","large":"https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default.gif","__typename":"ImageSizes"},"__typename":"Image"}},"modals":{"loginModal":false,"signUpModal":false,"forgotPasswordModal":false,"resetPasswordModal":false,"lightboxModal":false,"callback":null,"props":null},"podcast":{"id":null,"playing":false,"duration":0,"currentTime":0},"user":{"loggedIn":false,"savedArticleIDs":(),"userEmail":null,"editor":null,"__typename":"CurrentUser"},"comments":{"open":false}},

env: {

APP_URL: 'https://www.quantamagazine.org',

NODE_ENV: 'production',

WP_URL: 'https://api.quantamagazine.org',

HAS_GOOGLE_ID: true,

HAS_FACEBOOK_ID: true,

},

} .(tagsToTranslate)algorithms(t)computational complexity(t)computer science(t)graph theory(t)mathematics(t)entanglement(t)quantum information theory(t)computing(t)quantum computing(t)theoretical computer science(t)nondeterministic doubly exponential time(t)neexp(t)mip(t)np

This is a syndicated post. Read the original post at Source link .