4

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.

108_mk
  • 225
  • 2
  • 6
  • 3
    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 Mar 19 '24 at 14:42
  • @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. – 108_mk Mar 20 '24 at 02:43

0 Answers0