3
$\begingroup$

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?

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ The claim about the outsourcing does not make much sense to me; how would a classical verifier make sure that a quantum verifierr carries out the correct verification on a quantum state the classical verifier has no control of? $\endgroup$ Jun 14, 2023 at 15:22
  • $\begingroup$ Mahadev’s work is on classical verification of BQP machines. If a BQP machine were to receive a putative certificate $|\psi\rangle$ from a potentially more powerful Merlin, are you saying that classical Arthur has no way of binding his quantum BQP machine fiend to run phase estimation? $\endgroup$ Jun 14, 2023 at 15:27
  • $\begingroup$ How would they, given that they don't know anything about the state? The verification protocol does not allow for unknown quantum inputs to the circuit, and since it is unknown, there's ample of ways to cheat. $\endgroup$ Jun 14, 2023 at 17:04
  • $\begingroup$ @NorbertSchuch would you agree that if Merlin gave a classical Arthur a QCMA certificate, then the classical Arthur could outsource the work to a BQP machine by following Mahadev? $\endgroup$ Jun 14, 2023 at 18:01
  • 1
    $\begingroup$ I would have to look more closely again into the Mahadev protocol (it verifies that someone has a BQP machine, I'm not 100% sure on the spot whether this immediately implies that one can verify an arbitrary BQP computation, and complexity questions can be rather subtle), but I'd assume yes. But this is unrelated both to the question and the claim in your answer. (Not to mention that it still requires that the verifier is in possession of a BQP machine, in one way or another.) $\endgroup$ Jun 14, 2023 at 21:33
4
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ please provide links to sources for your statements $\endgroup$
    – glS
    Jun 13, 2023 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.