For the Local Hamiltonian Problem, how is soundness proved if Arthur uses phase estimation on the putative ground state provided by Merlin?

Question

Recall that showing QMA-completeness of the Local Hamiltonian Problem includes showing that the problem is both (A) in (promise) QMA and (B) QMA hard. QMA hardness is usually shown with a neat bespoke circuit-to-Hamiltonian construction that records the execution of any particular circuit.

As to containment, reviewing the many great lecture notes on the internet there seems to be two traditions for showing that the problem is in QMA. In particular, Merlin gives Arthur a state $|\eta\rangle$ that is alleged to be the ground state of some $k$-local Hamiltonian $H=H_1+H_2+\cdots + H_r$ having energy $\lambda\le a$, but Arthur should be suspicious that Merlin might have given him a garbage state.

1. A first approach (I think the original one of Kitaev) involves Arthur choosing an $i\in[1,r]$ at random, and performing a projective/POVM measurement only on the $k$ qudits in the $i^{th}$ clause to confirm that the state is just such an eigenstate, with probability of catching a cheating Merlin given by $\lambda/r$. This is used in the notes of Vidick, Vaziarani, and O'Donnell, among others.
2. A second involves Arthur using the Lie-Trotter product formula in conjunction with the (inverse) Quantum Fourier Transform, acting on all of the qudits of $|\eta\rangle$ (and a few ancilla clock qubits) to get the eigenvalue of $|\eta\rangle$. This is used in the notes of Gottesman, and Preskill, for example.

Interestingly in de Wolf's lecture notes, he leaves the proof of containment for both the first and second approaches as an exercise - see problem 4 on p. 113.

Soundness from the first "I cut, you choose" approach seems pretty natural and intuitive to me - as powerful as Merlin is, he can't know which of the $r$ clauses Arthur will test. This feels analogous to other private-coin classical interactive proofs such as the fun descriptions of graph non-isomorphism involving Arthur secretly permuting the edges of one of $G$ or $H$ before giving it to Merlin, who must then decide whether Arthur gave him $\pi(G)$ or $\pi(H)$.

But for the second approach, why is running the full Quantum Phase Estimation protocol still sound?

For the second approach, for example how can Arthur be assured that Merlin didn't send him some monkey state, potentially entangled with other qubits/qudits not available to Arthur and even under Merlin's control?

Answer 1

I don't see the issue: Both strategies output "accept" with a probability which relates to the energy expectation value of the proof. Soundness comes from the fact that there cannot be a proof with energy below the ground state. Whether Merlin entangles it or not is completely useless: The reduced state of Artur is always the same.

Note that also in approach 1, the randomness is not to confuse Merlin, but to get the average energy $$ \langle\psi|H|\psi\rangle = \sum_{i} \langle\psi|H_i|\psi\rangle $$ -- the randomness just picks one term in the sum.

In the end, any procedure accepting with a probability which in a suitable way relates to the value of $\langle\psi|H|\psi\rangle$ is sound. The reason for its soundness is simply the variational principle: There is no state (neither pure nor mixed) which can have an energy below the ground state energy.