# 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(for an overview see this excellent talk by her). 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 prover just looks at a single qubit part of his state (I am also very confused as to how the entanglement between the different qubits don't play any role here) and the author assumes this to be some pure state $$|\psi\rangle=\alpha_0|0\rangle+\alpha_1|1\rangle.$$ To commit to this state, the prover entangles this state with the two pre-images $$x_0,x_1$$ of the trapdoor clawfree function pair $$f_0,f_1$$ using a quantum oracle and sends back the classical string $$y=f(x_0)=f(x_1)$$. At this point, the prover holds the state $$|\psi_{ent}\rangle=\alpha_0|0\rangle|x_0\rangle+\alpha_1|1\rangle|x_1\rangle$$ which is a state that he himself doesn't know the full description of because it is hard to know $$x_0 \; \text{and}\; x_1$$ (actually even one of bit of $$x_1$$) simultaneously. The rest of the paper uses this ignorance to tie the hands of the prover and states that if the prover applies some arbitrary unitary to his state $$|\psi_{enc}\rangle$$ this U is computationally randomized both by the state encoding and the decoding of the verifier.

But my question is a lot simpler (and naive). I don't understand how the prover can apply an arbitary unitary even if he knew the full description of the state $$|\psi_{enc}\rangle$$. If the ground state of the Hamiltonian is unique, how can the prover apply a known unitary to his state and still expect to pass the Local Hamiltonian test? I am sure I am missing something trivial.

Also, it would be nice if someone can explain why the entanglement between the different qubit of the ground state can be just ignored and why the mixed case treatment is identical to the analysis done assuming pure states for each qubit.

• I don't know for sure, but to begin with let's call the prover Peggy and the verifier Vickey. If Peggy had broken the claw, she has access to $x_0$ and $x_1$, and she's also provided an $f(x_0)=f(x_1)$ to Vickey. But then if Peggy has broken the claw, my understanding is that she can do all of her work to fool Vickey classically, and she doesn't need to apply unitaries to any qubits at all, I believe. I might be fuzzy about this but the claw is supposed to bind Peggy to work coherently; a break in the claw-e.g. knowledge of $(x_0,x_1)$-lets her work classically to send junk to Vickey. May 16 at 23:30
• Hi Mark, thank you for your comment. Yes, I mostly understand this part but my question is how actually can Peggy be sure that if she cheats by sending classical distributions, she will pass the Local Hamiltonian test (QMA verification) with high enough probability? May 17 at 0:48
• I think she could just provide junk to the verifier. She doesn’t need to actually do anything quantum. Vickey would have no way to verify anyway... May 17 at 2:30
• What do you mean? Vickey does the QMA verification himself, no? After he gets the measurement outcomes from Peggy, he picks a term in the Hamiltonian at random to test if it passes with high probability. He can definitely catch Peggy if she gives him just junk. May 17 at 2:40

Vickey has no power to do the local Hamiltonian evaluation with qubits. Although it's true that Vickey can pick a term in the Hamiltonian for evaluation, she has to trade classical information with Peggy to evaluate the term of the Hamiltonian. If Peggy has access to the claw - that is, if she knows $$x_0$$ and $$x_1$$ such that $$f(x_0)=f(x_1)=y$$, then she has the same information that Vickey would use for the verification - she can play the role of Vickey herself. She could send $$x_0$$ or $$x_1$$ or a string $$d$$ orthogonal to $$x_0\oplus x_1$$ as needed to Vickey.
For example if Peggy has broken the claw then she doesn't need to apply any unitary, and indeed doesn't need to be quantum at all, but only needs to trade enough classical information with Vickey to trick Vickey into accepting. If Vickey asks for an $$x_b$$ and a $$b$$, or if she asks for a $$d$$, then Peggy can provide either as needed.
• Also please note that asking for a string d orthogonal to $x_0\oplus x_1$ is not part of the quantum verification protocol. It is used in a different paper for testing for certifiable randomness and genuine quantumness. May 18 at 4:56
• Two comments. Peggy cannot get away with just classical junk. There is a test round in the protocol that asks for a preimage $x_0 \text{ or } x_1$. This ensures that at some point in time Penny held a state that had $x_0 \text{ and } x_1$ in superposition. Regarding the terms yes, she can calculate the expectation of all of these but with respect to what? The ground state she has, sure. How does she know of a different distribution that passes the same test? And how she is guaranteed that if she samples from these two diff. distributions at random, she will still pass? May 18 at 17:29
• The title of your question is "How can one cheat in Mahadev's classical verification protocol if one can find a "claw''?, which I take to mean that the prover has access to the classical bitstrings $x_0$ and $x_1$. If the prover has access to these bitstrings, she can provide either $x_0$ or $x_1$ as needed (e.g. provide a pre-image), or she could classically simulate the effect of a Hadamard transform on $x_0$ and $x_1$ (e.g. she could simulate a "proof of superposition"). May 18 at 18:14