Classical Verification of Quantum Computations - Urmila Mahadev
Why Quantum Computing Stack Exchange recommends it
Quantum Computing Stack Exchange users point people to it as the speaker's own explanation of classical verification, both for newcomers following the topic and for askers working through the protocol's details.
Recommended by 1 people across 1 different months, 2018 to 2022.
What it is
A one-hour seminar at the Institute for Advanced Study in which Urmila Mahadev (UC Berkeley) presents her protocol that lets a purely classical verifier check the results of a quantum computation. It covers the cryptographic idea behind it, using trapdoor claw-free functions built from learning with errors.
What people said
Recommends Arnab · 2021-05 · Quantum Computing Stack Exchange · on “How can one cheat in Mahadev's classical verification protocol if one can find a "claw''?”
I was going through the seminal paper of Urmila Mahadev on Classical Verification of Quantum Computations [LINK] (for an overview see this excellent talk by her [this video] ). As a physicist by training, I am not very familiar with cryptographic strategies. Thus, I am not sure how exactly an adversary prover can get away with cheating if he can break the computational assumption of hardness of LWE (learning with errors) and thereby find a claw for the Trapdoor claw-free function pair. Specifically, the protocols starts out with the quantum prover creating an arbitrary state that he expects to pass the Local Hamiltonian test (so ideally the ground state of the Hamiltonian). For this state, the pr
Cites new_bee · 2018-12 · Quantum Computing Stack Exchange · on “Why it is hard to simulate a quantum device by a classical devices?”
I was recently watching a talk by Urmila Mahadev on "Classical Verification of Quantum Computations" ( see this [this video] ). I am not new to quantum computation just have a familiarity with the qubit and some part of quantum mechanics. I even did not get the meaning of the simulation. I am guessing it means that given an encoding of a quantum device with input. The classical device will take this encoding and get the results. The only thing which I have understood is that there may be many states in which quantum device can go through on a particular input. Question: Why it is hard to simulate a quantum device by a classical device? Please note that I am not sure what it means by " hard ". Is
Cites Mark Spinelli · 2022-08 · Quantum Computing Stack Exchange · on “Can we use cryptocurrency mining to verify claims of quantum advantage?”
Beginning with the earlier works of work of Brakerski et al. [LINK] or the more recent results of Kahanamoku-Meyer et al. [LINK] , interactive proofs of quantum advantage entail a classical verifier (Vicky) providing a quantum prover (Peggy) a circuit to evaluate a trapdoor claw-free function $f$ in superposition, e.g. Peggy prepares $\sum|x\rangle|f(x)\rangle$ , and evaluates the first and second register in the Hadamard and computational basis, respectively. See, e.g., Mahadev's lecture [this video] that expands these ideas into her breakthrough procedure to classically verify a quantum computation. These interactive procedures have Peggy to evaluate certain trapdoor claw-free functions. I'd li