<p>I would like to know the upper bound on the class of problem efficiently solved by a BQP (machine) with access to:</p>
<p>(i) a single (oracular) call to NP machine (or, <span class="math-container">$BQP^{NP[1]}$</span>)</p>
<p>(ii) poly-logarithmic number of call to NP machine (or, <span class="math-container">$BQP^{NP[log(n)]}$</span>)</p>
<p>(ii) polynomially many call to NP machine (or, <span class="math-container">$BQP^{NP}$</span>)</p>
<p><strong>Main query:</strong> Is class QMA (Quantum Merlin Arthur) class contained in the case(iii)?</p>
<hr />
<p><strong>My attempt:</strong></p>
<ul>
<li>By definition of <strong>QCMA</strong> (Quantum-<strong>Classical</strong> Merlin Arthur) which requires classical proof from Merlin to be verified by Arthur (BQP verifier). <strong>As per my undersatnding</strong>, the classical proof can be guessed by the (all powerful) Merlin (who is assumed to have an access to NP oracle too).</li>
</ul>
<p><strong>Claim I:</strong> Thus I <strong>infer</strong> <span class="math-container">$QCMA\subseteq BQP^{NP}$</span></p>
<ul>
<li>By definition of <strong>QMA</strong> (Quantum Merlin Arthur) which requires quantum proof from Merlin to be verified by Arthur (BQP verifier).
<strong>As per my undersatnding</strong>, the <strong>quantum proof</strong> is guessed by the Merlin (who is assumed to have an access to <em>quantum non-deterministic machine</em> (say, QNDTM).</li>
</ul>
<p><strong>Query-I:</strong>  Is power of QNDTM captured by (a) <span class="math-container">$BQP^{NP}$</span> or is it (b) <span class="math-container">$NP^{BQP}$</span>?</p>
<p>If (a) is the case then <span class="math-container">$QMA\subseteq BQP^{BQP^{NP}} = BQP^{NP}$</span>. (due to self low property of BQP class).</p>

CC BY-SA 4.0
2024-08-21T12:37:21.430Z
The classical witness that Merlin guesses using ^{} has to be a classical witness for an NP problem, not a classical witness for a QCMA problem. So your argument for Claim 1 doesn't seem to work; it's not clear that QCMA ⊆ BQP^{NP}.
Peter Shor 
CC BY-SA 4.0
2024-08-22T03:30:51.300Z
@Peter, point taken. I see the flaw in my argument. 
// side comment: (I) I am now looking for how $QCMA$ and $BQP^{NP}$ behave in a relativized world.
Manish Kumar
CC BY-SA 4.0
2024-08-22T03:31:06.923Z
(continue...) (II) I am aware of one (weak!) supporting argument for posing the conjecture $QCMA\subseteq BQP^{NP}$. This is due to quantum-classical PCP conjecture. If it holds then $QCMA\subseteq BQP^{NP[1]}$!!! [ ref: Theorem 1.3 in https://arxiv.org/pdf/2302.11578 along with their conjecture about QC-PCP.
Manish Kumar
<quantum-computing><np><qma>
How powerful is Quantum Turing machine with an oracle access to NP?
Manish Kumar
# How powerful is Quantum Turing machine with an oracle access to NP?

(Asked by: username_0 on 2024-08-14)

I would like to know the upper bound on the class of problem efficiently solved by a BQP (machine) with access to:

(i) a single (oracular) call to NP machine (or, $BQP^{NP[1]}$)

(ii) poly-logarithmic number of call to NP machine (or, $BQP^{NP[log(n)]}$)

(ii) polynomially many call to NP machine (or, $BQP^{NP}$)

**Main query:** Is class QMA (Quantum Merlin Arthur) class contained in the case(iii)?

---

**My attempt:**

* By definition of **QCMA** (Quantum-**Classical** Merlin Arthur) which requires classical proof from Merlin to be verified by Arthur (BQP verifier). **As per my undersatnding**, the classical proof can be guessed by the (all powerful) Merlin (who is assumed to have an access to NP oracle too).

**Claim I:** Thus I **infer** $QCMA\subseteq BQP^{NP}$

* By definition of **QMA** (Quantum Merlin Arthur) which requires quantum proof from Merlin to be verified by Arthur (BQP verifier).
  **As per my undersatnding**, the **quantum proof** is guessed by the Merlin (who is assumed to have an access to *quantum non-deterministic machine* (say, QNDTM).

**Query-I:** Is power of QNDTM captured by (a) $BQP^{NP}$ or is it (b) $NP^{BQP}$?

If (a) is the case then $QMA\subseteq BQP^{BQP^{NP}} = BQP^{NP}$. (due to self low property of BQP class).

**Tags:** quantum-computing, np, qma

> **Comments:**
> **username_1**: The classical witness that Merlin guesses using ^{} has to be a classical witness for an NP problem, not a classical witness for a QCMA problem. So your argument for Claim 1 doesn't seem to work; it's not clear that QCMA ⊆ BQP^{NP}.  
> **username_0**: @Peter, point taken. I see the flaw in my argument.  // side comment: (I) I am now looking for how $QCMA$ and $BQP^{NP}$ behave in a relativized world.  
> **username_0**: (continue...) (II) I am aware of one (weak!) supporting argument for posing the conjecture $QCMA\subseteq BQP^{NP}$. This is due to quantum-classical PCP conjecture. If it holds then $QCMA\subseteq BQP^{NP[1]}$!!! [ ref: Theorem 1.3 in https://arxiv.org/pdf/2302.11578 along with their conjecture about QC-PCP.  

---

## 0 answers

