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