Quantum states cannot be transmitted efficiently
classically
Ashley Montanaro
School of Mathematics, University of Bristol, UK
June 28, 2019
We show that any classical two-way communication protocol with shared randomness
that can approximately simulate the result of applying an arbitrary measurement (held by
one party) to a quantum state of n qubits (held by another), up to constant accuracy, must
transmit at least Ω(2
n
) bits. This lower bound is optimal and matches the complexity of a
simple protocol based on discretisation using an -net. The proof is based on a lower bound
on the classical communication complexity of a distributed variant of the Fourier sampling
problem. We obtain two optimal quantum-classical separations as easy corollaries. First,
a sampling problem which can be solved with one quantum query to the input, but which
requires Ω(N) classical queries for an input of size N. Second, a nonlocal task which
can be solved using n Bell pairs, but for which any approximate classical solution must
communicate Ω(2
n
) bits.
1 Introduction
How much classical information does it take to store or transmit a quantum state? In one sense, the
answer is clear: a pure state of n qubits corresponds to a unit vector in C
2
n
, which requires 2
n+1
− 2
real numbers to be specified exactly (2
n
complex numbers, except that the absolute value of the last
one is already determined by normalisation, and we can ignore an irrelevant overall phase). However,
surprisingly, a number of known results suggest that the amount of classical information required to
transmit a quantum state could actually be substantially less than this.
The most famous result of this nature is Holevo’s Theorem [23], a corollary of which is that the
classical information content of a quantum state of n qubits is bounded by n bits. A related result is a
bound of Nayak [35] which implies that any quantum communication protocol which transmits n bits
with success probability δ > 0 must send at least n − log
2
(1/δ) qubits. Indeed, the number of qubits
transmitted must be linear in n even if we seek only to retrieve one of the bits with high probability [4].
It was also shown by Aaronson [1] that to predict the outcomes of most measurements drawn from
some probability distribution on an n-qubit state, one needs to make only O(n) sample measurements
drawn from the same distribution. This result motivated Aaronson to make the provocative statement
that “while the effective dimension of an n-qubit Hilbert space appears to be exponential in n, in the
sense that is relevant for approximate learning and prediction, this appearance is illusory”.
One way to gain intuition for these results is to observe that having one copy of an n-qubit quantum
state |ψi does not allow the retrieval of up to around 2
n
parameters precisely. For any measurement
which we can perform on |ψi, if we instead applied it to |
e
ψi ≈ |ψi, the distribution on measurement
outcomes would be almost the same. Therefore, the most we can reasonably ask of a classical protocol
Ashley Montanaro: ashley.montanaro@bristol.ac.uk
Accepted in Quantum 2019-06-26, click title to verify 1
arXiv:1612.06546v3 [quant-ph] 27 Jun 2019
designed to store or transmit |ψi is to achieve what the quantum protocol itself does: allow approximate
reproduction of any measurement which we could perform on |ψi.
We can express this task within the framework of a communication game. Imagine there are two
parties (Alice and Bob), where Alice has a description of a pure quantum state |ψi of n qubits, and
Bob has a description of a quantum measurement (POVM) M. Let p
M
(|ψi) denote the probability
distribution resulting from applying the measurement M to |ψi. Then we ask that the classical protocol
allows Alice and Bob to sample from a distribution ep
M
(|ψi) such that kp
M
(|ψi) − ep
M
(|ψi)k
1
≤ , for
some > 0, where k·k
1
is the `
1
distance kvk
1
=
P
i
|v
i
|. Call this task Distributed Quantum Sampling
with inaccuracy . Distributed Quantum Sampling can clearly be solved with = 0 by a quantum
protocol communicating n qubits: Alice just sends |ψi to Bob, who measures according to M.
Distributed Quantum Sampling can also be solved with O(2
n
log(1/)) bits of classical communica-
tion. It is sufficient for Alice to encode |ψi using an -net with respect to the trace norm [22], i.e. a set
of states {|ψ
i
i} such that, for all |ψi, k|ψihψ|−|ψ
i
ihψ
i
|k
1
≤ for some i. Then Alice sends the identity
of the closest state in the -net to Bob, who samples from the distribution corresponding to applying
M to that state. As there are -nets of size (5/)
2
n+1
for the space of pure states of n qubits with
respect to the trace norm [22], the identity of a state in the net can be transmitted using O(2
n
log(1/))
bits of communication
1
. An -net argument can also be used to deal with a technicality: to completely
specify Alice and Bob’s inputs would require an unbounded amount of classical information, leading
to their protocols being only describable via a nonstandard computational model. Restricting Alice’s
input to be picked from an -net reduces the amount of information required to specify it to O(2
n
)
bits for constant > 0, without substantially changing the complexity of the problem (if Distributed
Quantum Sampling with inaccuracy can be solved for states in an -net, this implies a protocol for
Distributed Quantum Sampling for arbitrary states with inaccuracy 2). A similar -net idea can be
applied to discretise Bob’s input, assuming that we restrict to the case where his measurement has
a finite number of outcomes, as the set of POVMs on a finite-dimensional space with a fixed finite
number of outcomes is compact [41].
It is easy to see by a volume argument that the result of [22] is tight up to constant terms; that is,
any -net must have size at least (c/)
2
n
for some constant c > 0. But could we do better than this by
using a protocol which is not based on simply discretising the space of quantum states via an -net?
Questions of this nature are studied in the field of quantum communication complexity [13]. One of
the first results in this area was work of Buhrman, Cleve and Wigderson [12] which implies that, in our
terminology, Distributed Quantum Sampling with = 0 requires Ω(2
n
) bits of classical communication.
Their result is based on proving an Ω(2
n
) lower bound on the deterministic communication complexity
of a distributed version of the Deutsch-Jozsa problem in quantum query complexity. However, the
complexity of this problem drops to O(1) if is allowed to be nonzero.
Following this, a succession of results showed stronger separations between quantum and classical
communication complexity. Raz [36] gave a communication task which could be solved by a two-way
quantum protocol communicating O(n) qubits, but which requires Ω(
√
2
n
) bits of classical communi-
cation. Bar-Yossef, Jayram and Kerenidis [5] showed that there is a communication task which can
be solved by a one-way quantum protocol communicating O(n) qubits, while any classical one-way
bounded-error protocol must communicate Ω(
√
2
n
) bits. Gavinsky et al. [20] later proved a similar
separation for a functional problem, i.e. one where Alice and Bob’s task is to compute a function rather
than sample from a distribution.
Finally, it was shown by Klartag and Regev that Distributed Quantum Sampling requires Ω(
3
√
2
n
)
classical bits of communication between Alice and Bob [25], even if the communication is allowed to be
two-way. This improved a previous result of Gavinsky [19], which implied that Distributed Quantum
1
Note that the complexity achieved by this approach is better than would be obtained by simply writing down |ψi in
the computational basis, and truncating each amplitude after some number of digits. To achieve sufficient precision with
this approach requires specifying each amplitude up to precision O(/
√
2
n
), giving an overall communication complexity
of O(2
n
log(2
n
/)).
Accepted in Quantum 2019-06-26, click title to verify 2
Sampling requires Ω(
8
√
2
n
/
√
n) bits of classical two-way communication. The lower bound of [25] is
proven by considering a more restrictive problem known as the “vector in subspace” problem, which
is defined as follows. Alice gets an n-qubit quantum state |ψi and Bob gets a 2-outcome projective
measurement {M, I − M}. Alice and Bob are promised that either hψ|M |ψi = 1 or hψ|M|ψi = 0;
their task is to determine which is the case. This problem encompasses all one-way exact quantum
protocols where Bob has two possible outputs [27].
Thus, all these results (and more discussed in Section 1.5 below) leave open a natural question:
could there exist a non-trivial classical protocol for Distributed Quantum Sampling for fixed > 0,
i.e. one that transmits asymptotically less than 2
n
bits? Such a protocol indeed exists for the vector
in subspace problem: it was already shown by Raz [36] that this problem can be solved with bounded
failure probability using O(
√
2
n
) bits of classical one-way communication
2
. Could the same be true for
the more general Distributed Quantum Sampling problem? In the author’s opinion, the interest in this
question goes beyond simply finding a tight bound for this problem that would improve the best Ω(
3
√
2
n
)
lower bound known. On a fundamental, conceptual level, the question asks: are quantum states
“really” like an exponentially-long string of numbers, or do they have a more efficient representation?
1.1 Our results
Here we show that any classical communication protocol for Distributed Quantum Sampling with suf-
ficiently small constant inaccuracy > 0 must transmit Ω(2
n
) classical bits, even if the communication
is allowed to be two-way and the parties are allowed shared randomness. This immediately implies that
any classical method for storing an arbitrary quantum state such that measurements can be approxi-
mately simulated on that state must store Ω(2
n
) classical bits. This can be seen as an “anti-Holevo”
theorem: a quantum state of n qubits can only store at most n bits [23], but Ω(2
n
) classical bits are
required to store n qubits.
This optimal lower bound is based on proving a quantum-classical separation for the following
special case of Distributed Quantum Sampling, which we call Distributed Fourier Sampling:
• Alice is given a function f : {0, 1}
n
→ {±1}.
• Bob is given a function g : {0, 1}
n
→ {±1}.
• Their task is for one party (say Bob) to approximately sample from the distribution p
fg
on n-bit
strings s where
p
fg
(s) =
1
2
n
X
x∈{0,1}
n
(−1)
s·x
f(x)g(x)
2
(1)
and s · x =
P
n
i=1
s
i
x
i
. That is, Bob must output a sample from any distribution ep
fg
such that
kep
fg
− p
fg
k
1
≤ , for some constant inaccuracy .
The title “Distributed Fourier Sampling” refers to the fact that the distribution which must be sampled
from is the square of the Fourier transform of the function fg(x) = f(x)g(x) over Z
n
2
.
For conciseness, we henceforth write N = 2
n
. Distributed Fourier Sampling can be solved with n
qubits of one-way communication and = 0. Alice constructs the state |ψ
f
i =
1
√
N
P
x∈{0,1}
n
f(x)|xi
and sends it to Bob. Bob then applies the unitary operator defined by U
g
|xi = g(x)|xi to |ψ
f
i to
produce |ψ
fg
i =
1
√
N
P
x∈{0,1}
n
f(x)g(x)|xi. Finally, Bob applies a Hadamard gate to each qubit of
|ψ
fg
i and measures in the computational basis. The resulting distribution is exactly p
fg
.
By contrast, we have the following result:
2
This result was stated in [36] but the proof has not appeared. We include a proof in Appendix A.
Accepted in Quantum 2019-06-26, click title to verify 3
Theorem 1. There exist universal constants , γ > 0 such that, for sufficiently large N, any two-
way classical communication protocol for Distributed Fourier Sampling with shared randomness and
inaccuracy must communicate at least γN bits.
Theorem 1 implies an optimal lower bound on Distributed Quantum Sampling for = Ω(1),
matching the general upper bound of O(N log(1/)) bits. It remains open to prove a tight bound when
= o(1). However, note that a lower bound of Ω(N + log(1/)) does hold, because an Ω(log(1/))
bound is straightforward. If we let Alice’s state be α|0i + β|1i, and Bob’s measurement is fixed to
be a computational basis measurement, sampling from the corresponding probability distribution up
to inaccuracy is effectively the same as transmitting |α|
2
up to inaccuracy O(). This requires
transmitting Ω(log(1/)) bits.
1.2 Consequences of the lower bound
Theorem 1 immediately implies similar separations in related models.
Query complexity of sampling problems. We can use Distributed Fourier Sampling to obtain a
lower bound in the query model on the classical complexity of the (non-distributed) Fourier Sampling
problem [2, 8]. In this problem, we are given the ability to query (evaluate) an unknown function
h : {0, 1}
n
→ {±1}, which corresponds to an input of size N. Our task is to approximately sample
from the Fourier spectrum of h, i.e. the distribution p
h
on bit-strings s ∈ {0, 1}
n
where
p
h
(s) =
1
2
n
X
x∈{0,1}
n
(−1)
s·x
h(x)
2
.
More precisely, we are asked to output a sample from any distribution ep
h
such that kep
h
−p
h
k
1
≤ . This
problem can be solved exactly with 1 quantum query to h by constructing the state
1
√
2
n
P
x∈{0,1}
n
h(x)|xi,
applying a Hadamard gate to each qubit, and measuring in the computational basis.
Any randomised classical query algorithm solving Fourier Sampling using t queries immediately
implies a classical two-way communication protocol with shared randomness for Distributed Fourier
Sampling communicating at most 2t bits, via a standard reduction [29]. Alice and Bob simulate the
procedure for Fourier Sampling, and whenever they want to query h(x), they replace the query with
evaluating f(x)g(x) using 2 bits of communication
3
. Therefore, Theorem 1 implies a corresponding
lower bound on the query complexity of Fourier Sampling:
Corollary 2. For sufficiently small constant > 0, any randomised classical algorithm solving Fourier
Sampling on N input bits must make Ω(N ) queries.
A lower bound of Ω(N/ log N) queries on Fourier Sampling was previously shown by Aaronson
and Ambainis [2], who conjectured (on p44 of the first version of the paper on the arXiv) that this
bound was tight, not only for Fourier Sampling, but for all sampling problems that can be solved
with 1 quantum query. Corollary 2 refutes this conjecture. Interestingly, it was also shown by the
same authors that any partial boolean function which can be computed by a bounded-error quantum
algorithm making t = O(1) queries can be computed by a bounded-error classical algorithm making
O(N
1−1/(2t)
) queries [2]. Thus, to see maximal quantum-classical query separations, we are required
to go beyond computing boolean functions.
Following the completion of an initial version of this work, I learned that Scott Aaronson and
Lijie Chen have recently obtained an independent proof of Corollary 2 [3]. (Their proof technique
3
Note that, unlike in the setting of quantum query algorithms, it is not necessary for Alice and Bob to send each
other their query indices. The classical algorithm can be expressed as a distribution over deterministic decision trees.
Alice and Bob choose which deterministic tree to implement using shared randomness, and from that point onwards,
the values of the queried bits completely determine the algorithm’s behaviour.
Accepted in Quantum 2019-06-26, click title to verify 4
is compared with the present one in Section 1.3 below.) Also note that it is much simpler to prove
Corollary 2 for deterministic classical algorithms, i.e. ones that choose which queries to make via a
deterministic decision tree, then sample from some distribution depending on the results of the queries.
A proof for this special case is included in Appendix B.
Nonlocality problems. Using a standard mapping between communication protocols and entan-
glement [13, Section IV], we can obtain a distribution D which can be sampled from exactly with no
communication between the parties if Alice and Bob share n Bell pairs, but such that any classical
procedure for sampling from D up to distance in `
1
norm, for some constant > 0, requires Ω(2
n
)
bits of classical communication. A similar lower bound for exact sampling from the same distribution
D was previously shown by Brassard, Cleve and Tapp [9], but the bounded-error case was called “an
important open question” by Toner and Bacon [39].
To obtain D, we define a variant of the Distributed Fourier Sampling problem. Alice and Bob are
again each given a function, f and g respectively. However, this time they are asked to sample from a
distribution on pairs of bit-strings s, t ∈ {0, 1}
n
(where Alice outputs s, Bob outputs t) of the following
form, up to `
1
distance : a distribution where Pr[s ⊕t = u] = p
fg
(u) for all u ∈ {0, 1}
n
, where p
fg
is
defined as in (1). We call this problem Doubly Distributed Fourier Sampling (DDFS).
The quantum protocol for DDFS proceeds as follows. Alice and Bob share a maximally entan-
gled state
1
√
N
P
x∈{0,1}
n
|xi|xi. Alice and Bob each apply the unitary operators U
f
and U
g
, de-
fined by U
f
|xi = f(x)|xi, U
g
|xi = g(x)|xi, to their half of the state to produce the state |φ
fg
i =
1
√
N
P
x∈{0,1}
n
f(x)g(x)|xi|xi. They each then apply Hadamard gates to each qubit of their half of
|φ
fg
i, measure in the computational basis, and output the result.
The final state produced before measuring is
1
N
3/2
X
x∈{0,1}
n
f(x)g(x)
X
s∈{0,1}
n
(−1)
s·x
|si
X
t∈{0,1}
n
(−1)
t·x
|ti
,
so for each pair of bit-strings (s, t) such that s ⊕ t = u, the probability that Alice and Bob see that
pair of bit-strings is
1
N
3
X
x∈{0,1}
n
(−1)
x·(s⊕t)
f(x)g(x)
2
=
p
fg
(u)
N
.
Therefore, the probability that they see some pair of bit-strings (s, t) such that s ⊕ t = u is exactly
p
fg
(u). On the other hand, any classical communication protocol for DDFS approximating the output
distribution up to `
1
inaccuracy with cost c gives a protocol for Distributed Fourier Sampling up to
inaccuracy with cost c + n. This protocol proceeds as follows: after receiving outcomes (s, t) from
their DDFS protocol, Alice sends s to Bob, who outputs s ⊕ t. If the probability that Alice and Bob
output (s, t) was eq
fg
(s, t), then as the DDFS protocol achieved `
1
distance at most from a distribution
where Pr[s ⊕t = u] = p
fg
(u) for all u ∈ {0, 1}
n
, we have
X
s,t∈{0,1}
n
|q
fg
(s, t) − eq
fg
(s, t)| ≤
for some distribution q
fg
such that for all u ∈ {0, 1}
n
,
P
s,t:s⊕t=u
q
fg
(s, t) = p
fg
(u). So the `
1
distance
Accepted in Quantum 2019-06-26, click title to verify 5
between the output distribution and the desired distribution is
X
u∈{0,1}
n
p
fg
(u) −
X
s,t:s⊕t=u
eq
fg
(s, t)
=
X
u∈{0,1}
n
X
s,t:s⊕t=u
q
fg
(s, t)
p
fg
(u)
p
fg
(u) − eq
fg
(s, t)
≤
X
u∈{0,1}
n
X
s,t:s⊕t=u
|q
fg
(s, t) − eq
fg
(s, t)|
=
X
s,t:s,t∈{0,1}
n
|q
fg
(s, t) − eq
fg
(s, t)| ≤ .
We have obtained the following corollary:
Corollary 3. For sufficiently small constant > 0, any two-way classical communication protocol
with shared randomness for Doubly Distributed Fourier Sampling must communicate Ω(N) bits.
It is clear that the bound stated in Corollary 3 is tight up to constant factors, as Alice can send
her Doubly Distributed Fourier Sampling input to Bob using O(N) bits of communication. This
bound is also best possible for the following more general problem: Alice and Bob initially share an
arbitrary bipartite entangled state where each party has local dimension N, are each given as input
a local measurement of rank-1 projectors, and are asked to sample from the joint distribution on
measurement outcomes up to constant inaccuracy > 0. This task can be achieved classically using
O(N) bits of communication, via a similar -net construction as for Distributed Quantum Sampling.
Alice simulates her measurement on her half of the state, after which she knows Bob’s reduced state.
She then uses a shared -net to represent this state up to accuracy , and sends the identity of the state
in the -net to Bob, who can then simulate his own measurement. For constant > 0, it is sufficient
to transmit O(N) bits.
Finally, we remark that the results given here on Fourier Sampling and its distributed variant are
connected to some of the earliest works on quantum computation: the first exponential separation
between exact quantum and classical algorithms via the Deutsch-Jozsa algorithm [17], the first super-
polynomial separation between quantum and randomised classical algorithms via recursive Fourier
sampling [8], and the first exponential separations between exact quantum and classical communication
complexity via the distributed version of the Deutsch-Jozsa algorithm [9, 12]. It is remarkable that,
around 20 years after these pioneering results, Fourier Sampling continues to be a rich vein from which
quantum-classical separations can be mined.
1.3 Sketch of the proof of the main result
In the remainder of the paper, we prove the claimed lower bound on the classical communication
complexity of Distributed Fourier Sampling. We first give an outline of the proof. The starting point
is to observe that, if there is a classical protocol for approximately sampling from p
fg
up to constant
inaccuracy , there is a classical protocol with two outcomes (accept or reject) which communicates
the same number of bits and accepts with probability very close to
hf, gi
N
2
:
=
1
N
X
x∈{0,1}
n
f(x)g(x)
2
(2)
for most inputs f, g. More specifically, there is a protocol which accepts with probability ep(f, g) such
that the average of |ep(f, g) − (hf, gi/N )
2
| over uniformly random f and g is at most /N . A similar
idea was used in [2, 3] in the setting of query complexity. We present the reduction in the proof of
Lemma 5.
Next, we show that for sufficiently small > 0, any classical protocol whose acceptance probability
is this close to (hf, gi/N )
2
on average over f and g must communicate Ω(N ) bits. It is convenient to
Accepted in Quantum 2019-06-26, click title to verify 6
now switch notation and consider the problem of accepting with probability close to (hx, yi/N )
2
for
strings x, y ∈ {±1}
N
. The first challenge in proving a lower bound is that it is hard to reason about
protocols for sampling problems. In particular, one cannot necessarily assume that the existence of
a bounded-error randomised protocol for a sampling problem implies the existence of a deterministic
protocol for the same problem that is accurate on most inputs
4
. This is by contrast with the case of
communication complexity of functional (or relational) problems [29], where this connection is standard
and is a typical first step in the proof of lower bounds.
We instead need to reason directly about the acceptance probability of any low-communication
protocol P . Our high-level strategy is to find three distributions D
−
, D
0
, D
+
on inputs such that
we can upper-bound the acceptance probability p
0
of P under D
0
in terms of a weighted sum of its
acceptance probabilities p
−
, p
+
under D
−
, D
+
. Assuming that P is accurate allows us to find an
upper bound on each of these two acceptance probabilities (and hence an upper bound on p
0
), as
well as a lower bound on p
0
. If the upper bound is lower than the lower bound, we have obtained a
contradiction and there hence cannot exist an accurate low-communication protocol.
To implement this strategy mathematically, we use the fact that a communication protocol can
be understood in terms of rectangles, i.e. subsets of Alice and Bob’s inputs of the form R = A × B.
First, it is not difficult to see that the only rectangles that contribute appreciably to the protocol’s
average acceptance probability under some distribution are those that are large under that distribution.
Next we want to show that, for any large rectangle that contributes substantially to the acceptance
probability under some distribution D
0
, that rectangle must contribute even more substantially to the
acceptance probabilities under some other distributions D
−
, D
+
.
At this point, we can make a connection to a remarkably powerful previous technique used to
determine the communication complexity of the so-called gap-Hamming and gap-orthogonality prob-
lems [15, 16, 37, 40]. In the gap-Hamming problem Alice and Bob are each given strings x, y ∈ {±1}
N
,
under the promise that either hx, yi ≤ −
√
N or hx, yi ≥
√
N, where as above hx, yi =
P
i
x
i
y
i
; their
goal is to determine which is the case. It was first shown by Chakrabarti and Regev that the commu-
nication complexity of the gap-Hamming problem is Ω(N ) [15]. The key technical step of their bound
involved giving three distributions ξ
0
, ξ
−
, ξ
+
on pairs of strings x, y ∈ {±1}
N
such that, for any large
rectangle R,
1
2
(ξ
−
(R) + ξ
+
(R)) ≥
2
3
ξ
0
(R). (3)
The distributions ξ
−
and ξ
+
are concentrated on strings with relatively large and small (respectively)
Hamming distance; indeed, under these distributions x is uniformly random, while for each i, y
i
= x
i
with probability (1 ± p)/2, for some small p. ξ
0
is just the uniform distribution. Thus (3) can be seen
as an anticoncentration bound: any large rectangle (i.e. any rectangle that contains many pairs (x, y)
with respect to the uniform distribution) must contain many pairs (x, y) such that |hx, yi| is large.
This appears to give us exactly what we need to complete the proof. However, there are some
difficulties left to surmount. First, the corresponding acceptance probabilities of a good sampler under
the distributions ξ
0
, ξ
−
, ξ
+
used in [15] are not the ones that we need to use to prove the desired
contradiction. To address this, Alice and Bob randomly flip some of their input bits in a suitably
correlated way, which corresponds to shifting the expected acceptance probability (hx, yi/N)
2
under
each of the distributions. Even after doing this, the bound (3) turns out to not be enough to imply a
contradiction. We instead need a skewed version of the bound:
1
2
e
s
ξ
−
(R) + e
−s
ξ
+
(R)
≥
2
3
ξ
0
(R) (4)
for large rectangles R and arbitrary s ∈ R. Intuitively, in this expression we are improving the upper
bound on ξ
0
in terms of ξ
+
, at the expense of making the bound in terms of ξ
−
worse. It turns out to
4
A previous version of this paper claimed incorrectly that such an implication did hold.
Accepted in Quantum 2019-06-26, click title to verify 7
indeed be possible to prove such a generalised bound based on the techniques of [15]
5
. This generalised
bound could find applications elsewhere.
The final issue to deal with is apparently a technicality, but perhaps an important technicality.
We have from the accuracy constraint on the Distributed Fourier Sampling protocol that the expected
difference between the protocol’s acceptance probability and (hx, yi/N)
2
over uniformly random x and
y is at most /N . However, for the above bounds to be meaningful we need the protocol to also
have a comparable level of accuracy when (x, y) are picked from the distributions ξ
+
, ξ
−
. But the
distributions ξ
+
, ξ
−
we use are relatively far from the uniform distribution in total variation distance,
implying that an expected error of /N under the distribution ξ
0
may not translate into a small error
under the distributions ξ
+
, ξ
−
. To address this, Alice and Bob map their inputs (x, y) to new inputs
(x
0
, y
0
) that are larger by a constant factor but preserve the inner product hx, yi. This allows us to
show that all probabilities in the corresponding distributions ξ
0
±
on the larger inputs are at most a
constant multiple (depending on ) of their corresponding probabilities under the uniform distribution,
so the accuracy bound can be translated across.
We finally remark on connections between the proof techniques of the tight bound given here on the
communication complexity of Distributed Fourier Sampling, and the tight bound of Aaronson and Chen
on the query complexity of Fourier Sampling [3]. At a high level, Aaronson and Chen’s strategy is also
to prove hardness of accepting with probability close to (hx, yi/N)
2
, based on showing contradictory
bounds on the acceptance probability of any classical algorithm that makes few queries, under three
different input distributions. As query algorithms are much more restrictive than communication
protocols, this allows the acceptance probability of an algorithm in this setting to be written as a
weighted sum of certain functions of binomial coefficients. To complete the proof strategy of [3] it is then
sufficient to carry out some technical calculations to bound these coefficients. In the communication
complexity context, it seems necessary to prove a more general bound of the form of (4), which comes
with significant technical complications. For example, it does not seem obvious how to prove a variant
of (4) corresponding to the distributions used in [3].
1.4 Barriers to use of previous results
It is instructive to check why we cannot just use existing communication complexity results to easily
prove a lower bound on Distributed Fourier Sampling. First, by the O(
√
2
n
) classical upper bound of
Raz [36] for any partial boolean function, we can see that we need to look beyond protocols whose
acceptance and rejection probabilities are separated by an additive constant. Looking at (2), one might
naturally guess that a tight lower bound could be proven by considering inputs obeying the promise
that (for example) either hf, gi = 0, or |hf, gi| ≥ 3
√
N. In the former case, the protocol should accept
with probability at most /N , and in the latter case the protocol should accept with probability at
least (3 −)/N = 2/N. So there is a multiplicative constant separating the acceptance probabilities
in the two cases.
This is a variant of the gap-orthogonality problem [16, 37], for which an Ω(N ) lower bound is
known in the case where acceptance and rejection probabilities are separated by an additive constant.
So extending this result to hold in the nonstandard setting where acceptance and rejection probabilities
are small and separated by a multiplicative constant would suffice to prove our desired result. Further,
G¨o¨os and Watson [21] showed that communication lower bounds of this form can be proven using the
corruption method [6, 26, 42], an important lower bound technique in communication complexity, used
in particular by Sherstov to prove his Ω(N) lower bound for gap-orthogonality [37]. If we had a direct
corruption bound of Ω(N) for the gap-orthogonality problem as stated above, this would imply the
result we need.
5
For experts, we remark that the ultimate reason for this is that the bound of [15] hinges on the behaviour of the
function cosh(z), while here we need to understand the function cosh(z − s), which is very similar; and that it might
also be possible to use a suitably generalised and tightened version of bounds proven in [16] to obtain a similar result.
Accepted in Quantum 2019-06-26, click title to verify 8
But in fact such a bound cannot exist, because G¨o¨os and Watson also showed that the corruption
bound is equivalent to the communication complexity of an optimal protocol whose acceptance and
rejection probabilities can be arbitrarily small, but are separated by a multiplicative constant [21].
And there is indeed a nontrivial protocol of this form for gap-orthogonality: query
√
N random bits of
Alice and Bob’s inputs, and accept if they are all different, or all the same. If Alice and Bob’s strings
differ at a 1/2 + ∆/
√
N fraction of positions, the probability of acceptance is precisely
1
2
+
∆
√
N
√
N
+
1
2
−
∆
√
N
√
N
=
1
2
√
N
1 +
2∆
√
N
√
N
+
1 −
2∆
√
N
√
N
!
.
This is roughly equal to 2
−
√
N
(e
2∆
+ e
−2∆
) = 2
1−
√
N
cosh(2∆). For ∆ values separated by a constant
factor, the acceptance probabilities will also be separated by a constant factor (which can be made
arbitrarily large by taking the AND of multiple runs).
It therefore does not seem possible to use gap-orthogonality to prove the desired lower bound via
standard techniques. So how did Sherstov prove a corruption bound of Ω(N) for gap-orthogonality?
He considered the negation of the problem we consider here (i.e. reversing the roles of acceptance and
rejection), which does have such a lower bound. However, it is not clear how to use this problem to
prove a bound on the original Fourier sampling task, as the acceptance probabilities of the quantum
protocol do not correspond directly to the negated problem.
1.5 Other related prior work
The Distributed Quantum Sampling problem has also been studied in the physics literature, where it is
sometimes termed “classical teleportation”. Toner and Bacon [39] showed that, in the case where Bob
makes a projective measurement, Distributed Quantum Sampling on one qubit can be solved exactly
with 2 bits of communication from Alice to Bob (and shared randomness). An asymptotic protocol
which encompasses POVMs and which uses slightly more communication was previously proposed by
Cerf, Gisin and Massar [14]. Montina [32] gave an efficient classical protocol for the special case where
Bob’s measurement consists of two operators: the projector onto a pure state, and its complement (a
similar result can be obtained from work of Kremer, Nisan and Ron [28]). Montina, Pfaffhauser and
Wolf [34], and Montina and Wolf [33], related the asymptotic and one-shot communication complexities
of exact classical simulation of general quantum channels to convex optimisation problems. The related
problem of simulating the correlations obtained by measuring entangled states has also been studied
by a number of authors; see [11, 13] for surveys.
Galv˜ao and Hardy [18] considered a variant of the Distributed Quantum Sampling problem, where
Alice starts with a qubit in the state |0i, the qubit is sent to Bob via a communication channel in
which it undergoes a number of small rotations, and Bob is then asked to determine whether the final
state of the qubit is |0i or |1i, given that one of these is promised to be the case. Galv˜ao and Hardy
argued that any perfect classical simulation of this quantum protocol must use a system which can have
infinitely many states, hence must transmit infinitely many bits of information. (See [10] for a related
result applied to the study of non-classical temporal correlations.) However, this lower bound does not
hold for approximate simulations (e.g. the simulation method based on -nets mentioned above); in
addition, it only holds when arbitrarily many operations can affect the qubit during its progress from
Alice to Bob.
We finally remark that, using a connection between the corruption bound and Bell inequalities, the
gap-orthogonality problem was recently used by Laplante et al. [30] to give inefficiency-resistant Bell
inequalities with large violations.
Accepted in Quantum 2019-06-26, click title to verify 9
2 Preliminary definitions
We use standard definitions from communication complexity [29]. We consider the setting of two-way
communication protocols with shared randomness, with two separated parties (Alice and Bob). In
these protocols, Alice and Bob each receive an input (where Alice’s input is often denoted x ∈ X, and
Bob’s input is denoted y ∈ Y ) and share a random bit-string of arbitrary length. They then follow a
protocol to exchange messages, and at the end of the protocol, one party (e.g. Bob) is asked to output
a bit-string satisfying some predetermined criteria. The cost of the protocol is the total number of bits
communicated. (See [29] for formal definitions.) We usually consider sampling problems, where Alice
and Bob are given the pair (x, y) and asked to output a sample from some predetermined distribution
D
xy
, up to some predetermined accuracy. A rectangle R = A × B is a product subset of Alice and
Bob’s inputs (A ⊆ X, B ⊆ Y ).
[a, b] denotes the interval {z ∈ R : a ≤ z ≤ b}. We will use the following family of distributions on
correlated pairs (x, y) throughout:
Definition 1 (cf. [15]). For p ∈ [−1, 1], let ξ
N
p
denote the distribution on (x, y) ∈ {±1}
N
× {±1}
N
obtained by picking x ∈ {±1}
N
uniformly at random, then picking y by setting y
i
= x
i
with probability
(1 + p)/2, and y
i
= −x
i
with probability (1 − p)/2. When N is implicit, we often write ξ
p
:
= ξ
N
p
.
Note that ξ
N
0
is the uniform distribution on {±1}
N
× {±1}
N
.
3 Proof of main result
We now describe the proof of Theorem 1 in detail. We first state the technical lemmas from which the
main theorem follows, and give its proof assuming these lemmas. The lemmas themselves are proved
afterwards.
The first lemma is a characterisation of shared-randomness classical communication protocols in
terms of rectangles. Note that similar bounds are common in the communication complexity literature
(see e.g. [24]), but are usually stated only for decision problems, where one wishes to either accept or
reject with high probability. As we are interested in the more general setting of sampling problems,
we include a proof in Section 4.
Lemma 4 (Characterisation of communication protocols). Let P be a communication protocol with
two outcomes (accept and reject) and shared randomness, such that P communicates at most c bits.
Then there exists a non-negative function ρ(R) of rectangles R such, for any distribution µ on pairs
(x, y) ∈ X × Y ,
Pr[P accepts (x, y)] =
X
R
ρ(R)µ(R) = η +
X
R:µ(R)≥2
−2c
ρ(R)µ(R)
for some η ∈ [0, 2
−c
), where the probability is taken over both (x, y) ∼ µ and the shared randomness of
P .
Lemma 5 (From Fourier sampling to two-outcome protocols). Assume that, for all sufficiently large
N, there exists a protocol for Distributed Fourier Sampling with inaccuracy that communicates at
most γN bits. Let b be any positive constant. Then there exists a protocol that communicates at most
2γN bits and accepts with probability ep
xy
on input (x, y) ∈ {±1}
N
× {±1}
N
such that:
E
(x,y)∼ξ
−
√
b/N
[ep
xy
] ∈
1 −
0
4N
,
1 +
0
4N
, E
(x,y)∼ξ
0
[ep
xy
] ∈
(b + 1)β −
0
4N
,
(b + 1)β +
0
4N
,
E
(x,y)∼ξ
√
b/N
[ep
xy
] ∈
(4b + 1)β −
0
4N
,
(4b + 1)β +
0
4N
,
Accepted in Quantum 2019-06-26, click title to verify 10
where
0
= Ce
18b
for some universal constant C, and β ∈ [1 −o(1), 1].
Lemma 6 (Skewed anticoncentration bound for large rectangles). For all b > 0 there exists δ > 0
such that for large enough N , all rectangles R ⊆ {±1}
N
× {±1}
N
such that ξ
0
(R) ≥ 2
−δN
, and all s,
1
2
e
s
ξ
−
√
b/N
(R) + e
−s
ξ
√
b/N
(R)
≥
2
3
ξ
0
(R).
Theorem 1 (restated). There exist universal constants , γ > 0 such that, for sufficiently large N,
any two-way classical communication protocol for Distributed Fourier Sampling with shared randomness
and inaccuracy must communicate at least γN bits.
Proof. Assume towards a contradiction that for all sufficiently large N there exists a protocol for
Distributed Fourier Sampling with inaccuracy that communicates at most γN bits, for some small
constants , γ > 0 which will be chosen later. Let P be the corresponding two-outcome communication
protocol that communicates c ≤ 2γN bits and has acceptance probability bounds given by Lemma
5, for some choice of b = O(1) to be determined. By Lemma 4, P in turn implies the existence of a
non-negative function ρ(R) of rectangles R such that
p
0
:
= Pr
(x,y)∼ξ
0
[P accepts (x, y)] = η +
X
R,ξ
0
(R)≥2
−2c
ρ(R)ξ
0
(R) (5)
for some η ∈ [0, 2
−c
). By Lemma 5,
p
0
≥
(b + 1)β −
0
4N
,
where
0
= Ce
6b
and β = 1 −o(1). By (5) and Lemma 6, assuming that γ ≤ δ/4, for any s ∈ R
p
0
≤ 2
−c
+
X
R,ξ
0
(R)≥2
−2c
ρ(R)
3
4
e
s
ξ
−
√
b/N
(R) + e
−s
ξ
√
b/N
(R)
≤ 2
−c
+
3
4
e
s
X
R
ρ(R)ξ
−
√
b/N
(R) + e
−s
X
R
0
ρ(R
0
)ξ
√
b/N
(R
0
)
!
≤ 2
−c
+
3
4
e
s
Pr
(x,y)∼ξ
−
√
b/N
[P accepts (x, y)] + e
−s
Pr
(x,y)∼ξ
√
b/N
[P accepts (x, y)]
!
≤ 2
−c
+
3
4
e
s
1 +
0
4N
+ e
−s
(4b + 1)β +
0
4N
,
where the final inequality is Lemma 5. Choosing, for example, b = 10, s = 2, we get that for some
universal constant D,
11
4N
≤
3
16N
e
2
+
41
e
2
+ D
0
N
+ o(1/N ) ≤
10
4N
+ D
0
N
+ o(1/N ),
where we have folded the 2
−c
term into the o(1/N ) term, which is justified by assuming that P
communicates exactly 2γN bits, up to rounding to an integer (if there exists a protocol that solves
a problem by communicating at most k bits for some k, there exists a protocol that solves the same
problem by communicating exactly k bits). This is a contradiction for small enough = Ω(1) and
large enough N. Therefore such a protocol cannot exist.
4 Proofs of communication complexity lemmas
We first prove a mathematical characterisation of communication protocols in terms of rectangles.
Accepted in Quantum 2019-06-26, click title to verify 11
Lemma 4 (restated). Let P be a communication protocol with two outcomes (accept and reject)
and shared randomness, such that P communicates at most c bits. Then there exists a non-negative
function ρ(R) of rectangles R such, for any distribution µ on pairs (x, y) ∈ X ×Y ,
Pr[P accepts (x, y)] =
X
R
ρ(R)µ(R) = η +
X
R,µ(R)≥2
−2c
ρ(R)µ(R)
for some η ∈ [0, 2
−c
), where the probability is taken over both (x, y) ∼ µ and the internal randomness
of P .
Proof. For any (x, y), we have
Pr[P accepts (x, y)] =
X
D
π(D)[D accepts (x, y)] =
X
D
π(D)
X
R∈R
D
[(x, y) ∈ R],
where π(D) is a distribution on deterministic protocols D, each of which corresponds to a disjoint set
of 1-rectangles R
D
. Taking the expectation over µ,
Pr
(x,y)∼µ,D∼π
[P accepts (x, y)] =
X
D
π(D)
X
R∈R
D
µ(R)
=
X
D
π(D)
X
R∈R
D
,µ(R)<2
−2c
µ(R) +
X
D
π(D)
X
R∈R
D
,µ(R)≥2
−2c
µ(R)
= η +
X
D
π(D)
X
R∈R
D
,µ(R)≥2
−2c
µ(R),
where we infer that 0 ≤ η < 2
−c
by using |R
D
| ≤ 2
c
for all D and
P
D
π(D) = 1. The claim follows
by taking ρ(R) =
P
D,R∈R
D
π(D).
Next we prove a lemma that maps between a distributed Fourier sampler and a two-outcome
communication protocol whose acceptance probability obeys certain bounds. In order to prove the
lemma, we need the following technical claims, whose proofs are deferred to the very end (Section 6):
Proposition 7.
E
(x,y)∼ξ
N
p
"
hx, yi
N
2
#
=
1
N
+
1 −
1
N
p
2
.
Proposition 8. Let ξ
0
p
be the distribution on pairs x
0
, y
0
∈ {±1}
2N
formed by choosing (x, y) ∼ ξ
p
, then
setting x
0
= σ(x, x
00
), y
0
= σ(y, y
00
), where x
00
, y
00
∈ {±1}
N
are fixed strings such that hx
00
, y
00
i = 0, and
σ ∈ S
2N
is a random permutation of the indices of the strings. Then there exists a universal constant
C such that, for sufficiently large N and any ∆, and p ∈ [−0.01, 0.01],
Pr
(x
0
,y
0
)∼ξ
0
p
[hx
0
, y
0
i = ∆] ≤ Ce
2p
2
N
Pr
(x
0
,y
0
)∼ξ
2N
0
[hx
0
, y
0
i = ∆].
Lemma 5 (restated). Assume that, for all sufficiently large N, there exists a protocol for Distributed
Fourier Sampling with inaccuracy that communicates at most γN bits. Let b be any positive constant.
Then there exists a protocol that communicates at most 2γN bits and accepts with probability ep
xy
on
input (x, y) ∈ {±1}
N
× {±1}
N
such that:
E
(x,y)∼ξ
−
√
b/N
[ep
xy
] ∈
1 −
0
4N
,
1 +
0
4N
, E
(x,y)∼ξ
0
[ep
xy
] ∈
(b + 1)β −
0
4N
,
(b + 1)β +
0
4N
,
E
(x,y)∼ξ
√
b/N
[ep
xy
] ∈
(4b + 1)β −
0
4N
,
(4b + 1)β +
0
4N
,
where
0
= Ce
18b
for some universal constant C, and β ∈ [1 − o(1), 1].
Accepted in Quantum 2019-06-26, click title to verify 12
Proof. We first show that, for any N = 2
n
, the existence of a Fourier sampler with the assumed
parameters implies the existence of a protocol that communicates γN bits and accepts with probability
ep
xy
for each pair (x, y), such that
E
(x,y)∼ξ
0
"
ep
xy
−
hx, yi
N
2
#
≤
N
. (6)
To see this, note that by the definition of Distributed Fourier Sampling and the assumed parameters for
the protocol, there exists a protocol that communicates γN bits and samples from some distribution
p
0
xy
on bit-strings s ∈ {0, 1}
n
such that
≥ E
(x,y)∼ξ
0
X
s∈{0,1}
n
|p
0
xy
(s) − p
xy
(s)|
=
X
s∈{0,1}
n
E
x,y
[|p
0
xy
(s) − p
xy
(s)|],
where p
xy
(s) =
1
N
P
z∈{0,1}
n
(−1)
s·z
x
z
y
z
2
; observe that p
xy
(0
n
) = (hx, yi/N)
2
. By the above in-
equality, there is an s such that E
(x,y)∼ξ
0
[|p
0
xy
(s) − p
xy
(s)|] ≤ /N. This implies the existence of a
protocol which accepts with probability ep
xy
on input (x, y) such that E
(x,y)∼ξ
0
[|ep
xy
−p
xy
(s)|] ≤ /N ;
this protocol simply accepts when the outcome is s, and rejects otherwise. We can assume that s = 0
n
by replacing x with the string x
(s)
defined by x
(s)
z
= (−1)
s·z
x
z
, as p
xy
(s) = p
x
(s)
y
(0
n
). As (x, y) were
uniformly distributed, so are (x
(s)
, y).
Alice and Bob will apply their protocol which achieves the bound (6) to a pair of inputs x
0
, y
0
∈
{±1}
2N
given by a shifted version of their original inputs (x, y). For any α ∈ [−1, 1] and any α
0
∈ [0, 1],
given a pair of inputs (x, y) ∼ ξ
α
, Alice and Bob can produce a pair of inputs (x
00
, y
00
) distributed
according to ξ
α+α
0
−αα
0
by using their shared randomness to do the following: for each i, with proba-
bility α
0
, replace the pair (x
i
, y
i
) ∈ {±1}
2
with a pair (z
i
, z
i
), where z
i
is picked uniformly at random
from {±1}. Then each of x
00
i
and y
00
i
is individually uniform, and
Pr[x
00
i
= y
00
i
] = α
0
+ (1 − α
0
)
1 + α
2
=
1
2
+
α + α
0
− αα
0
2
.
Writing q =
p
b/N, q
0
= q/(1 + q) and then choosing α ∈ {−q, 0, q}, α
0
= q
0
, this maps ξ
−q
7→ ξ
0
,
ξ
0
7→ ξ
q/(1+q)
, ξ
q
7→ ξ
2q/(1+q)
.
Alice and Bob then form a pair of inputs (x
0
, y
0
) by concatenating the inputs (x
00
, y
00
) with a pair
of inputs in {±1}
N
that differ at exactly N/2 positions, and applying the same random permutation
of indices to each of their resulting strings. Denote the resulting distribution on pairs (x
0
, y
0
), when
applied to the distribution ξ
r
on (x
00
, y
00
), by ξ
0
r
. Then clearly
Pr
(x
0
,y
0
)∼ξ
0
r
[hx
0
, y
0
i = ∆] = Pr
(x,y)∼ξ
r
[hx, yi = ∆].
By Proposition 8, there is a universal constant C
0
such that for any r ∈ [−0.01, 0.01],
Pr
(x
0
,y
0
)∼ξ
0
r
[hx
0
, y
0
i = ∆] ≤ C
0
e
2r
2
N
Pr
(x
0
,y
0
)∼ξ
2N
0
[hx
0
, y
0
i = ∆].
For r ∈ {0, q/(1 + q), 2q/(1 + q)} and sufficiently large N , 0 ≤ r ≤ 3
p
b/N, where we recall that
q =
p
b/N. Write Err(x
0
, y
0
)
:
= |ep
x
0
y
0
−(hx
0
, y
0
i/(2N))
2
| for the error when Alice and Bob apply their
Accepted in Quantum 2019-06-26, click title to verify 13
protocol to (x
0
, y
0
). Then we have
E
(x
0
,y
0
)∼ξ
0
r
[Err(x
0
, y
0
)] =
N
X
∆=−N
Pr
(x
0
,y
0
)∼ξ
0
r
[hx
0
, y
0
i = ∆] E
hx
0
,y
0
i=∆
[Err(x
0
, y
0
)]
≤
N
X
∆=−N
C
0
e
18b
Pr
(x
0
,y
0
)∼ξ
2N
0
[hx
0
, y
0
i = ∆] E
hx
0
,y
0
i=∆
[Err(x
0
, y
0
)]
≤ C
0
e
18b
E
(x
0
,y
0
)∼ξ
2N
0
[Err(x
0
, y
0
)]
≤ C
0
e
18b
N
,
where the sums are only taken over even ∆, the inner expectations are uniform over strings x
0
, y
0
such
that hx
0
, y
0
i = ∆, and the last inequality follows from (6). By Proposition 7, we have
E
(x
0
,y
0
)∼ξ
0
0
"
hx
0
, y
0
i
2N
2
#
=
1
4N
, E
(x
0
,y
0
)∼ξ
0
q/(1+q)
"
hx
0
, y
0
i
2N
2
#
=
1
4
1
N
+
1 −
1
N
q
1 + q
2
!
,
E
(x
0
,y
0
)∼ξ
0
2q/(1+q)
"
hx
0
, y
0
i
N
2
#
=
1
4
1
N
+
1 −
1
N
2q
1 + q
2
!
.
The lemma follows by inserting the definition of q and setting C = 4C
0
.
5 Proof of Lemma 6: skewed anticoncentration bound
The proof of Lemma 6 is analogous to that of Lemma 2.5 in [15]. Indeed, although it is a generalisation
of this result, somewhat remarkably the same proof technique goes through. The starting point is to
prove an equivalent result for Gaussian measure.
Let γ
N
denote the Gaussian distribution on R
N
with density (2π)
−N/2
e
kxk
2
/2
, and let Ξ
p
denote
the distribution on pairs (x, y) formed by choosing x, z ∼ γ
N
, and setting y = px +
p
1 − p
2
z. Note
that Ξ
p
is the “Gaussian analogue” of the distribution ξ
p
previously introduced.
Let D(·k·) denote the relative entropy
D(P kQ)
:
=
Z
P (x) ln(P (x)/Q(x)) dx,
where P and Q are probability density functions over R, and write D
γ
(X)
:
= D(P kγ), where X is a
random variable with distribution P . We will need the following technical claims:
Proposition 9 (Chakrabarti and Regev [15, Claim 3.7]). For all , α
0
> 0 there exists a δ > 0 such
that for any probability distribution P on R satisfying D
γ
(P ) < δ, any z ∈ R, and any 0 < α ≤ α
0
,
we have
E
x∼P
[cosh(αx + z)] ≥ e
α
2
/2
− .
Theorem 10 (Chakrabarti and Regev [15, Theorem 3.1]). For all , δ > 0 and large enough N , the
following holds. Let A ⊆ R
N
satisfy γ
N
(A) ≥ e
−
2
N
. Then, for all but an e
−δN/36
measure of unit
vectors y ∈ R
N
, the distribution of hx, yi where x ∼ γ
N
|
A
is equal to the distribution of αX + Y for
some α ∈ [1 − δ, 1] and random variables X, Y satisfying D
γ
(X | Y ) ≤ .
We will prove the following result:
Accepted in Quantum 2019-06-26, click title to verify 14
Theorem 11. For all c, > 0 there exists δ > 0 such that for large enough N and 0 ≤ η ≤ c/
√
N, all
A, B ⊆ R
N
such that γ
N
(A), γ
N
(B) ≥ e
−δN
, and all s,
1
2
e
s
Pr
(x,y)∼Ξ
−η
[x ∈ A ∧y ∈ B] + e
−s
Pr
(x,y)∼Ξ
η
[x ∈ A ∧y ∈ B]
≥ (1 − )γ
N
(A)γ
N
(B).
Chakrabarti and Regev’s Theorem 3.5 is Theorem 11 with s = 0 [15]. The proof of Theorem 11 is
essentially identical to this special case. However, for completeness and the reader’s convenience, we
include a full proof. In the proof, β
1
, . . . , β
7
are positive constants that have to be sufficiently small.
Proof of Theorem 11. Let
A
0
:= {x ∈ A : (1 − β
1
)N ≤ kxk
2
≤ (1 + β
1
)N}
and similarly define B
0
. For sufficiently small δ, by concentration of Gaussian measure, we have
γ
N
(A
0
) ≥ γ
N
(A) − β
2
e
−δN
≥ (1 − β
2
)γ
N
(A)
and similarly for B
0
. Write, for any −1 ≤ ζ ≤ 1,
p
ζ
:
= Pr
(x,y)∼Ξ
ζ
[x ∈ A ∧y ∈ B].
Then
p
ζ
≥ Pr
(x,y)∼Ξ
ζ
[x ∈ A
0
∧ y ∈ B
0
]
= (2π)
−N/2
(2π(1 − η
2
))
−N/2
Z
1
A
0
(x)1
B
0
(y)e
−kxk
2
/2
e
−ky−ηxk
2
/(2(1−η
2
))
dx dy
= (1 − η
2
)
−N/2
E
x∼γ
N
|
A
0
,y∼γ
N
|
B
0
h
e
−η
2
kxk
2
/(2(1−η
2
))
e
−η
2
kyk
2
/(2(1−η
2
))
e
ηhx,yi/(1−η
2
)
i
γ
N
(A
0
)γ
N
(B
0
)
≥ (1 − η
2
)
−N/2
e
−η
2
(1+β
1
)N/(1−η
2
)
E
x∼γ
N
|
A
0
,y∼γ
N
|
B
0
h
e
ηhx,yi/(1−η
2
)
i
γ
N
(A
0
)γ
N
(B
0
)
Applying this inequality with ζ = ±η, we obtain that the quantity we wish to bound, which we can
write as
1
2
(e
s
p
−η
+ e
−s
p
η
), is lower-bounded by
(1−η
2
)
−N/2
e
−η
2
(1+β
1
)N/(1−η
2
)
E
x∼γ
N
|
A
0
,y∼γ
N
|
B
0
1
2
e
s
e
−ηhx,yi/(1−η
2
)
+
1
2
e
−s
e
ηhx,yi/(1−η
2
)
γ
N
(A
0
)γ
N
(B
0
).
(7)
We next observe that
1
2
e
s
e
−ηhx,yi/(1−η
2
)
+
1
2
e
−s
e
ηhx,yi/(1−η
2
)
= cosh(ηhx, yi/(1 − η
2
) − s).
Let B
00
⊆ B
0
be the set of all y ∈ B
0
for which
E
x∼γ
N
|
A
0
[cosh(ηhx, yi/(1 − η
2
) − s)] ≤ (1 − β
3
)e
(η/(1−η
2
))
2
(1−β
1
)N/2
.
We will show that this set is relatively small, γ
N
(B
00
) ≤ β
4
γ
N
(B
0
), implying that
E
x∼γ
N
|
A
0
,y∼γ
N
|
B
0
[cosh(ηhx, yi/(1 − η
2
) − s)] ≥ (1 − β
4
)(1 − β
3
)e
(η/(1−η
2
))
2
(1−β
1
)N/2
and hence
(7) ≥ (1 − η
2
)
−N/2
e
−η
2
(1+β
1
)N/(1−η
2
)
(1 − β
4
)(1 − β
3
)e
(η/(1−η
2
))
2
(1−β
1
)N/2
γ
N
(A
0
)γ
N
(B
0
)
≥ e
Nη
2
/2
e
−η
2
(1+β
1
)N/(1−η
2
)
(1 − β
4
)(1 − β
3
)e
(η/(1−η
2
))
2
(1−β
1
)N/2
(1 − β
2
)
2
γ
N
(A)γ
N
(B)
≥ (1 − )γ
N
(A)γ
N
(B)
Accepted in Quantum 2019-06-26, click title to verify 15
for sufficiently small β
1
, β
2
, β
3
, β
4
and sufficiently large N. Assume the contrary for a contradiction,
i.e. that γ
N
(B
00
) > β
4
γ
N
(B
0
) ≥ β
4
(1 − β
2
)e
−δN
.
Let r ∈ [
p
(1 − β
1
)N,
p
(1 + β
1
)N] be such that the Haar measure of points in B
00
of norm r,
normalised (and hence restricted to the sphere), is at least γ
N
(B
00
); existence of such an r follows from
spherical symmetry of the Gaussian distribution and the definition of B
00
. Next, apply Theorem 10
with chosen to be β
5
, δ chosen to be β
6
, and A chosen to be A
0
. Choosing δ (in the present theorem)
to be small enough, there exists y ∈ B
00
such that the distribution of hx, yi, where x ∼ γ
N
|
A
0
, is given
by αrX + rY for some α ∈ [1 − β
6
, 1] and random variables X, Y satisfying D
γ
(X | Y ) ≤ β
5
. This in
turn implies that
Pr
Y
[D
γ
(X|Y ) ≤
p
β
5
] ≥ 1 −
p
β
5
.
By Proposition 9, for sufficiently small β
7
,
E
x∼γ
N
|
A
0
[cosh(ηhx, yi/(1 − η
2
) − s)] = E[cosh(η(αrX + rY )/(1 − η
2
) − s)]
≥ (1 −
p
β
5
)(e
(αrη/(1−η
2
))
2
/2
− β
7
)
≥ (1 −
p
β
5
)(e
(η/(1−η
2
))
2
(1−β
6
)
2
(1−β
1
)N/2
− β
7
)
> (1 − β
3
)e
(η/(1−η
2
))
2
(1−β
1
)N/2
,
contradicting the assumption that y ∈ B
00
.
We can now prove the corollary we need for the boolean cube (which is Lemma 6 stated in a slightly
more general form).
Corollary 12. For all c, > 0 there exists δ > 0 such that for large enough N and 0 ≤ p ≤ c/
√
N,
all rectangles R ⊆ {±1}
N
× {±1}
N
such that ξ
0
(R) ≥ 2
−δN
, and all s,
1
2
e
s
ξ
−p
(R) + e
−s
ξ
p
(R)
≥ (1 − )ξ
0
(R).
Proof. Again, the argument is essentially the same as in [15]. For R = A × B, let A
0
= {x ∈ R
N
:
sgn(x) ∈ A}, and similarly for B
0
. Then one can check that, for any η ∈ [−1, 1],
Pr
(x,y)∼Ξ
η
[x ∈ A
0
∧ y ∈ B
0
] = ξ
p
(R)
for p = 1 −
2
π
arccos η. In particular, taking η = 0,
min{γ
N
(A
0
), γ
N
(B
0
)} ≥ γ
N
(A
0
)γ
N
(B
0
) = Pr
(x,y)∼Ξ
0
[x ∈ A
0
∧ y ∈ B
0
] = ξ
0
(R) ≥ 2
−δN
.
For p ≤ c/
√
N and sufficiently large N , η ≤ c
0
/
√
N for some constant c
0
, so we can apply Theorem 11
to infer the claim.
6 Proofs of further technical propositions
In this section we prove some claims about the distributions ξ
p
, ξ
0
p
used in the proof of Lemma 5.
Recall that ξ
N
p
is the distribution on pairs (x, y) ∈ {±1}
N
defined in Definition 1.
Proposition 7 (restated).
E
(x,y)∼ξ
N
p
"
hx, yi
N
2
#
=
1
N
+
1 −
1
N
p
2
.
Accepted in Quantum 2019-06-26, click title to verify 16
Proof.
E
(x,y)∼ξ
N
p
"
hx, yi
N
2
#
=
1
N
2
E
(x,y)∼ξ
N
p
X
i
x
i
y
i
!
2
=
1
N
+
1
N
2
X
i6=j
E
(x,y)∼ξ
N
p
[x
i
y
i
x
j
y
j
]
=
1
N
+
1
N
2
X
i6=j
E
(x,y)∼ξ
N
p
[x
i
y
i
] E
(x,y)∼ξ
p
[x
j
y
j
]
=
1
N
+
N(N − 1)
N
2
( E
(x,y)∼ξ
N
p
[x
1
y
1
])
2
=
1
N
+
1 −
1
N
1 + p
2
−
1 − p
2
2
=
1
N
+
1 −
1
N
p
2
.
Proposition 8 (restated). Let ξ
0
p
be the distribution on pairs x
0
, y
0
∈ {±1}
2N
formed by choosing
(x, y) ∼ ξ
p
, then setting x
0
= σ(x, x
00
), y
0
= σ(y, y
00
), where x
00
, y
00
∈ {±1}
N
are fixed strings such that
hx
00
, y
00
i = 0, and σ ∈ S
2N
is a random permutation of the indices of the strings. Then there exists a
universal constant C such that, for sufficiently large N and any ∆, and p ∈ [−0.01, 0.01],
Pr
(x
0
,y
0
)∼ξ
0
p
[hx
0
, y
0
i = ∆] ≤ Ce
p
2
N
Pr
(x
0
,y
0
)∼ξ
2N
0
[hx
0
, y
0
i = ∆].
Proof. Assume ∆ is an even integer, otherwise the claim is trivial. By the definition of the distributions
ξ, ξ
0
, we have
Pr
(x
0
,y
0
)∼ξ
0
p
[hx
0
, y
0
i = ∆] =
1 + p
2
(N+∆)/2
1 − p
2
(N−∆)/2
N
N+∆
2
,
Pr
(x
0
,y
0
)∼ξ
2N
0
[hx
0
, y
0
i = ∆] = 2
−2N
2N
N +
∆
2
.
Setting k = (N + ∆)/2, the ratio R of these two quantities is thus
R = 2
N
(1 + p)
k
(1 − p)
N−k
N
k
2N
k+N/2
≤ 2
N
e
p(2k−N )
N
k
2N
k+N/2
.
We now upper-bound this expression using the binomial coefficient bounds, valid for all integer ` ∈
[1, N − 1],
s
N
8`(N − `)
e
Nh(`/N)
≤
N
`
≤
s
N
2π`(N −`)
e
Nh(`/N)
, (8)
where h(x)
:
= −x ln x −(1 −x) ln(1 − x) is the binary entropy measured in nats [31].
First consider the case k ∈ [0, 0.1N] ∪ [0.9N, N]. For these values of k, using k ≤ N and (8), there
is a universal constant C such that
2
N
e
p(2k−N )
N
k
2N
k+N/2
≤ 2
N
e
Np
N
0.1N
2N
N/2
≤ C2
N
e
Np
e
Nh(0.1)−2N h(1/4)
≤ Ce
N(p−0.1)
,
Accepted in Quantum 2019-06-26, click title to verify 17
implying that, for p ≤ 0.01, R ≤ 1 for sufficiently large N.
Now consider the range k ∈ [0.1N, 0.9N]. Here we will use the inequality, which follows from (8),
that for some universal constant C
0
,
R ≤ C
0
2
N
e
p(2k−N )
s
(k + N/2)(3N/2 − k)
k(N −k)
e
N(h(k/N )−2h(k/(2N)+1/4))
.
Defining x = k/N and combining terms, we have
R ≤ C
0
s
(x + 1/2)(3/2 − x)
x(1 − x)
e
N(ln 2+p(2x−1)+h(x)−2h(x/2+1/4))
.
For these values of x,
R ≤ C
00
e
N(ln 2+p(2x−1)+h(x)−2h(x/2+1/4))
for some new universal constant C
00
, so to prove the bound claimed in the lemma it suffices to show
that f (x)
:
= ln 2 + p(2x − 1) + h(x) − 2h(x/2 + 1/4) ≤ p
2
for all x ∈ [0, 1). By concavity of h,
ln 2 + h(x) = h(1/2) + h(x) ≤ 2h(x/2 + 1/4), so f (x) ≤ p(2x − 1), which is negative for x < 1/2. So,
defining F (x)
:
= f(x + 1/2) −2px = ln 2+ h(x + 1/2) −2h(x/2 + 1/2), we want to find an upper bound
on F (x) over x ∈ [0, 1/2). We will show that F (x) ≤ −x
2
and hence f(x + 1/2) ≤ 2px − x
2
≤ p
2
,
where we take the maximum over x ∈ [0, 1/2).
We have F (0) = 0, and
F
0
(x)
:
=
d
dx
F (x) = ln
1 − 2x
1 + 2x
− ln
1 − x
1 + x
,
so F
0
(0) = 0 as well. Thus it is sufficient to show that F
00
(x) ≤ −2 for all x ∈ [0, 1/2) to prove the
desired bound. One can calculate that
F
00
(x) = −
2 + 4x
2
1 − 5x
2
+ 4x
4
≤ −2
for x in this range, completing the proof.
Acknowledgements
I would like to thank Laura Manˇcinska for helpful discussions on the topic of this paper, Tony Short for
the “anti-Holevo” terminology, Sandu Popescu for pointing out ref. [18], and Scott Aaronson for notify-
ing me of ref. [3]. I would also like to thank several referees for their very helpful comments on previous
versions of this paper. This work was supported by EPSRC Early Career Fellowship EP/L021005/1,
EPSRC grant EP/R043957/1 and the QuantERA ERA-NET Cofund in Quantum Technologies im-
plemented within the European Union’s Horizon 2020 Programme (QuantAlgo project).
A Classical upper bound for the vector in subspace problem
In this appendix we prove a general upper bound on the amount of classical communication required
to solve a bounded-error (and therefore at least as hard) variant of the “vector in subspace” problem
discussed in Section 1. In this version of the problem, Alice gets an n-qubit quantum state |ψi and
Bob gets a 2-outcome projective measurement {M, I − M}. Alice and Bob are promised that either
hψ|M|ψi ≥ 2/3 or hψ|M |ψi ≤ 1/3; their task is to output 1 in the first case, and 0 in the second.
We will show that there is a classical randomised protocol for this problem that communicates
O(
√
N) bits, where as before we set N = 2
n
. This implies that any one-way quantum protocol for
Accepted in Quantum 2019-06-26, click title to verify 18
computing a partial boolean function on n bits can be simulated by a classical protocol communicating
O(
√
N) bits [27]. This protocol was proposed by Raz [36] (and subsequently also described by Klartag
and Regev [25]), who stated this complexity bound, but no proof has appeared. We first note that we
can assume that tr M = 2
n−1
without loss of generality; if not, we embed |ψi and M appropriately
in a space of dimension N
0
≤ 2N such that tr M = N
0
/2, which does not substantially affect the
complexity bounds.
We will need the following technical lemma:
Lemma 13 (Corollary of Bennett et al. [7]). Let |ψi be picked from C
N
according to Haar measure
on the unit sphere, and let P be the projector onto an r-dimensional subspace of C
N
. Then, for any
δ ≥ 0,
Pr
h
hψ|P |ψi ≥ (1 + δ)
r
N
i
≤
(
exp(−rδ
2
/3) [0 ≤ δ ≤ 1]
exp(−rδ/3) [δ ≥ 1]
The protocol proceeds as follows. Alice and Bob use shared randomness to specify K quantum
states |φ
1
i, . . . , |φ
K
i, each picked independently according to Haar measure, for some K (it will turn
out that K = 2
Θ(
√
N)
suffices). Then Alice finds the state |φ
i
i such that |hφ
i
|ψi| is maximised, and
sends the identity of this state to Bob using dlog
2
Ke classical bits of communication. Bob then outputs
0 if hφ
i
|M|φ
i
i ≤ 1/2, and 1 otherwise.
We first observe that |φ
i
i can be expressed as
|φ
i
i = |ψi +
p
1 −
2
|ψ
⊥
i,
where is a random variable such that = hψ|φ
i
i, which can be taken to be real and positive such
that = |hψ|φ
i
i|, and |ψ
⊥
i is a unit vector distributed uniformly at random in the subspace of states
orthogonal to |ψi. This holds because the Haar measure is unitarily invariant, so for each j, |φ
j
i can
be picked by choosing its inner product with each vector in an arbitrary orthonormal basis according
to a complex Gaussian distribution, then normalising the resulting vector.
Assume that hψ|M |ψi ≤ 1/3 (the case hψ|M |ψi ≥ 2/3 is similar, swapping the roles of M and
I − M). Then the probability that Bob fails to output the correct answer is
Pr
|φ
i
i
hφ
i
|M|φ
i
i ≥
1
2
. (9)
We can expand
hφ
i
|M|φ
i
i =
hψ| +
p
1 −
2
hψ
⊥
|
M
|ψi +
p
1 −
2
|ψ
⊥
i
=
2
hψ|M|ψi + 2
p
1 −
2
Re(hψ
⊥
|M|ψi) + (1 −
2
)hψ
⊥
|M|ψ
⊥
i,
and using hψ|M|ψi ≤ 1/3 and a union bound, can upper-bound (9) as
Pr
hφ
i
|M|φ
i
i ≥
1
2
≤ Pr
2
p
1 −
2
Re(hψ
⊥
|M|ψi) ≥
2
12
+ Pr
(1 −
2
)hψ
⊥
|M|ψ
⊥
i ≥
1
2
−
5
2
12
.
We bound each of the remaining two terms separately, conditioned on the event that ≥
0
:= cN
−1/4
for some large constant c (we will show that this event occurs with high probability at the end). For
the first term, we use
Pr
2
p
1 −
2
Re(hψ
⊥
|M|ψi) ≥
2
12
≤ Pr
h
|hψ
⊥
|M|ψi| ≥
0
24
i
= Pr
"
|hψ
⊥
|(I − |ψihψ|)M|ψi|
2
k(I − |ψihψ|)M|ψik
2
≥
0
24k(I − |ψihψ|)M|ψik
2
#
≤ exp(−((
0
/24)
2
(N − 1) − 1)/3),
Accepted in Quantum 2019-06-26, click title to verify 19
where in the last step we apply Lemma 13 with r = 1, δ = (
0
/24)
2
(N − 1) − 1 to |ψ
⊥
i and the
projector
P =
(I − |ψihψ|)M|ψihψ|M(I − |ψihψ|)
tr((I − |ψihψ|)M|ψihψ|M(I − |ψihψ|))
and additionally use that
0
N
−1/2
. For the second term, we use
hψ
⊥
|M|ψ
⊥
i ≤ hψ
⊥
|Π
((I−|ψihψ|)M (I−|ψihψ|))
|ψ
⊥
i,
where Π
X
denotes the projector onto the support of X, and
N/2 = rank(M) ≥ rank((I −|ψihψ|)M(I −|ψihψ|)) = rank((I −|ψihψ|)M) ≥ rank(M) −1 = N/2 −1,
together with Lemma 13 and the bound
1
1 −
2
1
2
−
5
2
12
=
6 − 5
2
12(1 −
2
)
≥
1
2
+
2
12
≥
1
2
+
2
0
12
to obtain
Pr
hψ
⊥
|M|ψ
⊥
i ≥
1
1 −
2
1
2
−
5
2
12
≤ exp(−CN
4
0
)
for some universal constant C. As
0
= Ω(N
−1/4
), the sum of the two probabilities can be bounded
above by an arbitrarily small constant. All that remains is to determine how large K needs to be to
achieve ≥
0
with high probability. Recall that was the largest absolute inner product between any
of the random states |φ
j
i and the fixed state |ψi. For any 0 ≤ x ≤ 1, we have
Pr
|φ
j
i
[|hφ
j
|ψi|
2
≥ x] = (1 − x)
N−1
.
To see this, first note that the distribution obtained by measuring a Haar-random N-dimensional state
|φ
i
i in an arbitrary orthonormal basis is uniform in the probability simplex [38]. Geometrically, this
corresponds to a standard simplex in N −1 spatial dimensions. Truncating this simplex by restricting
one coordinate from the range [0, 1] to the range [x, 1] gives a geometrically similar simplex, whose
volume must therefore be the volume of the original simplex multiplied by (1 − x)
N−1
. So, for any
0 < D < N
1/2
,
Pr
|φ
j
i
[|hφ
j
|ψi|
2
≥ DN
−1/2
] = (1 − DN
−1/2
)
N−1
≥ (e
−2DN
−1/2
)
N−1
≥ e
−2D
√
N
.
It is therefore sufficient to choose K = 2
O(
√
N)
for there to exist some i ∈ {1, . . . , K} such that
|hφ
i
|ψi| ≥ cN
−1/4
with high probability for large enough N, corresponding to O(
√
N) bits of commu-
nication being required to specify |φ
i
i.
B Direct lower bound on the deterministic query complexity of Fourier
sampling
In this appendix we give a simple direct proof of Corollary 2 in the special case of deterministic query
algorithms; that is, algorithms that choose which bits to query deterministically, then sample from
some distribution depending on the bits queried.
Proposition 14. For sufficiently small constant > 0, any deterministic classical query algorithm
that solves Fourier Sampling on N input bits must make Ω(N) queries.
Accepted in Quantum 2019-06-26, click title to verify 20
Recall that in this problem we are given query access to a function h : {0, 1}
n
→ {±1} (equivalently,
to an arbitrary string of N = 2
n
±1’s), and are asked to output a sample from any distribution ep
h
such that kep
h
− p
h
k
1
≤ , where
p
h
(s) =
1
2
n
X
x∈{0,1}
n
(−1)
s·x
h(x)
2
.
Proof. Following the same argument as at the start of Lemma 5, from any classical algorithm which
solves Fourier Sampling with k queries, we can obtain an algorithm of the following form. Given oracle
access to a bit-string x ∈ {±1}
N
, the algorithm makes k queries to elements of x and accepts with
probability q
x
such that
Err := E
x
q
x
−
1
N
X
i
x
i
!
2
≤
N
,
where x is uniformly random. We first argue that we can assume that the algorithm deterministically
queries the first k bits of x and its acceptance probability depends only on these. Any deterministic
classical algorithm corresponds to a decision tree whose leaves are labelled with acceptance probabil-
ities, and where we can assume without loss of generality that no variable occurs more than once on
any path from the root to a leaf. Imagine the first query is to variable x
j
, where j 6= 1, and let x
¯
j
denote the sequence x
1
, . . . , x
j−1
, x
j+1
, . . . , x
n
. Then
Err =
1
2
E
x
¯
j
q
+
x
¯
j
−
1
N
+
1
N
X
i6=j
x
i
2
+
1
2
E
x
¯
j
q
−
x
¯
j
−
−
1
N
+
1
N
X
i6=j
x
i
2
for some sequences q
+
, q
−
corresponding to decision trees of depth k − 1 that do not query x
j
.
By permutation-symmetry of the function
P
i
x
i
, this quantity would remain unchanged if x
1
were
relabelled to x
j
throughout these decision trees. Following this, the overall tree’s first query to x
j
can
be replaced with a query to x
1
without affecting Err. Performing this transformation recursively, the
second query can be assumed to be to variable x
2
, etc.; ultimately the tree can be replaced with an
equivalent one querying variables x
1
, . . . , x
k
in order.
Thus, splitting x into a length-k “queried” string y and a length-m “unqueried” string z such that
k + m = N, the inaccuracy Err can be written in terms of a sequence of numbers q
y
such that
E
y,z
q
y
−
1
N
X
i
y
i
+
X
j
z
j
2
≤
N
.
We will find a lower bound on the left-hand side of this inequality. For convenience, take out a factor
of N
2
, rescaling q
y
appropriately. Then minimising this expression is equivalent to minimising
1
N
2
E
y,z
q
y
−
X
i
y
i
+
X
j
z
j
2
=
1
N
2
E
y,z
q
y
−
X
i
y
i
!
2
−
X
j
z
j
2
− 2
X
i
y
i
!
X
j
z
j
.
Shifting q
y
by (
P
i
y
i
)
2
(which we are free to do as q
y
is an arbitrary function of y), and using the
reverse triangle inequality, we can lower-bound this expression by
1
N
2
E
y,z
q
y
−
X
j
z
j
2
−
2
N
2
E
y,z
X
i
y
i
!
X
j
z
j
.
Accepted in Quantum 2019-06-26, click title to verify 21
The random variables y and z are independent and uniformly distributed; and we have E
y
[|
P
i
y
i
|] =
O(
√
k), E
z
[|
P
i
z
i
|] = O(
√
m). So the second term is at most O(
√
km/N
2
) in magnitude; and the first
term now does not depend on y. It remains to bound this term, i.e. to lower-bound
min
q
1
N
2
E
z
q −
X
j
z
j
2
.
We split into cases. If q ≤ m, this expression is lower-bounded by
1
N
2
m Pr
z
X
j
z
j
2
≥ 2m
≥
Cm
N
2
for some constant C; similarly, if q ≥ m, we obtain a lower bound of
1
N
2
m
2
Pr
z
X
j
z
j
2
≤
m
2
≥
C
0
m
N
2
for some constant C
0
. Therefore, the whole expression is lower-bounded by (Cm − D
√
km)/N
2
=
(m/N
2
)(C − D
p
N/m − 1) for some universal constants C and D. For small enough > 0, there
exists a universal constant D
0
< 1 such that, for all m ≥ D
0
N, this is strictly greater than /N .
References
[1] S. Aaronson. The learnability of quantum states. Proc. Roy. Soc. Ser. A, 463:2088, 2007. DOI:
10.1098/rspa.2007.0113. quant-ph/0608142.
[2] S. Aaronson and A. Ambainis. Forrelation: A problem that optimally separates quantum from
classical computing. In Proc. 47
th
Annual ACM Symp. Theory of Computing, pages 307–316,
2015. DOI: 10.1145/2746539.2746547. arXiv:1411.5729.
[3] S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy ex-
periments. In Proc. 32
nd
Annual IEEE Conf. Computational Complexity, 2017. DOI:
10.4230/LIPIcs.CCC.2017.22. arXiv:1612.05903.
[4] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani. Dense quantum coding and quantum finite
automata. J. ACM, 49(4):496–511, 2002. DOI: 10.1145/581771.581773. quant-ph/9804043.
[5] Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis. Exponential separation of quantum and clas-
sical one-way communication complexity. SIAM J. Comput., 38(1):366–384, 2008. DOI:
10.1137/060651835.
[6] P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A strong direct product theorem for cor-
ruption and the multiparty communication complexity of disjointness. Computational Complexity,
15:391–432, 2007. DOI: 10.1007/s00037-007-0220-2.
[7] C. H. Bennett, P. Hayden, D. Leung, P. Shor, and A. Winter. Remote preparation of quan-
tum states. IEEE Trans. Inform. Theory, 51(1):56–74, 2005. DOI: 10.1109/TIT.2004.839476.
quant-ph/0307100.
[8] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473,
1997. DOI: 10.1137/S0097539796300921.
[9] G. Brassard, R. Cleve, and A. Tapp. Cost of exactly simulating quantum entanglement with classi-
cal communication. Phys. Rev. Lett., 83(9):1874–1877, 1999. DOI: 10.1103/PhysRevLett.83.1874.
quant-ph/9901035.
Accepted in Quantum 2019-06-26, click title to verify 22
[10] S. Brierley, A. Kosowski, M. Markiewicz, T. Paterek, and A. Przysiezna. Non-classicality of
temporal correlations. Phys. Rev. Lett., 115:120404, 2015. DOI: 10.1103/PhysRevLett.115.120404.
arXiv:1501.03505.
[11] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner. Bell nonlocality. Rev. Mod.
Phys., 86:419, 2014. DOI: 10.1103/RevModPhys.86.419. arXiv:1303.2849.
[12] H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and com-
putation. In Proc. 30
th
Annual ACM Symp. Theory of Computing. ACM Press, 1998. DOI:
10.1145/276698.276713. quant-ph/9802040.
[13] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf. Non-locality and communication complexity.
Rev. Mod. Phys., 82(1):665–698, 2010. DOI: 10.1103/RevModPhys.82.665. arXiv:0907.3584.
[14] N. Cerf, N. Gisin, and S. Massar. Classical teleportation of a quantum bit. Phys. Rev. Lett., 84:
2521, 1999. DOI: 10.1103/PhysRevLett.84.2521. quant-ph/9906105.
[15] A. Chakrabarti and O. Regev. An optimal lower bound on the communication complexity of
Gap-Hamming-Distance. SIAM J. Comput., 41(5):1299–1317, 2012. DOI: 10.1137/120861072.
arXiv:1009.3460.
[16] A. Chakrabarti, R. Kondapally, and Z. Wang. Information complexity versus corruption and
applications to orthogonality and Gap-Hamming. In Approximation, Randomization, and Combi-
natorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2012), pages 483–494,
2012. DOI: 10.1007/978-3-642-32512-0˙41. arXiv:1205.0968.
[17] D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proc. Roy. Soc.
London Ser. A, 439(1907):553–558, 1992. DOI: 10.1098/rspa.1992.0167.
[18] E. Galv˜ao and L. Hardy. Substituting a qubit for an arbitrarily large number of classical bits.
Phys. Rev. Lett., 90:087902, 2003. DOI: 10.1103/PhysRevLett.90.087902. quant-ph/0110166.
[19] D. Gavinsky. Classical interaction cannot replace a quantum message. In Proc. 40
th
An-
nual ACM Symp. Theory of Computing, pages 95–102, 2008. DOI: 10.1145/1374376.1374393.
quant-ph/0703215.
[20] D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf. Exponential separations for one-way
quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38
(5):1695–1708, 2008. DOI: 10.1137/070706550. quant-ph/0611209.
[21] Mika G¨o¨os and Thomas Watson. Communication complexity of set-disjointness for all probabili-
ties. Theory of Computing, 12(9):1–23, 2016. DOI: 10.4086/toc.2016.v012a009.
[22] P. Hayden, D. Leung, P. Shor, and A. Winter. Randomizing quantum states: Constructions
and applications. Comm. Math. Phys., 250(2):371–391, 2004. DOI: 10.1007/s00220-004-1087-6.
quant-ph/0307104.
[23] A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communica-
tion channel. Problemy Peredachi Informatsii, 9(3):3–11, 1973. English translation Problems of
Information Transmission, vol. 9, pp. 177-183, 1973.
[24] R. Jain and H. Klauck. The partition bound for classical communication complexity and query
complexity. In Proc. 25
th
Annual IEEE Conf. Computational Complexity, pages 247–258, 2010.
DOI: 10.1109/CCC.2010.31. arXiv:0910.4266.
[25] B. Klartag and O. Regev. Quantum one-way communication can be exponentially stronger than
classical communication. In Proc. 43
rd
Annual ACM Symp. Theory of Computing, pages 31–40,
2011. DOI: 10.1145/1993636.1993642. arXiv:1009.3640.
[26] H. Klauck. Rectangle size bounds and threshold covers in communication complexity. In
Proc. 18
th
Annual IEEE Conf. Computational Complexity, pages 118–134, 2003. DOI:
10.1109/CCC.2003.1214415. cs/0208006.
[27] I. Kremer. Quantum communication. Master’s thesis, Hebrew University, 1995.
[28] I. Kremer, N. Nisan, and D. Ron. On randomized one-round communication complexity. Com-
putational Complexity, 8:21–49, 1999. DOI: 10.1007/s000370050018.
[29] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.
DOI: 10.1016/S0065-2458(08)60342-3.
Accepted in Quantum 2019-06-26, click title to verify 23
[30] S. Laplante, M. Lauri`ere, A. Nolin, J. Roland, and G. Senno. Robust Bell inequalities from commu-
nication complexity. Quantum, 2:72, 2018. DOI: 10.22331/q-2018-06-07-72. arXiv:1606.09514.
[31] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland,
Amsterdam, 1983.
[32] A. Montina. Exponential communication gap between weak and strong classical simulations of
quantum communication. Phys. Rev. A, 87:042331, 2013. DOI: 10.1103/PhysRevA.87.042331.
arXiv:1301.3452.
[33] A. Montina and S. Wolf. Lower bounds on the communication complexity of two-party (quantum)
processes. In Proc. 2014 IEEE International Symp. on Information Theory, pages 1484–1488,
2014. DOI: 10.1109/ISIT.2014.6875080. arXiv:1401.4126.
[34] A. Montina, M. Pfaffhauser, and S. Wolf. Communication complexity of channels in general
probabilistic theories. Phys. Rev. Lett., 111:160502, 2013. DOI: 10.1103/PhysRevLett.111.160502.
arXiv:1301.4441.
[35] A. Nayak. Optimal lower bounds for quantum automata and random access codes. In Proc.
40
th
Annual Symp. Foundations of Computer Science, pages 369–376, 1999. DOI: 10.1109/SF-
FCS.1999.814608.
[36] R. Raz. Exponential separation of quantum and classical communication complexity. In Proc. 31
st
Annual ACM Symp. Theory of Computing, pages 358–367, 1999. DOI: 10.1145/301250.301343.
[37] A. Sherstov. The communication complexity of gap Hamming distance. Theory of Computing, 8:
197–208, 2012. DOI: 10.4086/toc.2012.v008a008.
[38] S. S´ykora. Quantum theory and the Bayesian inference problems. J. Stat. Phys., 11(1):17–27,
1974. DOI: 10.1007/BF01019475.
[39] B. Toner and D. Bacon. Communication cost of simulating Bell correlations. Phys. Rev. Lett.,
91:187904, 2003. DOI: 10.1103/PhysRevLett.91.187904. quant-ph/0304076.
[40] T. Vidick. A concentration inequality for the overlap of a vector on a large set, with application
to the communication complexity of the gap-Hamming-distance problem. Chicago J. Theoret.
Comput. Sci., 2012(1):1–12, 2012. DOI: 10.4086/cjtcs.2012.001.
[41] J. Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. DOI:
10.1017/9781316848142. https://cs.uwaterloo.ca/
˜
watrous/TQI/.
[42] A. Yao. Lower bounds by probabilistic arguments. In Proc. 24
th
Annual Symp. Foundations of
Computer Science, pages 420–428, 1983. DOI: 10.1109/SFCS.1983.30.
Accepted in Quantum 2019-06-26, click title to verify 24