"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 If He Die
Read more

The Retort of the "Luxury Person"

Image
Coming up with biting and witty retorts. It’s something we dream of, but rarely manage to pull off. Worse, the more we stew over the offending remark, the more likely we are to come up with that dream retort, as Calvin ruefully points out: During our last holiday at the Taj Resort, seeing my wife carrying towels to our poolside chairs, one of the kids there mistook her for a member of the staff and asked for a towel. When my wife narrated this to us, I did not imagine that my 8 yo daughter would come up with her own retort. But a day later, my daughter recapped the incident, an incident that didn’t even involve her in the first place , and said, “You know what I’d have told that kid who asked for the towel?”. And without waiting for an answer, she told us anyway: “I don’t work here. I too am a luxury person who is living at this resort. Go get your own towel.” We were highly amused by the phrase she had coined: “luxury person”. It certainly captures the kind of holid
Read more

Animal Senses #7: Touch and Remote Touch

Instinctively, we think touch is based on contact. Not entirely true, explains Ed Yong in Immense World – there’s a more important aspect than contact: “These incredible feats are possible through movement. If you rest a fingertip upon a surface, you can get only a limited idea of its features. But as soon you’re allowed to move, everything changes. Hardness becomes apparent with a press. Textures resolve at a stroke.” As you run your fingers over a surface, they hit the tiny peaks and troughs and set off vibrations in the mechanoreceptors at their tips.   At the tip of its snout, the star-nosed mole has many pairs of hairless appendages. It uses them to touch things around itself. Alive or dead? Food or ignore? It does these movements at an insane speed. In the time it takes to blink our eyes, the star-nosed mole can probe, identify and swallow its food. “Light may be the fastest thing in the universe, but light sensors have their limits, and the star-nosed mole’s sense of
Read more