Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly /spl sube/ PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state " that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP /spl nsub/ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly /spl sube/ PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state " that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP /spl nsub/ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.
Abstract: Although a quantum state requires exponentially many classical bits to de-scribe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state ” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Un-derlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP 6 ⊂ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quan-tum one-way communication complexity. Using this method, we obtain optimal quantum
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP⊂BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).
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).
Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by k separate polynomial-time verifiers, for arbitrary polynomial k. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.
We show two results about the relationship between quantum and classical messages. Our first contribution is to show how to replace a quantum message in a one-way communication protocol by a deterministic message, establishing that for all partial Boolean functions f:{0,1}n×{0,1}m→{0,1} we have DA→B(f)≤O(QA→B,∗(f)⋅m). This bound was previously known for total functions, while for partial functions this improves on results by Aaronson, in which either a log-factor on the right hand is present, or the left hand side is RA→B(f), and in which also no entanglement is allowed. In our second contribution we investigate the power of quantum proofs over classical proofs. We give the first example of a scenario, where quantum proofs lead to exponential savings in computing a Boolean function. The previously only known separation between the power of quantum and classical proofs is in a setting where the input is also quantum. We exhibit a partial Boolean function f, such that there is a one-way quantum communication protocol receiving a quantum proof (i.e., a protocol of type QMA) that has cost O(logn) for f, whereas every one-way quantum protocol for f receiving a classical proof (protocol of type QCMA) requires communication Ω(n/logn).
In this paper the Nečiporuk method for proving lower bounds on the size of Boolean formulas is reformulated in terms of one-way communication complexity. We investigate the settings of probabilistic formulas, nondeterministic formulas, and quantum formulas. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. The main results regarding formula size are as follows: We show a polynomial size gap between probabilistic/quantum and deterministic formulas, a near-quadratic gap between the sizes of nondeterministic formulas with limited access to nondeterministic bits and nondeterministic formulas with access to slightly more such bits, and a near-quadratic lower bound on quantum formula size. Furthermore we give a polynomial separation between the sizes of quantum formulas with and without multiple read random inputs. The lower bound methods for quantum and probabilistic formulas employ a variant of the Nečiporuk bound in terms of the Vapnik–Chervonenkis dimension. To establish our lower bounds we show optimal separations between one-way and two-way protocols for limited nondeterministic and quantum communication complexity, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.