<p><span class="math-container">$\mathit{BPP}$</span> vs <span class="math-container">$\mathit{NP}$</span> and <span class="math-container">$\mathit{BQP}$</span> vs <span class="math-container">$\mathit{QMA}$</span> are two problems that are (in spirit, for classical and quantum computers respectively) similar and both are open. Moreover, we don't have any idea if <span class="math-container">$\mathit{BQP}$</span> and <span class="math-container">$\mathit{QMA}$</span> are contained in the Polynomial Hierarchy at all.</p>
<p>Would a (hypothetical) proof of <span class="math-container">$\mathit{NP}=\mathit{QMA}$</span> automatically imply <span class="math-container">$\mathit{BPP}=\mathit{BQP}$</span>? Or is it possible that <span class="math-container">$\mathit{NP}=\mathit{QMA}$</span> but <span class="math-container">$\mathit{BPP}\neq \mathit{BQP}$</span>?</p>
<p>I couldn't find much about it so any comments would be helpful.</p>

CC BY-SA 4.0
2022-03-04T17:57:15.120Z
@Turbo No. Assuming the unconditional proof that NP=QMA, what does that imply about the BPP vs BQP problem. Intuitively, I feel BQP should be equal to BPP in that case but I am not sure?
TheoryQuest1
CC BY-SA 4.0
2022-03-04T21:39:22.110Z
I suspect there is an oracle separation, i.e., an oracle $\mathcal O$ relative to which $BPP^{\mathcal O}\ne BQP^{\mathcal O}$ and $NP^{\mathcal O}=QMA^{\mathcal O}$. Therefore, if there is an implication, you will likely need non-relativizing techniques. In fact, you can probably obtain $BPP\subsetneq BQP=NP=QMA$ relative to some oracle.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-03-05T07:11:14.673Z
Thank you. But the way I am thinking is as follows: Since $NP=QMA$ the set of problems that the Quantum Computer can verify is the same as the set for classical TM. So in verification Quantum Gates do not offer any advantage over classical gates. And since $P$ is represents one deterministic path of a NDTM (which we know the TM should/would take) to solve the given problem, this combined with $QMA=NP$ would imply that in any such given path too, the QC does not offer any advantage. Where am I going wrong here?
TheoryQuest1
CC BY-SA 4.0
2022-03-05T07:23:23.827Z
@LieuweVinkhuijzen TheoryQuest1 does not want oracles. It was my comment too.
Turbo
CC BY-SA 4.0
2022-03-06T11:20:24.280Z
@TheoryQuest1 (1/2) That's a plausible line of reasoning. However, this line of reasoning talks only about paths that a TM might take, which means that your line of reasoning "_relativizes_". That is, such lines of reasoning hold also relative to all oracles. This is precisely why people look at oracle separations: in order to discover which conjectures can be proved with "only" ideas that relativize, versus which conjectures will require non-relativizing ideas.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-03-06T11:29:58.683Z
@TheoryQuest1 (2/3) So to answer your question "Where am I going wrong here?" You are not going wrong anywhere; it's just that, since this question requires non-relativizing techniques, and since we have so few non-relativizing techniques, there are therefore not many results that we can point to which support or refute your conjecture. Lastly, implications usually go "up", so e.g. $P=BQP\implies NP=NP^{BQP}$ holds; but your implication goes "down".
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-03-06T11:31:21.820Z
@TheoryQuest1 (3/3) I'm sorry I can't be of more help. Talking about oracles is just a way of saying "I can't be of more help, and here is why". You could ask the same question about $NP=MA\implies P=BPP?$, and the result would be the same: we don't know of any route which would prove this implication, because it requires non-relativizing techniques.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-03-06T14:02:34.860Z
@LieuweVinkhuijzen thank you. I understand. That is why I wanted to avoid oracle results :) So I guess as of now we can summarize the implies part with 'either of the two i.e. $BQP=BPP$ or $BQP\neq BPP$ is still possible' so no concrete implications of the result on this question are known.
TheoryQuest1
<cc.complexity-theory><quantum-computing>
$NP=QMA$'s impact on $BPP$ vs $BQP$ problem
TheoryQuest1
# $NP=QMA$'s impact on $BPP$ vs $BQP$ problem

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

$\mathit{BPP}$ vs $\mathit{NP}$ and $\mathit{BQP}$ vs $\mathit{QMA}$ are two problems that are (in spirit, for classical and quantum computers respectively) similar and both are open. Moreover, we don't have any idea if $\mathit{BQP}$ and $\mathit{QMA}$ are contained in the Polynomial Hierarchy at all.

Would a (hypothetical) proof of $\mathit{NP}=\mathit{QMA}$ automatically imply $\mathit{BPP}=\mathit{BQP}$? Or is it possible that $\mathit{NP}=\mathit{QMA}$ but $\mathit{BPP}\neq \mathit{BQP}$?

I couldn't find much about it so any comments would be helpful.

**Tags:** cc.complexity-theory, quantum-computing
> **Comments:**
> **username_0**: @Turbo No. Assuming the unconditional proof that NP=QMA, what does that imply about the BPP vs BQP problem. Intuitively, I feel BQP should be equal to BPP in that case but I am not sure?  
> **username_1**: I suspect there is an oracle separation, i.e., an oracle $\mathcal O$ relative to which $BPP^{\mathcal O}\ne BQP^{\mathcal O}$ and $NP^{\mathcal O}=QMA^{\mathcal O}$. Therefore, if there is an implication, you will likely need non-relativizing techniques. In fact, you can probably obtain $BPP\subsetneq BQP=NP=QMA$ relative to some oracle.  
> **username_0**: Thank you. But the way I am thinking is as follows: Since $NP=QMA$ the set of problems that the Quantum Computer can verify is the same as the set for classical TM. So in verification Quantum Gates do not offer any advantage over classical gates. And since $P$ is represents one deterministic path of a NDTM (which we know the TM should/would take) to solve the given problem, this combined with $QMA=NP$ would imply that in any such given path too, the QC does not offer any advantage. Where am I going wrong here?  
> **username_2**: @LieuweVinkhuijzen TheoryQuest1 does not want oracles. It was my comment too.  
> **username_1**: @TheoryQuest1 (1/2) That's a plausible line of reasoning. However, this line of reasoning talks only about paths that a TM might take, which means that your line of reasoning "_relativizes_". That is, such lines of reasoning hold also relative to all oracles. This is precisely why people look at oracle separations: in order to discover which conjectures can be proved with "only" ideas that relativize, versus which conjectures will require non-relativizing ideas.  
> **username_1**: @TheoryQuest1 (2/3) So to answer your question "Where am I going wrong here?" You are not going wrong anywhere; it's just that, since this question requires non-relativizing techniques, and since we have so few non-relativizing techniques, there are therefore not many results that we can point to which support or refute your conjecture. Lastly, implications usually go "up", so e.g. $P=BQP\implies NP=NP^{BQP}$ holds; but your implication goes "down".  
> **username_1**: @TheoryQuest1 (3/3) I'm sorry I can't be of more help. Talking about oracles is just a way of saying "I can't be of more help, and here is why". You could ask the same question about $NP=MA\implies P=BPP?$, and the result would be the same: we don't know of any route which would prove this implication, because it requires non-relativizing techniques.  
> **username_0**: @LieuweVinkhuijzen thank you. I understand. That is why I wanted to avoid oracle results :) So I guess as of now we can summarize the implies part with 'either of the two i.e. $BQP=BPP$ or $BQP\neq BPP$ is still possible' so no concrete implications of the result on this question are known.  

---

## 0 answers

