4
$\begingroup$

I was trying to read and understand about the complexity classes $QMA$ and $QCMA$:

$QMA$ is defined as the class with the set of problem such that, given a quantum certificate for any problem, its solution can be verified by a quantum computer in polynomial time.

$QCMA$ (as I undetstand) is defined as the class with the set of problem such that, given a classical certificate for any problem, its solution can be verified by a quantum computer in polynomial time.

Thus, the only difference between two classes seems to be the type of certificate.

Now given any $QMA-Complete$ problem, if we add an additional promise/constraint that the certificate is promised to be classical, does the resultant problem (with promise) automatically become $QCMA-Complete$?

It seems that this will be the case, but I need an external confirmation.

$\endgroup$
8
  • $\begingroup$ Interesting question. Let me ask for some clarification. A $QMA-Complete$ language is a pair $(L_{yes},L_{no})$ of disjoint languages. There's no notion of certificate in there as such. The problem statement is usually in informal prose, and also does not have a notion of 'certificate', e.g., "is this circuit the identity unitary?" What I'm asking is, what precisely do you mean when you say you "add an additional promise that the certificate is... classical"? Do you modify the $(L_{yes},L_{no})$ pair? Go into the problem statement? Look at the Arthur's verifying quantum circuit? $\endgroup$ Mar 27, 2022 at 14:19
  • $\begingroup$ Apologies for being a bit unclear (novice in QC). Lets consider any problem instance of a problem that is $QMA-Complete$. As I understand if a solution to it exists (i.e. $L_{yes}$) Merlin can always send a quantum certificate/solution to Arthur, and by definition Arthur can verify its correctness using a QC in polynomial time (lets ignore the error part). The promise is that: "For any $QMA-Complete$ problem instance, if its in $L_{yes}$ then the certificate will always be classical". $\endgroup$
    – J.Doe
    Mar 27, 2022 at 14:55
  • $\begingroup$ Does the above promise define the complexity class $QCMA-Complete$. Its seems be be the case but I am not sure? $\endgroup$
    – J.Doe
    Mar 27, 2022 at 14:56
  • $\begingroup$ @LieuweVinkhuijzen if possible can you please opine on the above? $\endgroup$
    – J.Doe
    Mar 30, 2022 at 14:43
  • 1
    $\begingroup$ (2/2) Here's an example; let me know if this is what you intended. Given a pair $(L_{yes},L_{no})\in QMA-complete$, let $K_{yes}\subseteq L_{yes}$ be the set of $x\in L_{yes}$ such that there exists a classical certificate which Arthur's Quantum Turing Machine accepts with $>2/3$ probability. If there exists a polynomial-time QTM which satisfies this description, then you conjecture that the promise language $(K_{yes},L_{no})$ is $QCMA$-Complete. That is, $K_{yes}$ is 'simply' the subset of $L_{yes}$ which can be $QCMA$-verified. Is this close to what you had in mind? $\endgroup$ Apr 10, 2022 at 18:12

0

Your Answer

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