Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with relational problems:
TR23-015 | 20th February 2023
Scott Aaronson, Harry Buhrman, William Kretschmer

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

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint