ECCC-Report TR23-015https://eccc.weizmann.ac.il/report/2023/015Comments and Revisions published for TR23-015en-usTue, 21 Nov 2023 05:54:28 +0200
Revision 1
| A Qubit, a Coin, and an Advice String Walk Into a Relational Problem |
Scott Aaronson,
Harry Buhrman,
William Kretschmer
https://eccc.weizmann.ac.il/report/2023/015#revision1Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for deterministic and randomized computation (FP, FBPP) and advice (/poly, /rpoly).
Our first result is that FBQP/qpoly != FBQP/poly, unconditionally, with no oracle---a striking contrast with what we know about the analogous decision classes. The proof repurposes the separation between quantum and classical one-way communication complexities due to Bar-Yossef, Jayram, and Kerenidis. We discuss how this separation raises the prospect of near-term experiments to demonstrate "quantum information supremacy," a form of quantum supremacy that would not depend on unproved complexity assumptions.
Our second result is that FBPP is not contained in FP/poly---that is, Adleman's Theorem fails for relational problems---unless PSPACE is contained in NP/poly. Our proof uses IP=PSPACE and time-bounded Kolmogorov complexity. On the other hand, we show that proving FBPP not in FP/poly will be hard, as it implies a superpolynomial circuit lower bound for PromiseBPEXP.
We prove the following further results:
* Unconditionally, FP != FBPP and FP/poly != FBPP/poly (even when these classes are carefully defined).
* FBPP/poly = FBPP/rpoly (and likewise for FBQP). For sampling problems, by contrast, SampBPP/poly != SampBPP/rpoly (and likewise for SampBQP).Tue, 21 Nov 2023 05:54:28 +0200https://eccc.weizmann.ac.il/report/2023/015#revision1
Paper TR23-015
| A Qubit, a Coin, and an Advice String Walk Into a Relational Problem |
Scott Aaronson,
Harry Buhrman,
William Kretschmer
https://eccc.weizmann.ac.il/report/2023/015Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for deterministic and randomized computation (FP, FBPP) and advice (/poly, /rpoly).
Our first result is that FBQP/qpoly != FBQP/poly, unconditionally, with no oracle---a striking contrast with what we know about the analogous decision classes. The proof repurposes the separation between quantum and classical one-way communication complexities due to Bar-Yossef, Jayram, and Kerenidis. We discuss how this separation raises the prospect of near-term experiments to demonstrate "quantum information supremacy," a form of quantum supremacy that would not depend on unproved complexity assumptions.
Our second result is that FBPP is not contained in FP/poly---that is, Adleman's Theorem fails for relational problems---unless PSPACE is contained in NP/poly. Our proof uses IP=PSPACE and time-bounded Kolmogorov complexity. On the other hand, we show that proving FBPP not in FP/poly will be hard, as it implies a superpolynomial circuit lower bound for PromiseBPEXP.
We prove the following further results:
* Unconditionally, FP != FBPP and FP/poly != FBPP/poly (even when these classes are carefully defined).
* FBPP/poly = FBPP/rpoly (and likewise for FBQP). For sampling problems, by contrast, SampBPP/poly != SampBPP/rpoly (and likewise for SampBQP).Mon, 20 Feb 2023 23:25:19 +0200https://eccc.weizmann.ac.il/report/2023/015