Is verifying the solution to a QMA-complete problem efficient?

Question

I am interested in the current state of the art on the difficulty of verifiability of a QMA complete problem, such as the local Hamiltonian problem. Suppose you are given a solution to a QMA complete problem, and you would like to verify it. Is the act of verification efficient for a classical verifier? What about the quantum verifier?

From my understanding, QMA-complete problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a candidate solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. However, I am not sure about the efficiency of verification for classical verifiers. Can anyone provide more information or insights on this topic?

Answer 1

Indeed for the standard, conventional QMA-complete Local Hamiltonian problem,

1. An all-powerful Merlin and a BQP-capable Arthur agree on a local Hamiltonian $\mathcal H$ acting on $n$ qubits;
2. Merlin provides Arthur the $n$-qubit witness $|\psi\rangle$ that is promised to be in an eigenstate of $\mathcal H$ having an eigenvalue less than some value $a$;
3. Arthur uses Hamiltonian simulation on $\mathcal H$ to run a quantum phase estimation algorithm on $|\psi\rangle$; and
4. Arthur can validate whether the measured energy eigenvalue is less than $a$.

As @Norbert indicated the verifier Arthur must be capable of running the BQP phase estimation algorithm (including the Hamiltonian simulation), which means Arthur should be quantum (assuming that BPP$\ne$BQP).

But, following a breakthrough by Mahadev, a classical Arthur can use post-quantum cryptography to outsource the running of BQP algorithms to a quantum machine! See this somewhat more accessible Quanta magazine article on Mahadev's results.

As @Norbert also indicates in the comments, however, it's not entirely clear if Mahadev's protocol carries through for the verification of QMA certificates. For example, an all-powerful QMA machine Merlin may provide a certificate $|\psi\rangle$ to a BQP machine, Guinevere, who then engages in a post-quantum cryptographic protocol with the fully classical Arthur. But, Merlin may be sneaky enough to trap Guinevere into being able to convince Arthur that Guinevere has received the proper quantum certificate $|\psi\rangle$, when in reality she's received garbage $|\psi'\rangle$. (I think the results do carry over, just thinking about the QMA certificate for group non-membership and the two test that Arthur can run. But, it's not clear and maybe a separate question).

However, Mahadev's protocol likely does carry over to verifications of QCMA certificates. There an powerful Merlin provides Arthur with a classical description of a quantum circuit that can be used to build the witness string $|\psi\rangle$, from which then Arthur could instruct Guinevere to construct and execute the verification. In the QCMA case, all-powerful Merlin never directly engages with BQP-bounded Guinevere.

Answer 2

Unless QMA = NP (which is generally believed not to be the case - at least so I think), there are problems in QMA for which the proof (at least in part of the instances) cannot be efficiently checked on a classical computer. In particular, this must be the case for any QMA-complete problem.

On the other hand, quantum verifiers can, by definition, efficiently check the proof for any yes-instance of a QMA problem.

Answer 3

Specifically, it is conjectured that there is no classical polynomial-time algorithm that can verify QMA-complete problems in general and impossible for classical verifier. theoretically the quantum verifier can do it but resource un available. It is important to note that while quantum verification may be efficient for QMA-complete problems, the resources required to generate the solution, the prover's quantum computation, can still be quite demanding.