Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-015 | 21st November 2023 05:54

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

RSS-Feed




Revision #1
Authors: Scott Aaronson, Harry Buhrman, William Kretschmer
Accepted on: 21st November 2023 05:54
Downloads: 32
Keywords: 


Abstract:

Relational 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).



Changes to previous version:

Minor corrections and writing improvements.


Paper:

TR23-015 | 20th February 2023 23:24

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem


Abstract:

Relational 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).



ISSN 1433-8092 | Imprint