<p>This question has been motivated by the existence of an ongoing (and possibly long-term) program for <span class="math-container">$P\neq NP$</span> conjecture like <a href="https://doi.org/10.1145/1944345.1944346" rel="nofollow noreferrer">GCT</a>(Mulmuley, 1999).</p>
<ul>
<li>Usually, such programs are marked by long and short-term goals. (see <a href="https://dl.acm.org/doi/pdf/10.1145/1562164.1562186" rel="nofollow noreferrer">Fortnow review article</a>)</li>
<li>A 'decent' number of people recognise the program's viability.</li>
</ul>
<blockquote>
<p>Is there a similar program for <span class="math-container">$P$</span> vs <span class="math-container">$BQP$</span> problem?</p>
</blockquote>
<p>A natural (to think) approach is to search for quantum analogous to Adelman's theorem. <a href="https://cstheory.stackexchange.com/q/15066/68722">(see Aaronson's answer)</a>. Informally, it is a search for 'pooling the quantumness trick'.</p>
<p>Are there any other relevant developments related to this problem?</p>
<p>Please note: this question is concerned with the existence of strategies to separate the classes rather than just looking for supporting evidence for <span class="math-container">$P\neq BQP$</span> as discussed <a href="https://cstheory.stackexchange.com/q/32817/68722">here</a>.</p>

CC BY-SA 4.0
2024-03-19T14:42:23.300Z
If you showed P ≠ BQP, you would show P ≠ PSPACE. The only "program" I know for showing this is Mulmuley's, so it seems unlikely anybody has come up with a plausible program to show P ≠ BQP.
Peter Shor 
CC BY-SA 4.0
2024-03-20T02:43:41.943Z
@PeterShor, point taken. // just curious to know the viability of an attempt to resolve P vs BQP using maths machinery/notions coming out of GCT. To be precise, a (quantum) analogues problem to permanent-determinant dichotomy. And then developing/implementing maths for it.
Manish Kumar
<cc.complexity-theory><complexity-classes><quantum-computing><open-problem>
Is there a 'mathematical program' to separate P from BQP?
Manish Kumar
# Is there a 'mathematical program' to separate P from BQP?

(Asked by: username_0 on 2024-03-12)

This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like [GCT](https://doi.org/10.1145/1944345.1944346)(Mulmuley, 1999).

* Usually, such programs are marked by long and short-term goals. (see [Fortnow review article](https://dl.acm.org/doi/pdf/10.1145/1562164.1562186))
* A 'decent' number of people recognise the program's viability.

> Is there a similar program for $P$ vs $BQP$ problem?

A natural (to think) approach is to search for quantum analogous to Adelman's theorem. [(see Aaronson's answer)](https://cstheory.stackexchange.com/q/15066/68722). Informally, it is a search for 'pooling the quantumness trick'.

Are there any other relevant developments related to this problem?

Please note: this question is concerned with the existence of strategies to separate the classes rather than just looking for supporting evidence for $P\neq BQP$ as discussed [here](https://cstheory.stackexchange.com/q/32817/68722).

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, open-problem
> **Comments:**
> **username_1**: If you showed P ≠ BQP, you would show P ≠ PSPACE. The only "program" I know for showing this is Mulmuley's, so it seems unlikely anybody has come up with a plausible program to show P ≠ BQP.  
> **username_0**: @PeterShor, point taken. // just curious to know the viability of an attempt to resolve P vs BQP using maths machinery/notions coming out of GCT. To be precise, a (quantum) analogues problem to permanent-determinant dichotomy. And then developing/implementing maths for it.  

---

## 0 answers

