This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999).

  • Usually, such programs are marked by long and short-term goals. (see Fortnow review article)
  • 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). 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.

  • 3
    $\begingroup$ 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. $\endgroup$ Mar 19 at 14:42
  • $\begingroup$ @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. $\endgroup$
    – 108_mk
    Mar 20 at 2:43


Your Answer

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