Theory of Computing, Volume 1 (2005), pp. 1–28 http://theoryofcomputing.org

Limitations of Quantum Advice and One-Way Communication

Scott Aaronson^{∗}

Received: June 29, 2004; published: February 9, 2005.

Abstract: 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

∗Work supported by an NSF Graduate Fellowship.

ACM Classification: F.1.2, F.1.3

AMS Classification: 81P68, 81P05, 68Q10, 68Q15, 42A05

Key words and phrases: quantum computation, advice, relativized complexity, direct product theorem, nonuniform, BQP, PP, communication, polynomial method, oracle

Authors retain copyright to their papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article is permitted as long as the author(s) and the journal are properly acknowledged. For the detailed

copyright statement, see http://theoryofcomputing.org/copyright.html.

\begin{matrix}c \\ ◯ \end{matrix} 2005 Scott Aaronson

Scott Aaronson

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

1 Introduction

How many classical bits can “really” be encoded into n qubits? Is it n, because of Holevo’s Theorem [19]; 2n, because of dense quantum coding [13] and quantum teleportation [9]; exponentially many, because of quantum fingerprinting [12]; or infinitely many, because amplitudes are continuous? The best general answer to this question is probably mu, the Zen word that “unasks” a question.^{1}

To a computer scientist, however, it is natural to formalize the question in terms of quantum one-way communication complexity [6, 12, 20, 40]. The setting is as follows: Alice has an n-bit string x, Bob has an m-bit string y, and together they wish to evaluate f (x,y)where f : {0,1}^{n}× {0,1}^{m}→ {0,1} is a Boolean function. After examining her input x = x_{1}...x_{n}, Alice can send a single quantum message ρ_{x} to Bob, whereupon Bob, after examining his input y = y_{1}...y_{m}, can choose some basis in which to measure ρ_{x}. He must then output a claimed value for f (x,y). We are interested in how long Alice’s message needs to be, for Bob to succeed with high probability on any x,y pair. Ideally the length will be much smaller than if Alice had to send a classical message.

Communication complexity questions have been intensively studied in theoretical computer science (see the book of Kushilevitz and Nisan [23] for example). In both the classical and quantum cases, though, most attention has focused on two-way communication, meaning that Alice and Bob get to send messages back and forth. We believe that the study of one-way quantum communication presents two main advantages. First, many open problems about two-way communication look gruesomely difficult—for example, are the randomized and quantum communication complexities of every total Boolean function polynomially related? We might gain insight into these problems by tackling their one-way analogues first. And second, because of its greater simplicity, the one-way model more directly addresses our opening question: how much “useful stuff” can be packed into a quantum state? Thus, results on one-way communication fall into the quantum information theory tradition initiated by Holevo [19] and others, as much as the communication complexity tradition initiated by Yao [38].

Related to quantum one-way communication is the notion of quantum advice. As pointed out by Nielsen and Chuang [28, p.203], there is no compelling physical reason to assume that the starting state of a quantum computer is a computational basis state:^{2}

[W]e know that many systems in Nature ‘prefer’ to sit in highly entangled states of many systems; might it be possible to exploit this preference to obtain extra computational power?

1Another mu-worthy question is, “Where does the power of quantum computing come from? Superposition? Interference?

The large size of Hilbert space?”

2One might object that the starting state is itself the outcome of some computational process, which began no earlier than the Big Bang. However, (1) for all we know highly entangled states were created in the Big Bang, and (2) 14 billion years is a long time.

Theory of Computing, Volume 1 (2005), pp. 1–28 2

Limitations of Quantum Advice and One-way Communication

It might be that having access to certain states allows particular computations to be done much more easily than if we are constrained to start in the computational basis.

One way to interpret Nielsen and Chuang’s provocative question is as follows. Suppose we could request the best possible starting state for a quantum computer, knowing the language to be decided and the input length n but not knowing the input itself.^{3} Denote the class of languages that we could then decide by BQP/qpoly—meaning quantum polynomial time, given an arbitrarily-entangled but polynomialsize quantum advice state.^{4} How powerful is this class? If BQP/qpoly contained (for example) the NP-complete problems, then we would need to rethink our most basic assumptions about the power of quantum computing. We will see later that quantum advice is closely related to quantum one-way communication, since we can think of an advice state as a one-way message sent to an algorithm by a benevolent “advisor.”

This paper is about the limitations of quantum advice and one-way communication. It presents three contributions which are basically independent of one another.

First, Section 3 shows that D^{1}(f) = O(mQ_{2}^{1}(f) logQ_{2}^{1}(f))for any Boolean function f, partial or total. Here D^{1}(f) is deterministic one-way communication complexity, Q_{2}^{1}(f) is bounded-error oneway quantum communication complexity, and m is the length of Bob’s input. Intuitively, whenever the set of Bob’s possible inputs is not too large, Alice can send him a short classical message that lets him learn the outcome of any measurement he would have wanted to make on the quantum message ρ_{x}. It is interesting that a slightly tighter bound for total functions—D^{1}(f) = O(mQ_{2}^{1}(f))—follows easily from a result of Klauck [20] together with a lemma of Sauer [34] about VC-dimension. However, the proof of the latter bound is highly nonconstructive, and seems to fail for partial f.

Using our communication complexity result, in Section 3.1 we show that BQP/qpoly ⊆ PP/poly— in other words, BQP with polynomial-size quantum advice can be simulated in PP with polynomial-size classical advice.^{5} This resolves a question of Harry Buhrman (personal communication), who asked whether quantum advice can be simulated in any classical complexity class with short classical advice. A corollary of our containment is that we cannot hope to show an unrelativized separation between quantum and classical advice (that is, that BQP/poly ≠ BQP/qpoly), without also showing that PP does not have polynomial-size circuits.

What makes this result surprising is that, in the minds of many computer scientists, a quantum state is basically an exponentially long vector. Indeed, this belief seems to fuel skepticism of quantum computing (see Goldreich [17] for example). But given an exponentially long advice string, even a classical computer could decide any language whatsoever. So one might imagine naïvely that quantum advice would let us solve problems that are not even recursively enumerable given classical advice of a similar size! The failure of this naïve intuition supports the view that a quantum superposition over n-bit strings is “more similar” to a probability distribution over n-bit strings than to a 2^{n}-bit string.

3If we knew the input, we would simply request a starting state that contains the right answer!

4BQP/qpoly might remind readers of a better-studied class called QMA (Quantum Merlin-Arthur). But there are two key differences: first, advice can be trusted while proofs cannot; second, proofs can be tailored to a particular input while advice cannot.

5Here PP is Probabilistic Polynomial-Time, or the class of languages for which there exists a polynomial-time classical randomized algorithm that accepts with probability greater than 1/2 if and only if an input x is in the language. Also, given a complexity class C, the class C/poly consists of all languages decidable by a C machine, given a polynomial-size classical advice string that depends only on the input length. See www.complexityzoo.com for more information about standard complexity classes mentioned in this paper.

Theory of Computing, Volume 1 (2005), pp. 1–28 3

Our second contribution, in Section 4, is an oracle relative to which NP is not contained in BQP/qpoly. Underlying this oracle separation is the first correct proof of a direct product theorem for quantum search. Given an N-item database with K marked items, the direct product theorem says that if a quantum algorithm makes o(\sqrt{N}) queries, then the probability that the algorithm finds all K of the marked items decreases exponentially in K. Notice that such a result does not follow from any existing quantum lower bound. Earlier Klauck [21] claimed a weaker direct product theorem, based on the hybrid method of Bennett et al. [8], in a paper on quantum time-space tradeoffs for sorting. Unfortunately, Klauck’s proof contained a bug. Our proof uses the polynomial method of Beals et al. [7], with the novel twist that we examine all higher derivatives of a polynomial (not just the first derivative). Our proof has already been improved by Klauck, Špalek, and de Wolf [22], who were able to recover and even extend Klauck’s original results about quantum sorting.

Our final contribution, in Section 5, is a new trace distance method for proving lower bounds on quantum one-way communication complexity. Previously there was only one basic lower bound technique: the VC-dimension method of Klauck [20], which relied on lower bounds for quantum random access codes due to Ambainis et al. [5] and Nayak [27]. Using VC-dimension one can show, for example, that Q_{2}^{1}(DISJ) = Ω(n), where the disjointness function DISJ: {0,1}^{n}× {0,1}^{n} → {0,1} is defined by DISJ(x,y)= 1 if and only if x_{i}y_{i} = 0 for all i ∈ {1,...,n}.

For some problems, however, the VC-dimension method yields no nontrivial quantum lower bound. Seeking to make this point vividly, Ambainis posed the following problem. Alice is given two elements x,y of a finite field 𝔽_{p} (where p is prime); Bob is given another two elements a,b ∈ 𝔽_{p}. Bob’s goal is to output 1 if y ≡ ax + b(modp) and 0 otherwise. For this problem, the VC-dimension method yields no randomized or quantum lower bound better than constant. On the other hand, the well-known fingerprinting protocol for the equality function [31] seems to fail for Ambainis’ problem, because of the interplay between addition and multiplication. So it is natural to conjecture that the randomized and even quantum one-way complexities are Θ(logp)—that is, that no nontrivial protocol exists for this problem.

Ambainis posed a second problem in the same spirit. Here Alice is given x ∈ {1,...,N}, Bob is given y ∈ {1,...,N}, and both players know a subset S ⊂ {1,...,N}. Bob’s goal is to decide whether x−y ∈ S where subtraction is modulo N. The conjecture is that if S is chosen uniformly at random with |S| about \sqrt{N}, then with high probability the randomized and quantum one-way complexities are both Θ(logN).

Using our trace distance method, we are able to show optimal quantum lower bounds for both of Ambainis’ problems. Previously, no nontrivial lower bounds were known even for randomized protocols. The key idea is to consider two probability distributions over Alice’s quantum message ρ_{x}. The first distribution corresponds to x chosen uniformly at random; the second corresponds to x chosen uniformly conditioned on f (x,y)= 1. These distributions give rise to two mixed states ρ and ρ_{y}, which Bob must be able to distinguish with non-negligible bias assuming he can evaluate f (x,y). We then show an upper bound on the trace distance ∥ρ − ρ_{y}∥ _{tr}, which implies that Bob cannot distinguish the distributions.

Theorem 5.1 gives a very general condition under which our trace distance method works; Corollaries 5.2 and 5.3 then show that the condition is satisfied for Ambainis’ two problems. Besides showing a significant limitation of the VC-dimension method, we hope our new method is a non-negligible step towards proving that R_{2}^{1}(f) = O(Q_{2}^{1}(f)) for all total Boolean functions f, where R_{2}^{1}(f) is randomized one-way complexity. We conclude in Section 6 with some open problems.

This paper is a moderately revised version of an extended abstract that appeared in CCC 2004 [2]. The proofs of Theorems 3.4, 3.5, 5.1, 5.2, and 5.4 have been written out in more detail; and discussions have been added to Sections 2.2 and 3.1, about the group membership problem and the class PQP/qpoly respectively. Also, an error has been fixed in Section 4: the direct product theorem in [2] based on Bernstein’s inequality is incorrect. Fortunately, the easier version based on V. A. Markov’s inequality is still perfectly sufficient to show NP ⊄ BQP/qpoly relative to an oracle; and in any case, the Bernstein’s version has been superseded by the results of Klauck, Špalek, and de Wolf [22].

2 Preliminaries

This section reviews basic definitions and results about quantum one-way communication (in Section 2.1) and quantum advice (in Section 2.2); then Section 2.3 proves a quantum information lemma that will be used throughout the paper.

2.1 Quantum One-Way Communication

Following standard conventions, we denote by D^{1}(f) the deterministic one-way complexity of f, or the minimum number of bits that Alice must send if her message is a function of x. Also, R_{2}^{1}(f), the bounded-error randomized one-way complexity, is the minimum k such that for every x,y, if Alice sends Bob a k-bit message drawn from some distribution 𝒟_{x}, then Bob can output a bit a such that a = f (x,y) with probability at least 2/3. (The subscript 2 means that the error is two-sided.) The zero-error randomized complexity R_{0}^{1}(f) is similar, except that Bob’s answer can never be wrong: he must output f (x,y)with probability at least 1/2 and otherwise declare failure.

The bounded-error quantum one-way complexity Q_{2}^{1}(f) is the minimum k such that, if Alice sends Bob a mixed state ρ_{x} of k qubits, there exists a joint measurement of ρ_{x} and y enabling Bob to output an a such that a = f (x,y)with probability at least 2/3. The zero-error and exact complexities Q_{0}^{1}(f) and Q_{E}^{1}(f) are defined analogously. Requiring Alice’s message to be a pure state would increase these complexities by at most a factor of 2, since by Kraus’ Theorem, every k-qubit mixed state can be realized as half of a 2k-qubit pure state. (Winter [37] has shown that this factor of 2 is tight.) See Klauck [20] for more detailed definitions of quantum and classical one-way communication complexity measures.

It is immediate that D^{1}(f) ≥ R_{0}^{1}(f) ≥ R_{2}^{1}(f) ≥ Q_{2}^{1}(f), that R_{0}^{1}(f) ≥ Q_{0}^{1}(f) ≥ Q_{2}^{1}(f), and that D^{1}(f) ≥ Q_{E}^{1}(f). Also, for total f, Duriš et al. [14] showed that R_{0}^{1}(f) = Θ(D^{1}(f)), while Klauck [20] showed that Q_{E}^{1}(f) = D^{1}(f) and that Q_{0}^{1}(f) = Θ(D^{1}(f)). In other words, randomized and quantum messages yield no improvement for total functions if we are unwilling to tolerate a bounded probability of error. This remains true even if Alice and Bob share arbitrarily many EPR pairs [20]. As is often the case, the situation is dramatically different for partial functions: there it is easy to see that R_{0}^{1}(f) can be constant even though D^{1}(f) = Ω(n): let f (x,y)= 1 if x_{1}y_{1} + ··· + x_{n/2}y_{n/2} ≥ n/4 and x_{n/2+1} y_{n/2+1} +··· +x_{n}y_{n} = 0 and f (x,y)= 0 if x_{1}y_{1}+··· +x_{n/2}y_{n/2} = 0 and x_{n/2+1} y_{n/2+1} +··· +x_{n}y_{n} ≥ n/4, promised that one of these is the case.

Moreover, Bar-Yossef, Jayram, and Kerenidis [6] have almost shown that Q_{E}^{1}(f) can be exponentially smaller than R_{2}^{1}(f). In particular, they proved that separation for a relation, meaning a problem for which Bob has many possible valid outputs. For a partial function f based on their relation, they also showed that Q_{E}^{1}(f) = Θ(logn)whereas R_{0}^{1}(f) = Θ(\sqrt{n}); and they conjectured (but did not prove) that R_{2}^{1}(f) = Θ(\sqrt{n}).

2.2 Quantum Advice

Informally, BQP/qpoly is the class of languages decidable in polynomial time on a quantum computer, given a polynomial-size quantum advice state that depends only on the input length. We now make the definition more formal.

Definition 2.1. A language L is in BQP/qpoly if there exists a polynomial-size quantum circuit family {C_{n}}_{n≥1} , and a polynomial-size family of quantum states {|ψ_{n}⟩}_{n≥1} , such that for all x ∈ {0,1}^{n},

(i) If x ∈ L then q(x)≥ 2/3, where q(x) is the probability that the first qubit is measured to be |1⟩, after C_{n} is applied to the starting state |x⟩⊗ |0··· 0⟩⊗ |ψ_{n}⟩.

(ii) If x ∉ L then q(x)≤ 1/3.^{6}

The central open question about BQP/qpoly is whether it equals BQP/poly, or BQP with polynomialsize classical advice. We do have a candidate for an oracle problem separating the two classes: the group membership problem of Watrous [36], which we describe for completeness. Let G_{n} be a black box group^{7} whose elements are uniquely labeled by n-bit strings, and let H_{n} be a subgroup of G_{n}. Both G_{n} and H_{n} depend only on the input length n, so we can assume that a nonuniform algorithm knows generating sets for both of them. Given an element x ∈ G_{n} as input, the problem is to decide whether x ∈ H_{n}.

If G_{n} is “sufficiently nonabelian” and H_{n} is exponentially large, we do not know how to solve this problem in BQP or even BQP/poly. On the other hand, we can solve it in BQP/qpoly as follows. Let our quantum advice state be an equal superposition over all elements of H_{n}:

|H_{n}⟩= \frac{1}{\sqrt{|H_{n}|}} ∑_{y∈H_{n}}|y⟩

We can transform |H_{n}⟩into

|xH_{n}⟩= \frac{1}{\sqrt{|H_{n}|}} ∑_{y∈H_{n}}|xy⟩

6If the starting state is |x⟩⊗ |0··· 0⟩⊗ |φ⟩ for some |φ⟩ ≠ |ψ_{n}⟩, then we do not require the acceptance probability to lie in [0,1/3]∪[2/3,1]. Therefore, what we call BQP/qpoly corresponds to what Nishimura and Yamakami [30] call BQP/^{∗}Qpoly.

Also, it does not matter whether the circuit family {C_{n}}_{n≥1} is uniform, since we are giving it advice anyway.

7In other words, we have a quantum oracle available that given x,y ∈ G_{n} outputs xy (i.e. exclusive-OR’s xy into an answer register), and that given x ∈ G_{n} outputs x^{−1} .

Theory of Computing, Volume 1 (2005), pp. 1–28 6

by mapping |y⟩|0⟩to |y⟩|xy⟩to |y ⊕ x^{−1} xy⟩|xy⟩= |0⟩|xy⟩for each y ∈ H_{n}. Our algorithm will first prepare the state (|0⟩|H_{n}⟩+ |1⟩|xH_{n}⟩) /\sqrt{2}, then apply a Hadamard gate to the first qubit, and finally measure the first qubit in the standard basis, in order to distinguish the cases |H_{n}⟩= |xH_{n}⟩and ⟨H_{n}|xH_{n}⟩= 0 with constant bias. The first case occurs whenever x ∈ H_{n}, and the second occurs whenever x ∉ H_{n}.

Although the group membership problem provides intriguing evidence for the power of quantum advice, we have no idea how to show that it is not also solvable using classical advice. Indeed, apart from a result of Nishimura and Yamakami [30] that EESPACE ⊄ BQP/qpoly, essentially nothing was known about the class BQP/qpoly before the present work.

2.3 The Almost As Good As New Lemma

The following simple lemma, which was implicit in [5], is used three times in this paper—in Theorems 3.4, 3.5, and 4.7. It says that, if the outcome of measuring a quantum state ρ could be predicted with near-certainty given knowledge of ρ, then measuring ρ will damage it only slightly. Recall that the trace distance ∥ρ − σ∥ _{tr} between two mixed states ρ and σ equals \frac{1}{2} ∑_{i}|λ_{i}|, where λ_{1},...,λ_{N} are the eigenvalues of ρ − σ.

Lemma 2.2. Suppose a 2-outcome measurement of a mixed state ρ yields outcome 0 with probability 1 − ε. Then after the measurement, we can recover a state ρ̃ such that ∥ρ̃ − ρ∥ _{tr}≤ \sqrt{ε}. This is true even if the measurement is a POVM (that is, involves arbitrarily many ancilla qubits).

Proof. Let |ψ⟩ be a purification of the entire system (ρ plus ancilla). We can represent any measurement as a unitary U applied to |ψ⟩, followed by a 1-qubit measurement. Let |φ_{0}⟩ and |φ_{1}⟩ be the two possible pure states after the measurement; then ⟨φ_{0}|φ_{1}⟩ = 0 and U |ψ⟩ = α |φ_{0}⟩+β |φ_{1}⟩ for some α,β such that |α|^{2} = 1 − ε and |β|^{2} = ε. Writing the measurement result as σ = (1 − ε) |φ_{0}⟩⟨φ_{0}| + ε |φ_{1}⟩⟨φ_{1}|, it is easy to show that

∥σ − U |ψ⟩⟨ψ| U^{−1} ∥_{tr}= \sqrt{ε (1 − ε)}.

So applying U^{−1} to σ,

∥U^{−1} σU − |ψ⟩⟨ψ| ∥_{tr}= \sqrt{ε (1 − ε)}.

Let ρ̃ be the restriction of U^{−1} σU to the original qubits of ρ. Theorem 9.2 of Nielsen and Chuang [28] shows that tracing out a subsystem never increases trace distance, so ∥ρ̃ − ρ∥ _{tr}≤ \sqrt{ε (1 − ε)} ≤ \sqrt{ε}.

3 Simulating Quantum Messages

Let f : {0,1}^{n}× {0,1}^{m} → {0,1} be a Boolean function. In this section we first combine existing results to obtain the relation D^{1}(f) = O(mQ_{2}^{1}(f))for total f, and then prove using a new method that D^{1}(f) = O(mQ_{2}^{1}(f) logQ_{2}^{1}(f))for all f (partial or total).

Define the communication matrix M_{f} to be a 2^{n}× 2^{m} matrix with f (x,y) in the x^{th} row and y^{th} column. Then letting rows(f) be the number of distinct rows in M_{f}, the following is immediate.

Proposition 3.1. For total f,

D^{1}(f) = ⌈log_{2}rows(f)⌉,
Q_{2}^{1}(f) = Ω(loglogrows(f)).

Also, let the VC-dimension VC(f) equal the maximum k for which there exists a 2^{n}× k submatrix M_{g} of M_{f} with rows(g) = 2^{k}. Then Klauck [20] observed the following, based on a lower bound for quantum random access codes due to Nayak [27].

Proposition 3.2 (Klauck). Q_{2}^{1}(f) = Ω(VC(f)) for total f.

Now let cols(f) be the number of distinct columns in M_{f}. Then Theorem 3.2 yields the following general lower bound:

Corllary 3.3. D^{1}(f) = O(mQ_{2}^{1}(f))for total f, where m is the size of Bob’s input.

Proof. It follows from a lemma of Sauer [34] that

rows(f) ≤ ∑_{i=0}^{VC(f)} \binom{cols(f)}{i} ≤ cols(f)^{VC(f)+1} .

Hence VC(f) ≥ log_{cols(f)} rows(f) − 1, so

Q_{2}^{1}(f) = Ω(VC(f)) = Ω( \begin{matrix}log & rows & (f) \\ log & cols & (f) \end{matrix} )

= Ω( \frac{D^{1}(f)}{m} ) .

In particular, D^{1}(f) and Q_{2}^{1}(f) are polynomially related for total f, whenever Bob’s input is polynomially smaller than Alice’s, and Alice’s input is not “padded.” More formally, D^{1}(f) = O( Q_{2}^{1}(f)^{1/(1−c)} ) whenever m = O(n^{c}) for some c < 1 and rows(f) = 2^{n} (i.e. all rows of M_{f} are distinct). For then D^{1}(f) = n by Theorem 3.1, and Q_{2}^{1}(f) = Ω(D^{1}(f) /n^{c})= Ω(n^{1−c} ) by Corollary 3.3.

We now give a new method for replacing quantum messages by classical ones when Bob’s input is small. Although the best bound we know how to obtain with this method—D^{1}(f) = O(mQ_{2}^{1}(f) logQ_{2}^{1}(f))— is slightly weaker than the D^{1}(f) = O(mQ_{2}^{1}(f))of Corollary 3.3, our method works for partial Boolean functions as well as total ones. It also yields a (relatively) efficient procedure by which Bob can reconstruct Alice’s quantum message, a fact we will exploit in Section 3.1 to show BQP/qpoly ⊆ PP/poly. By contrast, the method based on Sauer’s Lemma seems to be nonconstructive.

Theorem 3.4. D^{1}(f) = O(mQ_{2}^{1}(f) logQ_{2}^{1}(f))for all f (partial or total).

Proof. Let f : 𝒟 → {0,1} be a partial Boolean function with 𝒟 ⊆ {0,1}^{n}× {0,1}^{m}, and for all x ∈ {0,1}^{n}, let 𝒟_{x} = {y ∈ {0,1}^{m}: (x,y)∈ 𝒟}. Suppose Alice can send Bob a quantum state with Q_{2}^{1}(f) qubits, that enables him to compute f (x,y)for any y ∈ 𝒟_{x} with error probability at most 1/3. Then she can also send him a boosted state ρ with K = O(Q_{2}^{1}(f) logQ_{2}^{1}(f)) qubits, such that for all y ∈ 𝒟_{x},

|P_{y}(ρ)− f (x,y)| ≤ \frac{1}{Q_{2}^{1}(f)^{10}},

where P_{y}(ρ) is the probability that some measurement Λ[y]yields a ‘1’ outcome when applied to ρ. We can assume for simplicity that ρ is a pure state |ψ⟩⟨ψ|; as discussed in Section 2.1, this increases the message length by at most a factor of 2.

Let 𝒴 be any subset of 𝒟_{x} satisfying |𝒴| ≤ Q_{2}^{1}(f)^{2}. Then starting with ρ, Bob can measure Λ[y] for each y ∈ 𝒴 in lexicographic order, reusing the same message state again and again but uncomputing whatever garbage he generates while measuring. Let ρ_{t} be the state after the t^{th} measurement; thus ρ_{0} = ρ = |ψ⟩⟨ψ|. Since the probability that Bob outputs the wrong value of f (x,y)on any given y is at most 1/Q_{2}^{1}(f)^{10}, Lemma 2.2 implies that

∥ρ_{t}− ρ_{t−1}∥ _{tr}≤ \sqrt{\frac{1}{Q_{2}^{1}(f)^{10}}} = \frac{1}{Q_{2}^{1}(f)^{5}}.

Since trace distance satisfies the triangle inequality, this in turn implies that

∥ρ_{t}− ρ∥ _{tr}≤ \frac{t}{Q_{2}^{1}(f)^{5}} ≤ \frac{1}{Q_{2}^{1}(f)^{3}}.

Now imagine an “ideal scenario” in which ρ_{t} = ρ for every t; that is, the measurements do not damage ρ at all. Then the maximum bias with which Bob could distinguish the actual from the ideal scenario is

∥ρ_{0}− ρ∥ _{tr}+ ··· + ∥ρ_{|𝒴|−1} − ρ∥ _{tr}≤ \frac{|𝒴|}{Q_{2}^{1}(f)^{3}} ≤ \frac{1}{Q_{2}^{1}(f)}.

So by the union bound, Bob will output f (x,y)for every y ∈ 𝒴 simultaneously with probability at least

1 − \frac{|𝒴|}{Q_{2}^{1}(f)^{10}} − \frac{1}{Q_{2}^{1}(f)} ≥ 0.9

for sufficiently large Q_{2}^{1}(f).

Now imagine that the communication channel is blocked, so Bob has to guess what message Alice wants to send him. He does this by using the K-qubit maximally mixed state I in place of ρ. We can write I as

I = \frac{1}{2^{K}} ∑_{j=1}^{2^{K}} |ψ_{j}⟩ ⟨ψ_{j} | ,

where |ψ_{1}⟩,...,|ψ_{2^{K}}⟩ are orthonormal vectors such that |ψ_{1}⟩ = |ψ⟩. So if Bob uses the same procedure as above except with I instead of ρ, then for any 𝒴 ⊆ 𝒟_{x} with |𝒴| ≤ Q_{2}^{1}(f)^{2}, he will output f (x,y)for every y ∈ 𝒴 simultaneously with probability at least 0.9/2^{K}.

We now give the classical simulation of the quantum protocol. Alice’s message to Bob consists of T ≤ K inputs y_{1},...,y_{T} ∈ 𝒟_{x}, together with f (x,y_{1}),...,f (x,y_{T}).^{8} Thus the message length is mT + T = O(mQ_{2}^{1}(f) logQ_{2}^{1}(f)). Here are the semantics of Alice’s message: “Bob, suppose you looped over all y ∈ 𝒟_{x} in lexicographic order; and for each one, guessed that f (x,y)= round(P_{y}(I)), where round(p) is 1 if p ≥ 1/2 and 0 if p < 1/2. Then y_{1} is the first y for which you would guess the wrong value of f (x,y). In general, let I_{t} be the state obtained by starting from I and then measuring Λ[y_{1}],...,Λ[y_{t}]in that order, given that the outcomes of the measurements are f (x,y_{1}),...,f (x,y_{t})respectively. (Note that I_{t} is not changed by measurements of every y ∈ 𝒟_{x} up to y_{t}, only by measurements of y_{1},...,y_{t}.) If you looped over all y ∈ 𝒟_{x} in lexicographic order beginning from y_{t}, then y_{t+1} is the first y you would encounter for which round(P_{y}(I_{t}))≠ f (x,y).”

Given the sequence of y_{t}’s as defined above, it is obvious that Bob can compute f (x,y)for any y ∈ 𝒟_{x}. First, if y = y_{t} for some t, then he simply outputs f (x,y_{t}). Otherwise, let t^{∗} be the largest t for which y_{t} < y lexicographically. Then Bob prepares a classical description of the state I_{t^{∗}}—which he can do since he knows y_{1},...,y_{t^{∗}} and f (x,y_{1}),...,f (x,y_{t^{∗}})—and then outputs round(P_{y}(I_{t^{∗}}))as his claimed value of f (x,y). Notice that, although Alice uses her knowledge of 𝒟_{x} to prepare her message, Bob does not need to know 𝒟_{x} in order to interpret the message. That is why the simulation works for partial as well as total functions.

But why can we assume that the sequence of y_{t}’s stops at y_{T} for some T ≤ K? Suppose T > K; we will derive a contradiction. Let 𝒴 = {y_{1},...,y_{K+1}}. Then |𝒴| = K + 1 ≤ Q_{2}^{1}(f)^{2}, so we know from previous reasoning that if Bob starts with I and then measures Λ[y_{1}],...,Λ[y_{K+1}]in that order, he will observe f (x,y_{1}),...,f (x,y_{K+1})simultaneously with probability at least 0.9/2^{K}. But by the definition of y_{t}, the probability that Λ[y_{t}]yields the correct outcome is at most 1/2, conditioned on Λ[y_{1}],...,Λ[y_{t−1}] having yielded the correct outcomes. Therefore f (x,y_{1}),...,f (x,y_{K+1})are observed simultaneously with probability at most 1/2^{K+1} < 0.9/2^{K}, contradiction.

3.1 Simulating Quantum Advice

We now apply our new simulation method to upper-bound the power of quantum advice.

Theorem 3.5. BQP/qpoly ⊆ PP/poly.

Proof. For notational convenience, let L_{n}(x)= 1 if input x ∈ {0,1}^{n} is in language L, and L_{n}(x)= 0 otherwise. Suppose L_{n} is computed by a BQP machine using quantum advice of length p(n). We will give a PP machine that computes L_{n} using classical advice of length O(np(n)logp(n)). Because of the close connection between advice and one-way communication, the simulation method will be essentially identical to that of Theorem 3.4.

By using a boosted advice state on K = O(p(n)logp(n)) qubits, a polynomial-time quantum algorithm A can compute L_{n}(x) with error probability at most 1/p(n)^{10}. Now the classical advice to the PP machine consists of T ≤ K inputs x_{1},...,x_{T} ∈ {0,1}^{n}, together with L_{n}(x_{1}),...,L_{n}(x_{T}). Let I be the maximally mixed state on K qubits. Also, let P_{x}(ρ) be the probability that A outputs ‘1’ on input x, given ρ as its advice state. Then x_{1} is the lexicographically first input x for which round(P_{x}(I))≠ L_{n}(x). In general, let I_{t} be the state obtained by starting with I as the advice and then running A on x_{1},...,x_{t} in that order (uncomputing garbage along the way), if we postselect on A correctly outputting L_{n}(x_{1}),...,L_{n}(x_{t}). Then x_{t+1} is the lexicographically first x > x_{t} for which round(P_{x}(I_{t}))≠ L_{n}(x).

8Strictly speaking, Bob will be able to compute f (x,y_{1}),...,f (x,y_{T})for himself given y_{1},...,y_{T}; he does not need Alice to tell him the f values.

Theory of Computing, Volume 1 (2005), pp. 1–28 10

Given the classical advice, we can compute L_{n}(x)as follows: if x ∈ {x_{1},...,x_{T}}then output L_{n}(x_{t}). Otherwise let t^{∗} be the largest t for which x_{t}< x lexicographically, and output round(P_{x}(I_{t^{∗}})). The proof that this algorithm works is the same as in Theorem 3.4, and so is omitted for brevity. All we need to show is that the algorithm can be implemented in PP.

Adleman, DeMarrais, and Huang [4] (see also Fortnow and Rogers [16]) showed that BQP ⊆ PP, by using what physicists would call a “Feynman sum-over-histories.” Specifically, let C be a polynomialsize quantum circuit that starts in the all-0 state, and that consists solely of Toffoli and Hadamard gates (Shi [35] has shown that this gate set is universal). Also, let α_{z} be the amplitude of basis state |z⟩ after all gates in C have been applied. We can write α_{z} as a sum of exponentially many contributions, a_{1} + ··· + a_{N}, where each a_{i} is a rational real number computable in classical polynomial time. So by evaluating the sum

|α_{z}|^{2} = ∑_{i,j=1}^{N} a_{i}a_{j},

putting positive and negative terms on “opposite sides of the ledger,” a PP machine can check whether |α_{z}|^{2} > β for any rational constant β. It follows that a PP machine can also check whether

∑_{z : S_{1}(z)}|α_{z}|^{2} > ∑_{z : S_{0}(z)}|α_{z}|^{2}

(or equivalently, whether Pr[S_{1}]> Pr[S_{0}]) for any classical polynomial-time predicates S_{1} and S_{0}.

Now suppose the circuit C does the following, in the case x ∉ {x_{1},...,x_{T}}. It first prepares the K-qubit maximally mixed state I (as half of a 2K-qubit pure state), and then runs A on x_{1},...,x_{t^{∗}},x in that order, using I as its advice state. The claimed values of L_{n}(x_{1}),...,L_{n}(x_{t^{∗}}),L_{n}(x) are written to output registers but not measured. For i ∈ {0,1}, let the predicate S_{i}(z) hold if and only if basis state |z⟩contains the output sequence L_{n}(x_{1}),...,L_{n}(x_{t^{∗}}),i. Then it is not hard to see that

P_{x}(I_{t^{∗}})= \frac{Pr[S_{1}]}{Pr[S_{1}]+ Pr[S_{0}]} ,

so P_{x}(I_{t^{∗}})> 1/2 and hence L_{n}(x)= 1 if and only if Pr[S_{1}]> Pr[S_{0}]. Since the case x ∈ {x_{1},...,x_{T}}is trivial, this shows that L_{n}(x)is computable in PP/poly.

We make five remarks about Theorem 3.5. First, for the same reason that Theorem 3.4 works for partial as well as total functions, we actually obtain the stronger result that PromiseBQP/qpoly ⊆ PromisePP/poly, where PromiseBQP and PromisePP are the promise-problem versions of BQP and PP respectively.

Second, as pointed out to us by Lance Fortnow, a corollary of Theorem 3.5 is that we cannot hope to show an unrelativized separation between BQP/poly and BQP/qpoly, without also showing that PP does not have polynomial-size circuits. For BQP/poly ≠ BQP/qpoly clearly implies that P/poly ≠ PP/poly. But the latter then implies that PP ⊄ P/poly, since assuming PP ⊂ P/poly we could also obtain polynomial-size circuits for a language L ∈ PP/poly by defining a new language L′∈ PP, consisting of all (x,a) pairs such that the PP machine would accept x given advice string a. The reason this works is that PP is a syntactically defined class.

Third, an earlier version of this paper showed that BQP/qpoly ⊆ EXP/poly, by using a simulation in which an EXP machine keeps track of a subspace H of the advice Hilbert space to which the ‘true’ advice state must be close. In that simulation, the classical advice specifies inputs x_{1},...,x_{T} for which dim(H) is at least halved; the observation that dim(H) must be at least 1 by the end then implies that T ≤ K = O(p(n)logp(n)), meaning that the advice is of polynomial size. The huge improvement from EXP to PP came solely from working with measurement outcomes and their probabilities instead of with subspaces and their dimensions. We can compute the former using the same “Feynman sum-over-histories” that Adleman et al. [4] used to show BQP ⊆ PP, but could not see any way to compute the latter without explicitly storing and diagonalizing exponentially large matrices.

Fourth, assuming BQP/poly ≠ BQP/qpoly, Theorem 3.5 is almost the best result of its kind that one could hope for, since the only classes known to lie between BQP and PP and not known to equal either are obscure ones such as AWPP [16]. Initially the theorem seemed to us to prove something stronger, namely that BQP/qpoly ⊆ PostBQP/poly. Here PostBQP is the class of languages decidable by polynomial-size quantum circuits with postselection—meaning the ability to measure a qubit that has a nonzero probability of being |1⟩, and then assume that the measurement outcome will be |1⟩. Clearly PostBQP lies somewhere between BQP and PP; one can think of it as a quantum analogue of the classical complexity class BPP_{path} [18]. We have since shown, however, that PostBQP = PP [3].

Fifth, it is clear that Adleman et al.’s BQP ⊆ PP result [4] can be extended to show that PQP = PP. Here PQP is the quantum analogue of PP—that is, quantum polynomial time but where the probability of a correct answer need only be bounded above 1/2, rather than above 2/3. A reviewer asked whether Theorem 3.5 could similarly be extended to show that PQP/qpoly = PP/poly. The answer is no—for indeed, PQP/qpoly contains every language whatsoever! To see this, given any function L_{n}: {0,1}^{n} → {0,1}, let our quantum advice state be

|ψ_{n}⟩ = \frac{1}{2^{n/2}} ∑_{x∈\{0,1\}^{n}}|x⟩|L_{n}(x)⟩.

Then a PQP algorithm to compute L_{n} is as follows: given an input x ∈ {0,1}^{n}, first measure |ψ_{n}⟩ in the standard basis. If |x⟩|L_{n}(x)⟩is observed, output L_{n}(x); otherwise output a uniform random bit.

4 Oracle Limitations

Can quantum computers solve NP-complete problems in polynomial time? In the early days of quantum computing, Bennett et al. [8] gave an oracle relative to which NP ⊄ BQP, providing what is still the best evidence we have that the answer is no. It is easy to extend Bennett et al.’s result to give an oracle relative to which NP ⊄ BQP/poly; that is, NP is hard even for nonuniform quantum algorithms. But when we try to show NP ⊄ BQP/qpoly relative to an oracle, a new difficulty arises: even if the oracle encodes 2^{n} exponentially hard search problems for each input length n, the quantum advice, being an “exponentially large object” itself, might somehow encode information about all 2^{n} problems. We need to argue that even if so, only a miniscule fraction of that information can be extracted by measuring the advice.

How does one prove such a statement? As it turns out, the task can be reduced to proving a direct product theorem for quantum search. This is a theorem that in its weakest form says the following: given N items, K of which are marked, if we lack enough time to find even one marked item, then the probability of finding all K items decreases exponentially in K. For intuitively, suppose there were a quantum advice state that let us efficiently find any one of K marked items. Then by “guessing” the advice (i.e. replacing it by a maximally mixed state), and then using the guessed advice multiple times, we could efficiently find all K of the items with a success probability that our direct product theorem shows is impossible. This reduction is formalized in Theorem 4.7.

But what about the direct product theorem itself? It seems like it should be trivial to prove—for surely there are no devious correlations by which success in finding one marked item leads to success in finding all the others! So it is surprising that even a weak direct product theorem eluded proof for years. In 2001, Klauck [21] gave an attempted proof using the hybrid method of Bennett et al. [8]. His motivation was to show a limitation of space-bounded quantum sorting algorithms. Unfortunately, Klauck’s proof contained a bug.^{9}

In this section we give the first correct proof of a direct product theorem, based on the polynomial method of Beals et al. [7]. Besides showing that NP ⊄ BQP/qpoly relative to an oracle, our result can be used to recover the claims made in [21] about the hardness of quantum sorting (see Klauck, Špalek, and de Wolf [22] for details). We expect the result to have other applications as well.

We will need the following lemma of Beals et al. [7], which builds on ideas due to Minsky and Papert [26] and Nisan and Szegedy [29].

Lemma 4.1 (Beals et al.). Suppose a quantum algorithm makes T queries to an oracle string X ∈ {0,1}^{N}, and accepts with probability A(X). Then there exists a real polynomial p, of degree at most 2T, such that

p(i) = EX_{|X⊧i}[A(X)]

for all integers i ∈ {0,...,N}, where |X|denotes the Hamming weight of X.

Lemma 4.1 implies that, to lower-bound the number of queries T made by a quantum algorithm, it suffices to lower-bound deg(p), where p is a real polynomial representing the algorithm’s expected acceptance probability. As an example, any quantum algorithm that computes the ORfunction on N bits, with success probability at least 2/3, yields a polynomial p such that p(0) ∈ [0,1/3]and p(i) ∈ [2/3,1] for all integers i ∈ {1,...,N}. To lower-bound the degree of such a polynomial, one can use an inequality proved by A. A. Markov in 1890 ([24]; see also [32]):

Theorem 4.2 (A. A. Markov). Given a real polynomial p and constant N > 0, let r^{(0)} = max_{x∈[0,N]}|p(x)| and r^{(1)} = max_{x∈[0,N]}|p′(x)|. Then

deg(p) ≥ \sqrt{\frac{Nr^{(1)}}{2r^{(0)}}}.

9Specifically, the last sentence in the proof of Lemma 5 in [21] (“Clearly this probability is at least q_{x}(p_{x}− α) ”) is not justified by what precedes it.

Theory of Computing, Volume 1 (2005), pp. 1–28 13

Theorem 4.2 deals with the entire range [0,N], whereas in our setting p(x)is constrained only at the integer points x ∈ {0,...,N}. But as shown in [15, 29, 33], this is not a problem. For by elementary calculus, p(0) ≤ 1/3 and p(1) ≥ 2/3 imply that p′(x)≥ 1/3 for some real x ∈ [0,1], and therefore r^{(1)} ≥ 1/3. Furthermore, let x^{∗} be a point in [0,N]where |p(x^{∗})| = r^{(0)}. Then p(⌊x^{∗}⌋) ∈ [0,1] and p(⌈x^{∗}⌉) ∈ [0,1]imply that r^{(1)} ≥ 2(r^{(0)}− 1) . Thus

deg(p) ≥ \sqrt{\frac{Nr^{(1)}}{2r^{(0)}}} ≥ \sqrt{\frac{N max\{1/3,2(r^{(0)}− 1) \}}{2r^{(0)}}} = Ω( \sqrt{N}) .

This is the proof of Beals et al. [7] that quantum search requires Ω(\sqrt{N}) queries.

When proving a direct product theorem, we can no longer apply Theorem 4.2 so straightforwardly. The reason is that the success probabilities in question are extremely small, and therefore the maximum derivative r^{(1)} could also be extremely small. Fortunately, though, we can still prove a good lower bound on the degree of the relevant polynomial p. The key is to look not just at the first derivative of p, but at higher derivatives.

To start, we need a lemma about the behavior of functions under repeated differentiation.

Lemma 4.3. Let f : ℝ → ℝ be an infinitely differentiable function such that for some positive integer K, we have f (i) = 0 for all i ∈ {0,...,K − 1} and f (K)= δ > 0. Also, let r^{(m)}= max_{x∈[0,N]}|f^{(m)}(x)|, where f^{(m)}(x) is the m^{th} derivative of f evaluated at x (thus f^{(0)} = f). Then r^{(m)} ≥ δ/m! for all m ∈ {0,...,K}.

Proof. We claim, by induction on m, that there exist K − m + 1 points 0 ≤ x_{0}^{(m)}< ···< x_{K−m}^{(m)} ≤ K such that f^{(m)}( x_{i}^{(m)}) = 0 for all i ≤ K − m − 1 and f^{(m)}( x_{K−m}^{(m)}) ≥ δ/m!. If we define x_{i}^{(0)} = i, then the base case m = 0 is immediate from the conditions of the lemma. Suppose the claim is true for m; then by elementary calculus, for all i ≤ K − m − 2 there exists a point x_{i}^{(m+1)} ∈ ( x_{i}^{(m)},x_{i+1}^{(m)}) such that

f^{(m+1)} ( x_{i}^{(m+1)}) = 0. Notice that x_{i}^{(m+1)} ≥ x_{i}^{(m)} ≥ ···≥ x_{i}^{(0)} = i. So there is also a point x_{K−m−1}^{(m+1)} ∈

( x_{K−m−1}^{(m)} ,x_{K−m}^{(m)}) such that

f^{(m+1)} ( x_{K−m−1}^{(m+1)} ) ≥ \frac{f^{(m)}( x_{K−m}^{(m)}) − f^{(m)}( x_{K−m−1}^{(m)} )}{x_{K−m}^{(m)} − x_{K−m−1}^{(m)}}

≥ \frac{δ/m! − 0}{K − (K − m − 1)}

= \frac{δ}{(m + 1)!}.

With the help of Lemma 4.3, we can sometimes lower-bound the degree of a real polynomial even its first derivative is small throughout the region of interest. To do so, we use the following generalization of A. A. Markov’s inequality (Theorem 4.2), which was proved by A. A. Markov’s younger brother V. A. Markov in 1892 ([25]; see also [32]).

Theorem 4.4 (V. A. Markov). Given a real polynomial p of degree d and positive real number N, let r^{(m)}= max_{x∈[0,N]}|p^{(m)}(x)|. Then for all m ∈ {1,...,d},

r^{(m)}≤ ( \frac{2r^{(0)}}{N}) ^{m}T_{d}^{(m)}(1)

≤ ( \frac{2r^{(0)}}{N}) ^{m} \frac{d^{2}(d^{2}− 1^{2}) (d^{2}− 2^{2}) · ··· · ( d^{2}− (m − 1)^{2})}{1 · 3 · 5 · ··· · (2m − 1)}.

Here T_{d}(x)= cos(d arccosx)is the d^{th}Chebyshev polynomial of the first kind.

As we demonstrate below, combining Theorem 4.4 with Lemma 4.3 yields a lower bound on deg(p).

Lemma 4.5. Let p be a real polynomial such that

(i) p(x)∈ [0,1]at all integer points x ∈ {0,...,N}, and

(ii) for some positive integer K ≤ N and real δ > 0, we have p(K)= δ and p(i) = 0 for all i ∈ {0,...,K − 1}.

Then deg(p) = Ω( \sqrt{Nδ^{1/K}}).

Proof. Let p^{(m)} and r^{(m)} be as in Theorem 4.4. Then for all m ∈ {1,...,deg(p)}, Theorem 4.4 yields

r^{(m)}≤ ( \frac{2r^{(0)}}{N}) ^{m} \frac{deg(p)^{2m}}{1 · 3 · 5 · ··· · (2m − 1)}

Rearranging,

deg(p) ≥ \sqrt{\frac{N}{2r^{(0)}} (1 · 3 · 5 · ··· · (2m − 1) · r^{(m)})^{1/m}}

for all m ≥ 1 (if m > deg(p) then r^{(m)}= 0 so the bound is trivial).

There are now two cases. First suppose r^{(0)} ≥ 2. Then as discussed previously, condition (i) implies that r^{(1)} ≥ 2(r^{(0)}− 1) , and hence that

deg(p) ≥ \sqrt{\frac{Nr^{(1)}}{2r^{(0)}}} ≥ \sqrt{\frac{N (r^{(0)}− 1)}{r^{(0)}}} = Ω( \sqrt{N})

by Theorem 4.2. Next suppose r^{(0)} < 2. Then r^{(m)} ≥ δ/m! for all m ≤ K by Lemma 4.3. So setting m = K yields

deg(p) ≥ \sqrt{\frac{N}{4}( 1 · 3 · 5 · ··· · (2K − 1) · \frac{δ}{K!})^{1/K}} = Ω( \sqrt{Nδ^{1/K}}) .

Either way we are done.

Theory of Computing, Volume 1 (2005), pp. 1–28 15

Strictly speaking, we do not need the full strength of Theorem 4.4 to prove a lower bound on deg(p) that suffices for an oracle separation between NP and BQP/qpoly. For we can show a “rough-and-ready” version of V. A. Markov’s inequality by applying A. A. Markov’s inequality (Theorem 4.2) repeatedly, to p,p^{(1)},p^{(2)}, and so on. This yields

r^{(m)}≤ \frac{2}{N}deg(p)^{2}r^{(m−1)} ≤ ( \frac{2}{N}deg(p)^{2}) ^{m}r^{(0)}

for all m. If deg(p) is small, then this upper bound on r^{(m)} contradicts the lower bound of Lemma 4.3. However, the lower bound on deg(p) that one gets from A. A. Markov’s inequality is only Ω( \sqrt{Nδ^{1/K}/K}),

as opposed to Ω( \sqrt{Nδ^{1/K}}) from Lemma 4.5.^{10}

Shortly after seeing our proof of a weak direct product theorem, Klauck, Špalek, and de Wolf [22] managed to improve the lower bound on deg(p) to the essentially tight Ω( \sqrt{NKδ^{1/K}}). In particular,

their bound implies that δ decreases exponentially in K whenever deg(p) = o(\sqrt{NK}). They obtained this improvement by factoring p instead of differentiating it as in Lemma 4.3.

In any case, a direct product theorem follows trivially from what has already been said.

Theorem 4.6 (Direct Product Theorem). Suppose a quantum algorithm makes T queries to an oracle string X ∈ {0,1}^{N}. Let δ be the minimum probability, over all X with Hamming weight |X|= K, that the algorithm finds all K of the ‘1’ bits. Then δ ≤ (cT^{2}/N)^{K} for some constant c.

Proof. Have the algorithm accept if it finds K or more ‘1’ bits and reject otherwise. Let p(i) be the expected probability of acceptance if X is drawn uniformly at random subject to |X|= i. Then we know the following about p:

(i) p(i) ∈ [0,1]at all integer points i ∈ {0,...,N}, since p(i) is a probability.

(ii) p(i) = 0 for all i ∈ {0,...,K − 1}, since there are not K marked items to be found.

(iii) p(K)≥ δ.

Furthermore, Lemma 4.1 implies that p is a polynomial in i satisfying deg(p) ≤ 2T. It follows from Lemma 4.5 that T = Ω( \sqrt{Nδ^{1/K}}), or rearranging, that δ ≤ (cT^{2}/N)^{K} for some constant c.

We can now prove the desired oracle separation using standard complexity theory tricks.

Theorem 4.7. There exists an oracle relative to which NP ⊄ BQP/qpoly.

10An earlier version of this paper claimed to prove deg(p) = Ω( \sqrt{NK}/log^{3/2}(1/δ)), by applying Bernstein’s inequality [11] rather than A. A. Markov’s to all derivatives p^{(m)}. We have since discovered a flaw in that argument. In any case, the Bernstein lower bound is both unnecessary for an oracle separation, and superseded by the later results of Klauck et al. [22].

Theory of Computing, Volume 1 (2005), pp. 1–28 16

Proof. Given an oracle A : {0,1}^{∗} → {0,1}, define the language L_{A} by (y,z)∈ L_{A} if and only if y ≤ z lexicographically and there exists an x such that y ≤ x ≤ z and A(x)= 1. Clearly L_{A}∈ NP^{A} for all A. We argue that for some A, no BQP/qpoly machine M with oracle access to A can decide L_{A}. Without loss of generality we assume M is fixed, so that only the advice states {|ψ_{n}⟩}_{n≥1} depend on A. We also assume the advice is boosted, so that M’s error probability on any input (y,z)is 2^{−Ω(n^{2})} .

Choose a set S ⊂ {0,1}^{n} subject to |S|= 2^{n/10}; then for all x ∈ {0,1}^{n}, set A(x)= 1 if and only if x ∈ S. We claim that by using M, an algorithm could find all 2^{n/10} elements of S with high probability after only 2^{n/10}poly(n) queries to A. Here is how: first use binary search (repeatedly halving the distance between y and z) to find the lexicographically first element of S. By Lemma 2.2, the boosted advice state |ψ_{n}⟩ is good for 2^{Ω(n^{2})} uses, so this takes only poly(n) queries. Then use binary search to find the lexicographically second element, and so on until all elements have been found.

Now replace |ψ_{n}⟩ by the maximally mixed state as in Theorem 3.4. This yields an algorithm that uses no advice, makes 2^{n/10}poly(n) queries, and finds all 2^{n/10} elements of S with probability 2^{−O(poly(n))} . But taking δ = 2^{−O(poly(n))} , T = 2^{n/10}poly(n), N = 2^{n}, and K = 2^{n/10}, such an algorithm would satisfy δ ≫ (cT^{2}/N)^{K}, which violates the bound of Theorem 4.6.

Indeed one can show that NP ⊄ BQP/qpoly relative a random oracle with probability 1.^{11}

5 The Trace Distance Method

This section introduces a new method for proving lower bounds on quantum one-way communication complexity. Unlike in Section 3, here we do not try to simulate quantum protocols using classical ones. Instead we prove lower bounds for quantum protocols directly, by reasoning about the trace distance between two possible distributions over Alice’s quantum message (that is, between two mixed states). The result is a method that works even if Alice’s and Bob’s inputs are the same size.

We first state our method as a general theorem; then, in Section 5.1, we apply the theorem to prove lower bounds for two problems of Ambainis. Let ∥𝒟 − ℰ∥ denote the variation distance between probability distributions 𝒟 and ℰ.

Theorem 5.1. Let f : {0,1}^{n}× {0,1}^{m}→ {0,1} be a total Boolean function. For each y ∈ {0,1}^{m}, let 𝒜_{y} be a distribution over x ∈ {0,1}^{n} such that f (x,y)= 1. Let ℬ be a distribution over y ∈ {0,1}^{m}, and let 𝒟_{k} be the distribution over ({0,1}^{n})^{k} formed by first choosing y ∈ ℬ and then choosing k samples independently from 𝒜_{y}. Suppose that Pr_{x∈𝒟_{1},y∈ℬ} [f (x,y)= 0] = Ω(1) and that ∥𝒟_{2}− 𝒟_{1}^{2}∥ ≤ δ. Then Q_{2}^{1}(f) = Ω(log1/δ).

Proof. Suppose that if Alice’s input is x, then she sends Bob the l-qubit mixed state ρ_{x}. Suppose also that for every x ∈ {0,1}^{n} and y ∈ {0,1}^{m}, Bob outputs f (x,y)with probability at least 2/3. Then by amplifying a constant number of times, Bob’s success probability can be made 1 − ε for any constant ε > 0. So with L = O(l) qubits of communication, Bob can distinguish the following two cases with constant bias:

11First group the oracle bits into polynomial-size blocks as Bennett and Gill [10] do, then use the techniques of Aaronson [1] to show that the acceptance probability is a low-degree univariate polynomial in the number of all-0 blocks. The rest of the proof follows Theorem 4.7.

Theory of Computing, Volume 1 (2005), pp. 1–28 17

Case I. y was drawn from ℬ and x from 𝒟_{1}.

Case II. y was drawn from ℬ and x from 𝒜_{y}.

For in Case I, we assumed that f (x,y)= 0 with constant probability, whereas in Case II, f (x,y)= 1 always. An equivalent way to say this is that with constant probability over y, Bob can distinguish the mixed states ρ = EX_{x∈𝒟_{1}} [ρ_{x}]and ρ_{y} = EX_{x∈𝒜_{y}} [ρ_{x}]with constant bias. Therefore

EX_{y∈ℬ}[∥ρ − ρ_{y}∥ _{tr}] = Ω(1).

We need an upper bound on the trace distance ∥ρ − ρ_{y}∥ _{tr} that is more amenable to analysis. Let λ_{1},...,λ_{2^{L}} be the eigenvalues of ρ − ρ_{y}. Then

∥ρ − ρ_{y}∥ _{tr}= \frac{1}{2} ∑_{i=1}^{2^{L}} |λ_{i}|

≤ \frac{1}{2}\sqrt{2^{L} ∑_{i=1}^{2^{L}} λ_{i}^{2}}

= 2^{L/2−1} \sqrt{∑_{i,j=1}^{2^{L}} |(ρ)_{ij} − (ρ_{y})_{ij} | ^{2}}

where (ρ)_{ij} is the (i,j) entry of ρ. Here the second line uses the Cauchy-Schwarz inequality, and the third line uses the unitary invariance of the Frobenius norm.

We claim that

EX_{y∈ℬ}[ ∑_{i,j=1}^{2^{L}} |(ρ)_{ij} − (ρ_{y})_{ij} | ^{2}] ≤ 2δ.

From this claim it follows that

EX_{y∈ℬ}[∥ρ − ρ_{y}∥ _{tr}] ≤ 2^{L/2−1} EX_{y∈ℬ}[ \sqrt{∑_{i,j=1}^{2^{L}} |(ρ)_{ij} − (ρ_{y})_{ij} | ^{2}}]

≤ 2^{L/2−1} \sqrt{EX_{y∈ℬ}[ ∑_{i,j=1}^{2^{L}} |(ρ)_{ij} − (ρ_{y})_{ij} | ^{2}]}

≤ \sqrt{2^{L−1}δ}.

Therefore the message length L must be Ω(log1/δ) to ensure that EX_{y∈ℬ} [∥ρ − ρ_{y}∥ _{tr}] = Ω(1). Let us now prove the claim. We have

EX_{y∈ℬ}[ ∑_{i,j=1}^{2^{L}} |(ρ)_{ij} − (ρ_{y})_{ij} | ^{2}] = ∑_{i,j=1}^{2^{L}} ( |(ρ)_{ij} |^{2}− 2Re( (ρ)_{ij}^{∗} EX_{y∈ℬ}[(ρ_{y})_{ij}]) + EX_{y∈ℬ}[ |(ρ_{y})_{ij} |^{2}])

= ∑_{i,j=1}^{2^{L}} ( EX_{y∈ℬ}[ |(ρ_{y})_{ij} |^{2}] − |(ρ)_{ij} |^{2}) ,

Theory of Computing, Volume 1 (2005), pp. 1–28 18

since EX_{y∈ℬ} [(ρ_{y})_{ij}] = (ρ)_{ij}. For a given (i,j) pair,

EX_{y∈ℬ}[ |(ρ_{y})_{ij} |^{2}] − |(ρ)_{ij} |^{2} = EX_{y∈ℬ}[ | EX_{x∈𝒜_{y}} [(ρ_{x})_{ij}]|^{2}] − | EX_{x∈𝒟_{1}} [(ρ_{x})_{ij}]|^{2}

= EX_{y∈ℬ,x,z∈𝒜_{y}} [(ρ_{x})_{ij}^{∗} (ρ_{z})_{ij}] − EX_{x,z∈𝒟_{1}} [(ρ_{x})_{ij}^{∗} (ρ_{z})_{ij}]

= ∑_{x,z}( Pr_{𝒟_{2}}[x,z]− Pr_{𝒟_{1}^{2}}[x,z]) (ρ_{x})_{ij}^{∗} (ρ_{z})_{ij} .

Now for all x,z,

| ∑_{i,j=1}^{2^{L}} (ρ_{x})_{ij}^{∗} (ρ_{z})_{ij} | ≤ ∑_{i,j=1}^{2^{L}} |(ρ_{x})_{ij} |^{2} ≤ 1.

Hence

∑_{x,z}( Pr_{𝒟_{2}}[x,z]− Pr_{𝒟_{1}^{2}}[x,z]) ∑_{i,j=1}^{2^{L}} (ρ_{x})_{ij}^{∗} (ρ_{z})_{ij} ≤ ∑_{x,z}( Pr_{𝒟_{2}}[x,z]− Pr_{𝒟_{1}^{2}}[x,z])
= 2∥𝒟_{2}− 𝒟_{1}^{2}∥
≤ 2δ,

and we are done.

The difficulty in extending Theorem 5.1 to partial functions is that the distribution 𝒟_{1} might not make sense, since it might assign a nonzero probability to some x for which f (x,y)is undefined.

5.1 Applications

In this subsection we apply Theorem 5.1 to prove lower bounds for two problems of Ambainis. To facilitate further research and to investigate the scope of our method, we state the problems in a more general way than Ambainis did. Given a group G, the coset problem Coset(G) is defined as follows. Alice is given a left coset C of a subgroup in G, and Bob is given an element y ∈ G. Bob must output 1 if y ∈ C and 0 otherwise. By restricting the group G, we obtain many interesting and natural problems. For example, if p is prime then Coset(ℤ_{p}) is just the equality problem, so the protocol of Rabin and Yao [31] yields Q_{2}^{1}(Coset(ℤ_{p})) = Θ(loglogp).

Theorem 5.2. Q_{2}^{1}(Coset(ℤ_{p}^{2})) = Θ(logp).

Proof. The upper bound is obvious. For the lower bound, it suffices to consider a function f_{p} defined as follows. Alice is given ⟨x,y⟩∈ 𝔽_{p}^{2} and Bob is given ⟨a,b⟩∈ 𝔽_{p}^{2}; then

f_{p}(x,y,a,b)= \{ \begin{matrix}1 & if y ≡ ax + b(modp) \\ 0 & otherwise. \end{matrix}

Let ℬ be the uniform distribution over ⟨a,b⟩∈ 𝔽_{p}^{2}, and let 𝒜_{a,b} be the uniform distribution over ⟨x,y⟩ such that y ≡ ax + b(modp). Thus 𝒟_{1} is the uniform distribution over ⟨x,y⟩∈ 𝔽_{p}^{2}; note that

Pr_{⟨x,y⟩∈𝒟_{1},⟨a,b⟩∈ℬ} [f_{p}(x,y,a,b)= 0] = 1 − \frac{1}{p}.

But what about the distribution 𝒟_{2}, which is formed by first drawing ⟨a,b⟩∈ ℬ, and then drawing ⟨x,y⟩ and ⟨z,w⟩independently from 𝒜_{a,b}? Given a pair ⟨x,y⟩,⟨z,w⟩∈ 𝔽_{p}^{2}, there are three cases regarding the probability of its being drawn from 𝒟_{2}:

(1) ⟨x,y⟩= ⟨z,w⟩(p^{2} pairs). In this case

Pr_{𝒟_{2}}[⟨x,y⟩,⟨z,w⟩]= ∑_{⟨a,b⟩∈𝔽_{p}^{2}} Pr[⟨a,b⟩]Pr[⟨x,y⟩,⟨z,w⟩| ⟨a,b⟩]

= p( \frac{1}{p^{2}} · \frac{1}{p^{2}}) = \frac{1}{p^{3}}.

(2) x ≠ z (p^{4}−p^{3} pairs). In this case there exists a unique ⟨a^{∗},b^{∗}⟩such that y ≡ a^{∗}x+b^{∗}(modp) and w ≡ a^{∗}z + b^{∗}(modp), so

Pr_{𝒟_{2}}[⟨x,y⟩,⟨z,w⟩]= Pr[⟨a^{∗},b^{∗}⟩]Pr[⟨x,y⟩,⟨z,w⟩| ⟨a^{∗},b^{∗}⟩]

= \frac{1}{p^{2}} · \frac{1}{p^{2}} = \frac{1}{p^{4}}.

(3) x = z but y ≠ w (p^{3}− p^{2} pairs). In this case Pr_{𝒟_{2}} [⟨x,y⟩,⟨z,w⟩]= 0.

Putting it all together,

∥𝒟_{2}− 𝒟_{1}^{2}∥ = \frac{1}{2} ( p^{2} | \frac{1}{p^{3}} − \frac{1}{p^{4}} | + (p^{4}− p^{3}) | \frac{1}{p^{4}} − \frac{1}{p^{4}} | + (p^{3}− p^{2}) |0 − \frac{1}{p^{4}} | )

= \frac{1}{p} − \frac{1}{p^{2}}.

So taking δ = 1/p − 1/p^{2}, we have Q_{2}^{1}(Coset(ℤ_{p}^{2})) = Ω(log(1/δ)) = Ω(logp) by Theorem 5.1.

We now consider Ambainis’ second problem. Given a group G and nonempty set S ⊂ G with |S| ≤ |G|/2, the subset problem Subset(G,S) is defined as follows. Alice is given x ∈ G and Bob is given y ∈ G; then Bob must output 1 if xy ∈ S and 0 otherwise.

Let ℳ be the distribution over st^{−1} ∈ G formed by drawing s and t uniformly and independently from S. Then let Δ = ∥ℳ − 𝒟_{1}∥ , where 𝒟_{1} is the uniform distribution over G.

Proposition 5.3. For all G,S such that |S|≤ |G|/2,

Q_{2}^{1}(Subset(G,S)) = Ω(log1/Δ) .

Proof. Let ℬ be the uniform distribution over y ∈ G, and let 𝒜_{y} be the uniform distribution over x such that xy ∈ S. Thus 𝒟_{1} is the uniform distribution over x ∈ G; note that

Pr_{x∈𝒟_{1},y∈ℬ} [xy ∉ S]= 1 − \frac{|S|}{|G|} ≥ \frac{1}{2}.

We have

∥𝒟_{2}− 𝒟_{1}^{2}∥ = \frac{1}{2} ∑_{x,z∈G}| \begin{matrix}| & \{y ∈ G,s,t ∈ S: xy = s,zy = t\} & | \\ |G| & |S| & 2 \end{matrix} − \frac{1}{|G|^{2}} |

= \frac{1}{2} ∑_{x,z∈G}| \begin{matrix}| & \{s,t ∈ S: xz^{−1} = st^{−1} \} & | \\ |S| & 2 \end{matrix} − \frac{1}{|G|^{2}} |

= \frac{1}{2} ∑_{x∈G} | \begin{matrix}| & \{s,t ∈ S: x = st^{−1} \} & | \\ |S| & 2 \end{matrix} − \frac{1}{|G|}|

= \frac{1}{2} ∑_{x∈G} |Pr_{ℳ}[x]− \frac{1}{|G|}|

= ∥ℳ − 𝒟_{1}∥

= Δ.

Therefore log(1/δ) = Ω(log1/Δ).

Having lower-bounded Q_{2}^{1}(Subset(G,S)) in terms of 1/Δ, it remains only to upper-bound the variation distance Δ. The following proposition implies that for all constants ε > 0, if S is chosen uniformly at random subject to |S| = |G|^{1/2+ε} , then Q_{2}^{1}(Subset(G,S)) = Ω(log(|G|)) with constant probability over S.

Theorem 5.4. For all groups G and integers K ∈ {1,...,|G|}, if S ⊂ G is chosen uniformly at random subject to |S|= K, then Δ = O( \sqrt{|G|}/K) with Ω(1) probability over S.

Proof. We have

Δ = \frac{1}{2} ∑_{x∈G} |Pr_{ℳ}[x]− \frac{1}{|G|}| ≤ \frac{\sqrt{|G|}}{2}\sqrt{∑_{x∈G}( Pr_{ℳ}[x]− \frac{1}{|G|}) ^{2}}

by the Cauchy-Schwarz inequality. We claim that

EX_{S}[ ∑_{x∈G}( Pr_{ℳ}[x]− \frac{1}{|G|}) ^{2}] ≤ \frac{c}{K^{2}}

for some constant c. From this it follows by Markov’s inequality that

Pr_{S}[ ∑_{x∈G}( Pr_{ℳ}[x]− \frac{1}{|G|}) ^{2} ≥ \frac{2c}{K^{2}}] ≤ \frac{1}{2}

Theory of Computing, Volume 1 (2005), pp. 1–28 21

and hence

Δ ≤ \frac{\sqrt{|G|}}{2}\sqrt{\frac{2c}{K^{2}}} = O( \frac{\sqrt{|G|}}{K})

with probability at least 1/2.

Let us now prove the claim. We have

Pr_{ℳ}[x]= Pr_{i,j}[s_{i}s_{j}^{−1} = x] = Pr_{i,j}[s_{i} = xs_{j}],

where S = {s_{1},...,s_{K}} and i,j are drawn uniformly and independently from {1,...,K}. So by linearity of expectation,

EX_{S}[ ∑_{x∈G}( Pr_{ℳ}[x]− \frac{1}{|G|}) ^{2}] = EX_{S}[ ∑_{x∈G}( ( Pr_{i,j}[s_{i} = xs_{j}]) ^{2}− \frac{2}{|G|} Pr_{i,j}[s_{i} = xs_{j}] + \frac{1}{|G|^{2}}) ]

= ∑_{x∈G}( \frac{1}{K^{4}} ∑_{i,j,k,l=1}^{K} p_{x,ijkl}) − \frac{2}{|G|} ∑_{x∈G}( \frac{1}{K^{2}} ∑_{i,j=1}^{K} p_{x,ij}) + \frac{1}{|G|}

where

p_{x,ij} = Pr_{S}[s_{i} = xs_{j}],
p_{x,ijkl} = Pr_{S}[s_{i} = xs_{j} ∧ s_{k} = xs_{l}] .

First we analyze p_{x,ij}. Let ord(x)be the order of x in G. Of the K^{2} possible ordered pairs (i,j), there are K pairs with the “pattern” ii (meaning that i = j), and K (K − 1) pairs with the pattern ij (meaning that i ≠ j). If ord(x)= 1 (that is, x is the identity), then we have p_{x,ij} = Pr_{S}[s_{i} = s_{j}], so p_{x,ij} = 1 under the pattern ii, and p_{x,ij} = 0 under the pattern ij. On the other hand, if ord(x)> 1, then p_{x,ij} = 0 under the pattern ii, and p_{x,ij} = \frac{1}{|G|−1} under the pattern ij. So

\frac{1}{K^{2}} ∑_{x∈G} ∑_{i,j=1}^{K} p_{x,ij} = \frac{1}{K^{2}}( K + (|G|− 1) \frac{K (K − 1)}{|G|− 1}) = 1.

Though unnecessarily cumbersome, the above analysis was a warmup for the more complicated case of p_{x,ijkl}. The following table lists the expressions for p_{x,ijkl}, given ord(x)and the pattern of (i,j,k,l).

Pattern  Number of such 4-tuples ord(x)= 1 ord(x)= 2  ord(x)> 2
iiii,iikk  K^{2}  1  0  0
ijij  K (K − 1)  0  \frac{1}{|G|−1}  \frac{1}{|G|−1}
ijji  K (K − 1)  0  \frac{1}{|G|−1}  0
iiil,iiki,ijii,ijjj  4K (K − 1)  0  0  0
ijki,ijjk  2K (K − 1) (K − 2)  0  0  \frac{1}{(|G|−1) (|G|−2)}
iikl,ijkk,ijik,ijkj 4K (K − 1) (K − 2)  0  0  0
ijkl  K (K − 1) (K − 2) (K − 3)  0  \frac{1}{(|G|−1) (|G|−3)}  \frac{1}{(|G|−1) (|G|−3)}

Let r be the number of x ∈ G such that ord(x)= 2, and let r′= |G|− r − 1 be the number such that ord(x)> 2. Then

\frac{1}{K^{4}} ∑_{x∈G} ∑_{i,j,k,l=1}^{K} p_{x,ijkl} = \frac{1}{K^{4}}( \begin{matrix}K^{2}+ (2r + r′) \frac{K(K−1)}{|G|−1} + 2r′\frac{K(K−1)(K−2)}{(|G|−1) (|G|−2)} \\ +(r + r′) \frac{K(K−1)(K−2)(K−3)}{(|G|−1) (|G|−3)} \end{matrix} )

≤ \frac{1}{|G|− 3} + O( \frac{1}{K^{2}})

using the fact that K ≤ |G|.

Putting it all together,

EX_{S}[ ∑_{x∈G}( Pr_{ℳ}[x]− \frac{1}{|G|}) ^{2}] ≤ \frac{1}{|G|− 3} + O( \frac{1}{K^{2}}) − \frac{2}{|G|}+ \frac{1}{|G|} = O( \frac{1}{K^{2}})

and we are done.

From fingerprinting we also have the following upper bound. Let q be the periodicity of S, defined as the number of distinct sets gS = {gs: s ∈ S} where g ∈ G.

Proposition 5.5. R_{2}^{1}(Subset(G,S)) = O(log|S|+ loglogq) .

Proof. Assume for simplicity that q = |G|; otherwise we could reduce to a subgroup H ≤ G with |H|= q. The protocol is as follows: Alice draws a uniform random prime p from the range [|S|^{2}log^{2}|G|,2|S|^{2}log^{2}|G|]; she then sends Bob the pair (p,xmodp)where x is interpreted as an integer. This takes O(log|S|+ loglog|G|) bits. Bob outputs 1 if and only if there exists a z ∈ G such that zy ∈ S and x ≡ z(modp). To see the protocol’s correctness, observe that if x ≠ z, then there at most log|G|primes p such that x −z ≡ 0(modp), whereas the relevant range contains Ω( \begin{matrix}|S| & ^{2} & log & ^{2} & |G| \\ log & (|S|log|G|) \end{matrix}) primes. Therefore, if xy ∉ S, then by the union bound

Pr_{p}[∃z: zy ∈ S,x ≡ z(modp)] = O( |S|log|G| \begin{matrix}log & (|S|log|G|) \\ |S| & 2 & log & 2 & |G| \end{matrix}) = o(1).

6 Open Problems

• Are R_{2}^{1}(f) and Q_{2}^{1}(f) polynomially related for every total Boolean function f? Also, can we exhibit any asymptotic separation between these measures? The best separation we know of is a factor of 2: for the equality function we have R_{2}^{1}(EQ) ≥ (1 − o(1)) log_{2}n, whereas Winter [37] has shown that Q_{2}^{1}(EQ) ≤ (1/2 + o(1)) log_{2}n using a protocol involving mixed states.^{12} This factor-2 savings is tight for equality: a simple counting argument shows that Q_{2}^{1}(EQ) ≥ (1/2 − o(1)) log_{2}n; and although the usual randomized protocol for equality [31] uses (2 + o(1)) log_{2}n bits, there exist protocols based on error-correcting codes that use only log_{2}(cn)= log_{2}n + O(1) bits. All of this holds for any constant error probability 0 < ε < 1/2.

12If we restrict ourselves to pure states, then (1 − o(1)) log_{2}n qubits are needed. Based on that fact, a previous version of this paper claimed incorrectly that Q_{2}^{1}(EQ) ≥ (1 − o(1)) log_{2}n.

Theory of Computing, Volume 1 (2005), pp. 1–28 23

• As a first step toward answering the above questions, can we lower-bound Q_{2}^{1}(Coset(G)) for groups other than ℤ_{p}^{2} (such as ℤ_{2}^{n}, or nonabelian groups)? Also, can we characterize Q_{2}^{1}(Subset(G,S)) for all sets S, closing the gap between the upper and lower bounds?

• Is there an oracle relative to which BQP/poly ≠ BQP/qpoly?

• Can we give oracles relative to which NP ∩ coNP and SZK are not contained in BQP/qpoly? Bennett et al. [8] gave an oracle relative to which NP ∩ coNP ⊄ BQP, while Aaronson [1] gave an oracle relative to which SZK ⊄ BQP.

• Even more ambitiously, can we prove a direct product theorem for quantum query complexity that applies to any partial or total function (not just search)?

• For all f (partial or total), is R_{2}^{1}(f) = O(\sqrt{n}) whenever Q_{2}^{1}(f) = O(logn)? In other words, is the separation of Bar-Yossef et al. [6] the best possible?

• Can the result D^{1}(f) = O(mQ_{2}^{1}(f) logQ_{2}^{1}(f))for partial f be improved to D^{1}(f) = O(mQ_{2}^{1}(f))? We do not even know how to rule out D^{1}(f) = O(m + Q_{2}^{1}(f)).

• In the Simultaneous Messages (SM) model, there is no direct communication between Alice and Bob; instead, Alice and Bob both send messages to a third party called the referee, who then outputs the function value. The complexity measure is the sum of the two message lengths. Let R_{2}^{||}(f) and Q_{2}^{||}(f) be the randomized and quantum bounded-error SM complexities of f respectively, and let R_{2}^{||,pub}(f) be the randomized SM complexity if Alice and Bob share an arbitrarily long random string. Building on work by Buhrman et al. [12], Yao [40] showed that Q_{2}^{||}(f) = O(logn)whenever R_{2}^{||,pub}(f) = O(1). He then asked about the other direction: for some ε > 0, does R_{2}^{||,pub}(f) = O(n^{1/2−ε} ) whenever Q_{2}^{||}(f) = O(logn), and does R_{2}^{||}(f) = O(n^{1−ε} ) whenever Q_{2}^{||}(f) = O(logn)? In an earlier version of this paper, we showed that R_{2}^{||}(f) = O( \sqrt{n}( R_{2}^{||,pub}(f) + logn) ), which means that a positive answer to Yao’s first question would imply a positive answer to the second. Later we learned that Yao independently proved the same result [39].

Here we ask a related question: can Q_{2}^{||}(f) ever be exponentially smaller than R_{2}^{||,pub}(f)? (Buhrman et al. [12] showed that Q_{2}^{||}(f) can be exponentially smaller than R_{2}^{||}(f).) Iordanis Kerenidis has pointed out to us that, based on the hidden matching problem of Bar-Yossef et al. [6] discussed in Section 2, one can define a relation for which Q_{2}^{||}(f) is exponentially smaller than R_{2}^{||,pub}(f). However, as in the case of Q_{2}^{1}(f) versus R_{2}^{1}(f), it remains to extend that result to functions.

7 Acknowledgments

I thank Oded Regev for pointing out the connection between advice and one-way communication; Andris Ambainis for posing the coset and subset problems; Harry Buhrman for asking about an upper bound on BQP/qpoly; Lance Fortnow for pointing out that P/poly ≠ PP/poly implies PP ⊄ P/poly; Hartmut Klauck and Ronald de Wolf for discussions that led to improvements of Lemma 4.5; Iordanis Kerenidis and Andreas Winter for correcting me about the constant factors in R_{2}^{1}(EQ) and Q_{2}^{1}(EQ); and the anonymous reviewers and ToC editors for helpful comments and corrections.

References

[1] * S. Aaronson: Quantum lower bound for the collision problem. In Proc. 34th ACM STOC, pp. 635–642, 2002. [STOC:509907.509999, arXiv:quant-ph/0111102]. 11, 6

[2] * S. Aaronson: Limitations of quantum advice and one-way communication. In 19th IEEE Conf. Comput. Complexity (CCC), pp. 320–332, 2004. [CCC:10.1109/CCC.2004.1313854, arXiv:quant-ph/0402095]. 1

[3] * S. Aaronson: Quantum computing, postselection, and probabilistic polynomial-time. Submitted, 2004. [arXiv:quant-ph/0412187]. 3.1

[4] * L. Adleman, J. DeMarrais, and M.-D. Huang: Quantum computability. SIAM J. Computing, 26(5):1524–1540, 1997. [SICOMP:10.1137/S0097539795293639]. 3.1

[5] * A. Ambainis, A. Nayak, A. Ta-Shma, and U. V. Vazirani: Quantum dense coding and quantum finite automata. J. ACM, 49:496–511, 2002. Earlier version in 31st ACM STOC, 1999, pp. 376-383. [JACM:581771.581773, arXiv:quant-ph/9804043]. 1, 2.3

[6] * Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis: Exponential separation of quantum and classical one-way communication complexity. In 36th ACM STOC, pp. 128–137, 2004. [STOC:1007352.1007379, ECCC:TR04-036]. 1, 2.1, 6

[7] * R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Earlier version in 39th IEEE FOCS, 1998, pp. 352-361. [JACM:502090.502097, arXiv:quant-ph/9802049]. 1, 4, 4

[8] * C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Computing, 26(5):1510–1523, 1997. [SICOMP:30093, arXiv:quant-ph/9701001]. 1, 4, 6

[9] * C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. Wootters: Teleporting an unknown quantum state by dual classical and EPR channels. Phys. Rev. Lett., 70:1895–1898, 1993. [PRL:10.1103/PhysRevLett.70.1895]. 1 [10] * C. H. Bennett and J. Gill: Relative to a random oracle A, P^{A} ≠ NP^{A} ≠ coNP^{A}with proba-

bility 1. SIAM J. Computing, 10(1):96–113, 1981. [SICOMP:10/0210008]. 11

[11] * S. N. Bernstein: Sur l’ordre de la meilleure approximation des fonctions continues par les polynômes de degré donné. Mem. Cl. Sci. Acad. Roy. Belg., 4:1–103, 1912. French. 10

[12] * H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf: Quantum fingerprinting. Phys. Rev. Lett., 87(16), 2001. 4 pages. [PRL:10.1103/PhysRevLett.87.167902, arXiv:quant-ph/0102001]. 1, 6

[13] * H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: a survey. Theoretical Computer Sci., 288:21–43, 2002. [TCS:10.1016/S0304-3975(01)00144-X]. 1

[14] * P. Duriš, J. Hromkovič, J. D. P. Rolim, and G. Schnitger: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In 14th Symp. Theoret. Aspects of Comp.Sci. (STACS), pp. 117–128, 1997. 2.1

[15] * H. Ehlich and K. Zeller: Schwankung von Polynomen zwischen Gitterpunkten. Mathematische Zeitschrift, 86:41–44, 1964. 4

[16] * L. Fortnow and J. Rogers: Complexity limitations on quantum computation. J. Comput. Sys. Sci., 59(2):240–252, 1999. [JCSS:10.1006/jcss.1999.1651, arXiv:cs.CC/9811023]. 3.1

[17] * O. Goldreich: On quantum computing. 2004. 1 page. 1

[18] * Y. Han, L. Hemaspaandra, and T. Thierauf: Threshold computation and cryptographic security. SIAM J. Computing, 26(1):59–78, 1997. [SICOMP:24046]. 3.1

[19] * A. S. Holevo: Some estimates of the information transmitted by quantum communication channels. Problems of Information Transmission, 9:177–183, 1973. English translation. 1

[20] * H. Klauck: Quantum communication complexity. In 27th Int’l. Colloq. on Automata, Languages, and Programming (ICALP), pp. 241–252, 2000. [arXiv:quant-ph/0005032]. 1, 2.1, 3

[21] * H. Klauck: Quantum time-space tradeoffs for sorting. In 35th ACM STOC, pp. 69–76, 2003. [STOC:780542.780553, arXiv:quant-ph/0211174]. 1, 4, 9

[22] * H. Klauck, R. Špalek, and R. de Wolf: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. In 45th IEEE FOCS, pp. 12–21, 2004. [FOCS:10.1109/FOCS.2004.52, arXiv:quant-ph/0402123]. 1, 4, 4, 10

[23] * E. Kushilevitz and N. Nisan: Communication Complexity. Cambridge, 1997. 1

[24] * A. A. Markov: On a question by D. I. Mendeleev. Zapiski Imperatorskoi Akademii Nauk, SP6(62):1–24, 1890. Russian. English translation at

http://www.math.technion.ac.il/hat/fpapers/markov4.pdf. 4

[25] * V. A. Markov: Über Polynome, die in einem gegebenen Intervalle möglichst wenig von Null abweichen. Math. Ann., 77:213–258, 1916. German. Originally written in 1892. 4

[26] * M. Minsky and S. Papert: Perceptrons (2nd edition). MIT Press, 1988. First appeared in 1968. 4

[27] * A. Nayak: Optimal lower bounds for quantum automata and random access codes. In 40th IEEE FOCS, pp. 369–377, 1999. [FOCS:10.1109/SFFCS.1999.814608, arXiv:quant-ph/9904093]. 1, 3

[28] * M. Nielsen and I. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000. 1, 2.3

[29] * N. Nisan and M. Szegedy: On the degree of Boolean functions as real polynomials. Computational Complexity, 4(4):301–313, 1994. 4, 4

[30] * H. Nishimura and T. Yamakami: Polynomial time quantum computation with advice. Inform. Proc. Lett., 90:195–204, 2003. [IPL:10.1016/j.ipl.2004.02.005, ECCC:TR03-059, arXiv:quant-ph/0305100]. 6, 2.2

[31] * M. Rabin and A. C-C. Yao: Manuscript, cited in [38], 1979. 1, 5.1, 6

[32] * T. J. Rivlin: Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory. Wiley, 1990. 4, 4

[33] * T. J. Rivlin and E. W. Cheney: A comparison of uniform approximations on an interval and a finite subset thereof. SIAM J. Numerical Analysis, 3(2):311–320, 1966. [SINUM:03/0703024]. 4

[34] * N. Sauer: On the density of families of sets. J. Combinatorial Theory Series A, 13:145–147, 1972. [JCombThA:10.1016/0097-3165(72)90019-2]. 1, 3

[35] * Y. Shi: Both Toffoli and controlled-NOT need little help to do universal quantum computation. Quantum Information and Computation, 3(1):84–92, 2002. [arXiv:quant-ph/0205115]. 3.1

[36] * J. Watrous: Succinct quantum proofs for properties of finite groups. In 41st IEEE FOCS, pp. 537–546, 2000. [FOCS:10.1109/SFCS.2000.892141, arXiv:cs.CC/0009002]. 2.2

[37] * A. Winter: Quantum and classical message identification via quantum channels. In O. Hirota, editor, Quantum Information, Statistics, Probability (A. S. Holevo festschrift), pp. 172–189. Rinton, 2004. [arXiv:quant-ph/0401060]. 2.1, 6

[38] * A. C-C. Yao: Some complexity questions related to distributive computing. In 11th ACM STOC, pp. 209–213, 1979. [STOC:804414]. 1, 31

[39] * A. C-C. Yao: Princeton University course assignment, 2001. 6

[40] * A. C-C. Yao: On the power of quantum fingerprinting. In 35th ACM STOC, pp. 77–81, 2003. [STOC:780542.780554, ECCC:TR02-074]. 1, 6 AUTHOR

Scott Aaronson^{13} postdoc Institute for Advanced Study, Princeton aaronson ias edu

http://www.cs.berkeley.edu/~aaronson

ABOUT THE AUTHOR

Scott Aaronson received his Ph.D. at the University of California, Berkeley, in 2004 under Umesh Vazirani. He is proud to be the first author in Theory of Computing.

13This work was performed while the author was a graduate student at UC Berkeley.

Theory of Computing, Volume 1 (2005), pp. 1–28 28