<p>I was trying to read and understand about the complexity classes <span class="math-container">$QMA$</span> and <span class="math-container">$QCMA$</span>:</p>
<p><span class="math-container">$QMA$</span> 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.</p>
<p><span class="math-container">$QCMA$</span> (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.</p>
<p>Thus, the only difference between two classes seems to be the type of certificate.</p>
<p>Now given any <span class="math-container">$QMA-Complete$</span> problem, if we add an additional promise/constraint that the certificate is promised to be classical, does the resultant problem (with promise) automatically become <span class="math-container">$QCMA-Complete$</span>?</p>
<p>It seems that this will be the case, but I need an external confirmation.</p>

CC BY-SA 4.0
2022-03-27T14:19:30.490Z
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?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-03-27T14:55:46.870Z
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".
J.Doe
CC BY-SA 4.0
2022-03-27T14:56:35.583Z
Does the above promise define the complexity class $QCMA-Complete$. Its seems be be the case but I am not sure?
J.Doe
CC BY-SA 4.0
2022-03-30T14:43:53.693Z
@LieuweVinkhuijzen if possible can you please opine on the above?
J.Doe
CC BY-SA 4.0
2022-04-10T10:07:25.757Z
can anyone please clarify this ??
J.Doe
CC BY-SA 4.0
2022-04-10T18:05:42.883Z
(1/2) Thanks for your reponse. What I'm asking is, can you define mathematically how you would transform a $QMA$-Complete language $(L_{yes},L_{no})$ to a pair of languages in your paradigm? How would the transformation work? Would it work for all pairs of languages? An obstacle that I see is that, for example, given the circuit that Arthur uses there may not always be a classical certificate with high acceptance probability; whereas it may be the case that Arthur there is a classical certificate if Arthur uses a different circuit.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-04-10T18:12:25.963Z
(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?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-04-10T18:50:38.103Z
@LieuweVinkhuijzen Thank you. I think its close to what I am saying. The 'promise' amounts to saying that, if for the certificate $x$, $x\in L_{yes}$ that it is also the case that $x\in K_{yes}$ thus, the promise language is $(K_{yes},L_{no})$. Thanks again. It answers my question.
J.Doe
<cc.complexity-theory><quantum-computing>
Relationship b/w $QMA$ and $QCMA$
J.Doe
# Relationship b/w $QMA$ and $QCMA$

(Asked by: username_0 on 2022-03-27)

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.

**Tags:** cc.complexity-theory, quantum-computing
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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".  
> **username_0**: Does the above promise define the complexity class $QCMA-Complete$. Its seems be be the case but I am not sure?  
> **username_0**: @LieuweVinkhuijzen if possible can you please opine on the above?  
> **username_0**: can anyone please clarify this ??  
> **username_1**: (1/2) Thanks for your reponse. What I'm asking is, can you define mathematically how you would transform a $QMA$-Complete language $(L_{yes},L_{no})$ to a pair of languages in your paradigm? How would the transformation work? Would it work for all pairs of languages? An obstacle that I see is that, for example, given the circuit that Arthur uses there may not always be a classical certificate with high acceptance probability; whereas it may be the case that Arthur there is a classical certificate if Arthur uses a different circuit.  
> **username_1**: (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?  
> **username_0**: @LieuweVinkhuijzen Thank you. I think its close to what I am saying. The 'promise' amounts to saying that, if for the certificate $x$, $x\in L_{yes}$ that it is also the case that $x\in K_{yes}$ thus, the promise language is $(K_{yes},L_{no})$. Thanks again. It answers my question.  

---

## 0 answers

