Graduate Student Solves Quantum Verification Problem
October 8, 2018 10:01 PM Subscribe
Urmila Mahadev spent eight years in graduate school solving one of the most basic questions in quantum computation "How do you know whether a quantum computer has done anything quantum at all?"
Dr. Mahadev's (she recently finished her PhD) paper, Classical Verification of Quantum Computations has been described as “one of the most outstanding ideas to have emerged at the interface of quantum computing and theoretical computer science in recent years.”
Erika Klarreich's article on this achievement goes into much more detail. (Same link as the title.)
Erika Klarreich's article on this achievement goes into much more detail. (Same link as the title.)
I wish I understood this better but it seems very impressive.
When I read articles like this for lay people like me I get to sentences like this and just wonder if they're making stuff up:
Mahadev showed that it’s impossible for the quantum computer to cheat significantly without leaving unmistakable traces of its duplicity. Essentially, Vidick wrote, the qubits the computer is to measure have been “set in cryptographic stone.”
Like, what the hell is this Star Trek shit?? But obvs it's just light-years above my head.
posted by latkes at 10:27 PM on October 8, 2018 [5 favorites]
When I read articles like this for lay people like me I get to sentences like this and just wonder if they're making stuff up:
Mahadev showed that it’s impossible for the quantum computer to cheat significantly without leaving unmistakable traces of its duplicity. Essentially, Vidick wrote, the qubits the computer is to measure have been “set in cryptographic stone.”
Like, what the hell is this Star Trek shit?? But obvs it's just light-years above my head.
posted by latkes at 10:27 PM on October 8, 2018 [5 favorites]
The thing is, with an article like this, the point is that this woman did this amazing thing through her perservance. Most Star Trek episodes are also like this, with technobabble occurring when someone is learning what the problem is, or what the solution to the problem is. And when you're watching those shows you just hand-wave away the technobabble.
You can hand-wave it away here too and focus on the true narrative, except that the technobabble may actually have an impact on your life within the next decade so WOW THAT IS GROOVY COOL.
posted by hippybear at 10:30 PM on October 8, 2018 [6 favorites]
You can hand-wave it away here too and focus on the true narrative, except that the technobabble may actually have an impact on your life within the next decade so WOW THAT IS GROOVY COOL.
posted by hippybear at 10:30 PM on October 8, 2018 [6 favorites]
This is really cool; I get the impression that Post Quantum Crypto is a big deal right now, and this feels foundational, like Paxos or CAP.
[The writing was really great but I guarantee you I will not be able to explain this to anyone in the morning]
posted by batter_my_heart at 11:16 PM on October 8, 2018
[The writing was really great but I guarantee you I will not be able to explain this to anyone in the morning]
posted by batter_my_heart at 11:16 PM on October 8, 2018
In addition to what hippybear said, I found it rewarding to read about a woman with such a classical name - Urmila Urmila is notable for her unparalleled sacrifice called Urmila Nidra
/plus the feeling of being represented
posted by infini at 11:43 PM on October 8, 2018 [3 favorites]
/plus the feeling of being represented
posted by infini at 11:43 PM on October 8, 2018 [3 favorites]
So we can cheat too (for a subset of otherwise computationally intractable problems).
posted by solarion at 1:18 AM on October 9, 2018 [2 favorites]
posted by solarion at 1:18 AM on October 9, 2018 [2 favorites]
Why are we developing cheating computers?
So that AI can be truly human?
posted by Thorzdad at 4:22 AM on October 9, 2018 [1 favorite]
So that AI can be truly human?
posted by Thorzdad at 4:22 AM on October 9, 2018 [1 favorite]
It's not so much that the computer is likely to cheat, but that a vital principal of modern computing is testing correctness where possible. The quantum computer could be used to solve a problem that is not only impractical/impossible to solve otherwise, but it's impractical to check the answer. But they can have bugs or errors too. In fact because they operate probabilistically, checking the result (and possibly re-running) is expected to be part of the process of using a quantum computer (at least last I heard).
Imagine you pay $$$ to some institution that's providing access to quantum computing as a service: you ask to solve question Q and their machine says the answer is A, but you can't check that the answer is right because the problem is that hard. You just have to use the answer. The previous result was that if you had your own mini quantum computer you could use that to verify. This result allows you to cryptographically embed a problem you can check on a normal computer within your original problem, thus verifying that answer A is actually an answer to your question Q. Yes, the cryptographic part does prevent fraud, but I think the point is that it's a proof of correctness.
posted by Humanzee at 4:33 AM on October 9, 2018 [13 favorites]
Imagine you pay $$$ to some institution that's providing access to quantum computing as a service: you ask to solve question Q and their machine says the answer is A, but you can't check that the answer is right because the problem is that hard. You just have to use the answer. The previous result was that if you had your own mini quantum computer you could use that to verify. This result allows you to cryptographically embed a problem you can check on a normal computer within your original problem, thus verifying that answer A is actually an answer to your question Q. Yes, the cryptographic part does prevent fraud, but I think the point is that it's a proof of correctness.
posted by Humanzee at 4:33 AM on October 9, 2018 [13 favorites]
> Why are we developing cheating computers?
> So that AI can be truly human?
"How about a nice game of chess... Whoa, look, what's that behind you!?"
posted by Greasy Eyed Gristle Man at 4:54 AM on October 9, 2018 [10 favorites]
> So that AI can be truly human?
"How about a nice game of chess... Whoa, look, what's that behind you!?"
posted by Greasy Eyed Gristle Man at 4:54 AM on October 9, 2018 [10 favorites]
Imagine you pay $$$ to some institution that's providing access to quantum computing as a service: you ask to solve question Q and their machine says the answer is A, but you can't check that the answer is right because the problem is that hard. You just have to use the answer.
My quantum computer said 43, but Adams went with the low bidder. Whuddaya gonna do?
posted by Cris E at 8:01 AM on October 9, 2018 [2 favorites]
My quantum computer said 43, but Adams went with the low bidder. Whuddaya gonna do?
posted by Cris E at 8:01 AM on October 9, 2018 [2 favorites]
Metafilter: Like, what the hell is this Star Trek shit??
posted by RolandOfEld at 8:04 AM on October 9, 2018 [2 favorites]
posted by RolandOfEld at 8:04 AM on October 9, 2018 [2 favorites]
(like Schrödinger’s cat, which is simultaneously dead and alive)
But the cat knows, right? This bit has always nagged at my soul. Why not something purely material, no consciousness to muck things up? Instead of the atomic clock triggering a poison vial, why not just a paint bomb or similar? The box is green or not green.
posted by Meatbomb at 8:08 AM on October 9, 2018 [2 favorites]
But the cat knows, right? This bit has always nagged at my soul. Why not something purely material, no consciousness to muck things up? Instead of the atomic clock triggering a poison vial, why not just a paint bomb or similar? The box is green or not green.
posted by Meatbomb at 8:08 AM on October 9, 2018 [2 favorites]
(like Schrödinger’s cat, which is simultaneously dead and alive)
But the cat knows, right? This bit has always nagged at my soul.
Schrödinger intended the experiment to be "quite ridiculous": obviously the cat is alive or dead independent of our observation of it. Einstein agreed.
posted by Etrigan at 8:31 AM on October 9, 2018 [1 favorite]
But the cat knows, right? This bit has always nagged at my soul.
Schrödinger intended the experiment to be "quite ridiculous": obviously the cat is alive or dead independent of our observation of it. Einstein agreed.
posted by Etrigan at 8:31 AM on October 9, 2018 [1 favorite]
Quick, get her a Wikipedia page!
posted by Big Al 8000 at 8:36 AM on October 9, 2018 [6 favorites]
posted by Big Al 8000 at 8:36 AM on October 9, 2018 [6 favorites]
Why not something purely material, no consciousness to muck things up?
I don't think this makes any difference, since the thought experiment is based on an observer's point-of-view, and the incoherence of a mixed dead/alive feline state, even for that observer.
posted by thelonius at 8:57 AM on October 9, 2018
I don't think this makes any difference, since the thought experiment is based on an observer's point-of-view, and the incoherence of a mixed dead/alive feline state, even for that observer.
posted by thelonius at 8:57 AM on October 9, 2018
> But the cat knows, right? This bit has always nagged at my soul.
"Knowing" is a phenomenon caused by systems of atoms, and would itself be in a state of superposition. When people talk about observation, they are being a bit loose with words. Practically speaking, what's important is entanglement. Observation has nothing to do with consciousness: you observe a particle by hitting it with a photon and causing it to become entangled with an outside system. A cat has so many particles that the probability of putting them all into perfect superposition at the same time is practically impossible. The idea that this could be achieved by releasing a substance that is already entangled with you is what makes it completely ridiculous.
posted by I-Write-Essays at 9:36 AM on October 9, 2018
"Knowing" is a phenomenon caused by systems of atoms, and would itself be in a state of superposition. When people talk about observation, they are being a bit loose with words. Practically speaking, what's important is entanglement. Observation has nothing to do with consciousness: you observe a particle by hitting it with a photon and causing it to become entangled with an outside system. A cat has so many particles that the probability of putting them all into perfect superposition at the same time is practically impossible. The idea that this could be achieved by releasing a substance that is already entangled with you is what makes it completely ridiculous.
posted by I-Write-Essays at 9:36 AM on October 9, 2018
Asimov's three (later four) laws of robotics do not include any requirement that robots be truthful, so this is a good thing.
posted by DevilsAdvocate at 9:50 AM on October 9, 2018
posted by DevilsAdvocate at 9:50 AM on October 9, 2018
Also: Entanglement is a type of state in which a quantum system can be, where everything there is to know about the state of that system can be expressed by giving the correlations between particles, and that the particles have no independent state individually. It is one of the ways in which reductionism breaks down at extremely small scales.
posted by I-Write-Essays at 9:52 AM on October 9, 2018
posted by I-Write-Essays at 9:52 AM on October 9, 2018
oh so this is how Janet learned to lie after repeated reboots
posted by numaner at 1:55 PM on October 9, 2018 [3 favorites]
posted by numaner at 1:55 PM on October 9, 2018 [3 favorites]
I am by no means an expert in this field (though I did study complexity theory in grad school), but I am inclined to agree with batter_my_heart that this feels foundational. After skimming the arXiv paper, it seems to me that not only is the proof explicitly constructive, it actually seems practical to construct the required functions (at least, relatively speaking).
Of course, if it is practical to implement the protocol, I wonder if now someone can get D-Wave, the quantum computer start-up, to finally prove that they really have implemented a quantum computer or, as some others have suspected, just a really fast non-quantum computer. Last I heard, their machines were extremely specialized so it was hard to really probe and test them so maybe it's still up in the air.
posted by mhum at 6:21 PM on October 9, 2018
Of course, if it is practical to implement the protocol, I wonder if now someone can get D-Wave, the quantum computer start-up, to finally prove that they really have implemented a quantum computer or, as some others have suspected, just a really fast non-quantum computer. Last I heard, their machines were extremely specialized so it was hard to really probe and test them so maybe it's still up in the air.
posted by mhum at 6:21 PM on October 9, 2018
mhum, did the proof make use of complexity theory? Leonard Susskind has been a big advocate of using quantum circuit complexity to measure distance between states, and trying to link it as the quantity that increases when space grows behind the horizon of a black hole. It would be really cool if complexity has turned up in a big way like this.
Here are his latest lectures on the subject from PitP 2018: "Complexity and Gravity" 1 2 3
posted by I-Write-Essays at 9:36 PM on October 9, 2018
Here are his latest lectures on the subject from PitP 2018: "Complexity and Gravity" 1 2 3
posted by I-Write-Essays at 9:36 PM on October 9, 2018
did the proof make use of complexity theory?
I wouldn't say that the proof "made use" of complexity theory as much as it is itself a result in complexity theory. Because it's about quantum stuff, it seems like it's about physics but, really, the quantum stuff is more of an abstraction of a computation model than about physical phenomena (at least in my reading of it).
posted by mhum at 9:07 AM on October 10, 2018
I wouldn't say that the proof "made use" of complexity theory as much as it is itself a result in complexity theory. Because it's about quantum stuff, it seems like it's about physics but, really, the quantum stuff is more of an abstraction of a computation model than about physical phenomena (at least in my reading of it).
posted by mhum at 9:07 AM on October 10, 2018
In what subject areas would one need to be fluent to understand Dr. Mahadev's paper? I'm guessing QM and number theory. I took QM a few decades ago but know nothing of number theory (or any other area in discrete). Would I need to know large swathes of NT or just crypto? Or something else?
posted by neuron at 10:26 AM on October 10, 2018
posted by neuron at 10:26 AM on October 10, 2018
I would say that number theory is not really pre-requisite or even that much needed in this result. Even QM is not necessarily pre-requisite but probably would help to get a jump-start on understanding some of the concepts. The real subject area that you'd need to be fluent in is quantum information science, specifically quantum computing. I don't see anything in there that would require quantum information theory, but I haven't read the papers it references so maybe there's some of that in there too. Anyways, quantum computing is almost kind of its own thing that straddles computational complexity theory (from theoretical computer science) and quantum physics.
posted by mhum at 5:01 PM on October 10, 2018 [1 favorite]
posted by mhum at 5:01 PM on October 10, 2018 [1 favorite]
I didn't fully understand the article (my background is classical computing, not quantum) but I did enjoy at least trying to understand it.
And i really, really enjoyed how it was just a straightforward article about a woman of colour engaged in science without any bullshit framing that harps on that (see: zillions of articles about female scientists that start with a paragraph about their reproductive status or marriage). She just is and she's remarkable because of the science she did.
posted by jacquilynne at 7:31 AM on October 14, 2018
And i really, really enjoyed how it was just a straightforward article about a woman of colour engaged in science without any bullshit framing that harps on that (see: zillions of articles about female scientists that start with a paragraph about their reproductive status or marriage). She just is and she's remarkable because of the science she did.
posted by jacquilynne at 7:31 AM on October 14, 2018
I mean I don't understand any of this at all but that is a nicely-written paper for sure.
posted by turbid dahlia at 6:02 PM on October 14, 2018
posted by turbid dahlia at 6:02 PM on October 14, 2018
Super agreeing with jacquilynne -- I am so ridiculously happy for Mahadev! Also I love that she did not know she wanted to do CS until partway through her undergrad -- a data point here saying that at least some brilliant computer scientists didn't hear their calling as, like, infants.
Those of you in the Boston area: on the 26th she gives a talk at MIT.
posted by brainwane at 7:30 AM on October 24, 2018
Those of you in the Boston area: on the 26th she gives a talk at MIT.
posted by brainwane at 7:30 AM on October 24, 2018
« Older Good food | United Daughters of the Confederacy Problematic... Newer »
This thread has been archived and is closed to new comments
posted by hippybear at 10:26 PM on October 8, 2018 [6 favorites]