How can one cheat in Mahadev's classical verification protocol if one can find a "claw''?

Question

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.

Thanks in advance.

Answer 1

I don't understand all of the details of the protocol, but to provide a tentative answer, in Mahadev's scheme the verifier (Vickey) is always purely classical, and only trades classical information back and forth with the prover (Peggy). Vickey does not do any QMA verification alone, as she is not a QMA machine herself, and doesn't receive any qubits from Peggy but only receives classical information.

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.