"Verification Problem" for Quantum Computers


In his book, Labyrinths of Reason, William Poundstone talks of the “Oracle of the Maze”, an oracle who can answer any question immediately. Even if he is a true oracle, convincing others isn’t easy. Why?
“Answer a question that no one else possibly could, and he is accused of fabricating; answer a question whose answer is known or knowable, and he is accused of cheating.”
So is there no way out for the oracle? Aha, there is: “a difficult question whose answer, once stated, can be verified easily”. The solution to an insanely big and twisted maze is an example, ergo, the name Poundstone gave: Oracle of the Maze.

This topic is of practical relevance (no, not maze solving; checking if an oracle is really an oracle) in… quantum computing, writes Erica Klarreich:
“Once a quantum computer can perform computations a classical computer can’t, how will we know if it has done them correctly?”
See the parallel with the Oracle of the Maze? Is there “any ironclad guarantee that it really has done what it claimed”? Worse, unlike the solution to a maze, many problems a quantum computer could solve cannot even be checked using classical methods! This then is the “verification problem”.

Researchers had proven that a verifier can check a quantum computer if the verifier can measure quantum bits. But to read a quantum bit, you needed a quantum computer. But trying to use a quantum computer to check the answer of a quantum computer is circular…

Enter Urmila Mahadev, a seventh-year graduate student at Berkeley (it probably helped that “I was never thinking of graduation, because my goal was never graduation”). Here’s the simplified gist of her solution (sorry, it’s still very technical/quantum):
1)      The quantum computer first calculates the answer;
2)     It then entangles the answer with another piece of quantum information that the computer does not know but for which the verifier himself knows the options to;
3)     At that stage, making the computer read the quantum bit(s) from the entangled entity would solve the circularity problem. Because the verifier already knows the possible options to #2, he can use that part as a check for the validity of the answer the computer found to #1.

In principle, this works. But the hard part is #2, building a “secret state” that is known only to the verifier but not the computer. Mahadev with her doctoral advisor, Umesh Vazirani, and Paul Christiano found a way to solve #2. The concept is called the “trapdoor function”. Why the name? Because the function ensures that “it’s impossible for the quantum computer to cheat significantly without leaving unmistakable traces of its duplicity”, as Klarreich puts it.

While this is a huge step in solving the “verification problem”, it still has two limitations/risks:
A)    Step #3 above is just a very educated guess: what are the odds that a quantum computer guessed the bits of an unknown piece of information by sheer chance? The lower the odds, the more likely it really works…
B)    The trapdoor function itself. It needs to be something even a quantum computer can’t crack. While we believe we know a few such functions exist, what if we were wrong and a quantum computer could solve them? Of course, that would only mean we need to find another trapdoor function, not that Mahadev’s concept is wrong.

In any case, Mahadev’s protocol won’t be feasible for at least five years, but hey, it’s not like we have quantum computers around the corner either. But it makes sense to have a way to check the correctness of one whenever it’s ready.

Comments

Post a Comment

Popular posts from this blog

Student of the Year

Image
As a toddler, my daughter loved Alia Bhatt’s songs, esp. the ones from Student of the Year . (That movie did have many good songs and well-choreographed dances). Fast forward to present day, when she is 12 yo. She rarely watches Hindi movies now, but one of the few ones she likes of late, Raja aur Rani ki Prem Kahani has, yes, Alia Bhatt.   If I had any hopes that there was anything to be read in the name of her toddler-time favorite ( Student of the Year ), they have been dashed. Our conversations come exam time are perfectly captured by this photo and its caption: In fact, the pic below captures how she and I look at her answer sheets – me intently, she with an expression of “It’s over, so why are you even looking at it?”   Of late, we pull her leg and tell her that she isn’t showing any signs of academic prowess, she’d better find a rich guy to marry. Some time later, she showed us this meme on the Internet: “Me No Study, Me No Care Me Go Marry Millionaire ...
Read more

Why we Deceive Ourselves

In their book, The Elephant in the Brain , the authors describe this weird aspect of deception that we practice: deceiving ourselves! That is so weird: “If our minds contain maps of our worlds, what good comes from having an inaccurate version of these maps?” The Sigmund Freud school of thought treats self-deception as a defense mechanism, “a way for the ego to protect itself”. The mind seeks to protect itself from anxiety and other negative emotions. Many object to this reasoning: since accurate information is so critical to our survival, surely distorting information would be dangerous. Wouldn’t the goal of protecting our self-esteem have been better achieved by making the brain’s self-esteem mechanism stronger instead? The new school of thought explains self-deception as “primarily outward-facing, manipulative, and ultimately self-serving”. This is based on Thomas Schelling’s work on game theory: “In a variety of scenarios, limiting or sabotaging yourself is the winn...
Read more

Europe #3 - Innsbruck

The last city we visited in Europe was Innsbruck in the Austrian Alps. After the cold and windy experience (at times) of Paris and Netherlands, Innsbruck was a wonderful change – it didn’t feel that cold, it was not windy all of which made it easy to walk around. Something absolutely necessary given how scenic the place is.   Since the hotel check-in time was much later in the day, we left the baggage and went to the Swarovski HQ-cum-museum about an hour by bus from Innsbruck. The crystal exhibits were brilliant – colorful, bright, shiny. Jewellery aside, it was a display of what one can do with crystals. While my wife and daughter loved the jewellery, I liked the superhero themed exhibits of Batman, Spiderman, the Hulk, and Star Wars. We didn’t buy anything there, though we did buy stuff in the Swarovski store in Innsbruck – jewellery, not the superhero stuff.   Innsbruck is a major tourist attraction during the skiing season but now in summer, we saw many groups of ...
Read more