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/ FP/poly - that is, Adleman s Theorem fails for relational problems - unless PSPACE NP/poly. Our proof uses IP = PSPACE and time-bounded Kolmogorov complexity. On the other hand, we show that proving FBPP/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).

, , , ,
doi.org/10.4230/LIPIcs.ITCS.2024.1
Leibniz International Proceedings in Informatics (LIPIcs)
Quantum Software Consortium , Networks
15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
,
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Aaronson, S., Buhrman, H., & Kretschmer, W. (2024). A qubit, a coin, and an advice string walk into a relational problem. In Innovations in Theoretical Computer Science Conference (pp. 1:1–1:24). doi:10.4230/LIPIcs.ITCS.2024.1