Authors Cedric Yen-Yu Lin, Han-Hsuan Lin,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35
www.theoryofcomputing.org
Upper Bounds on Quantum
Query Complexity Inspired by
the Elitzur–Vaidman Bomb Tester
Cedric Yen-Yu Lin Han-Hsuan Lin
Received August 17, 2015; Revised February 29, 2016; Published November 28, 2016
Abstract: Inspired by the Elitzur–Vaidman bomb testing problem (1993), we introduce a
new query complexity model, which we call bomb query complexity, B( f ). We investigate its
relationship with the usual quantum query complexity Q( f ), and show that B( f ) = Θ(Q( f )2 ).
This result gives a new method to derive upper bounds on quantum query complexity:
we give a method of finding bomb query algorithms from
p classical algorithms, which then
provide non-constructive upper bounds on Q( f ) = Θ( B( f )). Subsequently, we were able
to give explicit quantum algorithms matching our new bounds. We apply this method to the
single-source shortest paths problem on unweighted graphs, obtaining an algorithm with
O(n1.5 ) quantum query complexity, improving the best known algorithm of O(n1.5 log n)
(Dürr et al. 2006, Furrow 2008). Applying this method to the maximum bipartite matching
problem gives an algorithm with O(n1.75 ) quantum query complexity, improving the best
known (trivial) O(n2 ) upper bound.
ACM Classification: F.1.2, F.1.3, F.2.2
AMS Classification: 81P68, 68Q12, 68Q17, 68Q05
Key words and phrases: algorithms, query complexity, quantum algorithms, quantum query complexity,
graph algorithms, Elitzur-Vaidman bomb tester, adversary method, maximum bipartite matching
A conference version of this paper appeared in the Proceedings of the 30th Computational Complexity Conference,
2015 [37].
© 2016 Cedric Yen-Yu Lin and Han-Hsuan Lin
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2016.v012a018
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
1 Introduction
Quantum query complexity is an important method of understanding the power of quantum computers.
In this model we are given a black box containing a Boolean string x = x1 · · · xN , and we would like to
calculate some function f (x) with as few quantum accesses to the black box as possible. It is often easier
to give bounds on the query complexity than on the time complexity of a problem, and insights from the
former often prove useful in understanding the power and limitations of quantum computers. One famous
example is Grover’s algorithm for unstructured search on a set
√ of size N [25]; by treating the unstructured
database as a black box √ to be queried, it was shown that Θ( N) queries were required [9], proving that
Grover’s algorithm’s O( N) time complexity is optimal.
Several methods have been proposed to bound the quantum query complexity. Upper bounds are
almost always proved by finding better query algorithms. Some general methods of constructing quantum
algorithms have been proposed, such as quantum walks [4, 50, 38, 31] and learning graphs [7]. For
lower bounds, the main methods are the polynomial method [6] and the adversary method [3]. In
particular, the general adversary lower bound [30] has been shown to tightly characterize quantum query
complexity [47, 48, 36], but calculating such a tight bound seems difficult in general. Nevertheless, the
general adversary lower bound is valuable as a theoretical tool, for example in proving composition
theorems [48, 36, 33] or showing non-constructive (!) upper bounds [33].
Our work
To improve our understanding of quantum query complexity, we introduce and study an alternative oracle
model, which we call the bomb oracle (see Section 3 for the precise definition). Our model is inspired by
the concept of interaction-free measurements, illustrated vividly by the Elitzur-Vaidman bomb testing
problem [22], in which a property of a system can be measured without disturbing the system significantly.
Like the quantum oracle model, in the bomb oracle model we want to evaluate a function f (x) on a
hidden Boolean string x = x1 · · · xN while querying the oracle as few times as possible. In this model,
however, the bomb oracle is a controlled quantum oracle with the extra requirement that the algorithm
fails if the controlled query returns a 1. This seemingly impossible task can be tackled using the quantum
Zeno effect [40], in a fashion similar to the Elitzur-Vaidman bomb tester [35] (Section 2.2).
Our main result (Theorem 4.1) is that the bomb query complexity, B( f ), is characterized by the square
of the quantum query complexity Q( f ):
Theorem 4.1. B( f ) = Θ(Q( f )2 ).
We prove the upper bound, B( f ) = O(Q( f )2 ) (Theorem 4.3), by adapting Kwiat et al.’s solution of
the Elitzur-Vaidman bomb testing problem (Section 2.2, [35]) to our model. We prove the lower bound,
B( f ) = Ω(Q( f )2 ) (Theorem 4.5), by demonstrating that B( f ) is lower bounded by the square of the
general adversary bound [30], (Adv± ( f ))2 . The aforementioned result that the general adversary bound
tightly characterizes the quantum query complexity [47, 48, 36], Q( f ) = Θ(Adv± ( f )), allows us to draw
our conclusion.
The characterization of query complexity given in Theorem 4.1 allows us to give non-constructive
upper bounds on the quantum query complexity for some problems. For some functions f a bomb query
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 2
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
algorithm is easily designed by adapting a classical algorithm. Specifically, we show the following (stated
informally).
Theorem 5.4. Suppose there is a classical algorithm that computes f (x) in T queries, and the algorithm
guesses the result of each query (0 or 1), making at most an expected G mistakes for all x. Then
we can design a bomb query algorithm that√uses O(T G) queries, and hence B( f ) = O(T G). By our
characterization of Theorem 4.1, Q( f ) = O( T G).
√This result inspired us to look for an explicit quantum algorithm that reproduces the query complexity
O( T G). We were able to do so.
Theorem 5.5. Under the assumptions
√ of Theorem 5.4, there is an explicit algorithm (Algorithm 5.9) for
f with query complexity O( T G).
Using Algorithm 5.9, we were able to give an O(n3/2 ) algorithm for the single-source shortest
paths (SSSP) problem in an unweighted graph with n vertices, beating the best-known O(n3/2 log n)
algorithm [21, 24]. A more striking application is our O(n7/4 ) algorithm for maximum bipartite matching;
in this case the best-known upper bound was the trivial O(n2 ), although the time complexity of this
problem had been studied in [5] (and similar problems in [19]).
Finally, in Section 7 we briefly discuss a related query complexity model, which we call the projective
query complexity P( f ), in which each quantum query to x is immediately followed by a classical
measurement of the query result. This model seems interesting to us because its power lies between
classical and quantum: we observe that Q( f ) ≤ P( f ) ≤ R( f ), where R( f ) is the classical randomized
query complexity, and P( f ) ≤ B( f ) = Θ(Q( f )2 ). We note that Regev and Schiff [46] showed that
P(OR) = Θ(N).
Past and related work
Mitchison and Jozsa have proposed a different computational model called counterfactual computation
[41], also based on interaction-free measurement. In counterfactual computation the result of a com-
putation may be learnt without ever running the computer. There has been some discussion on what
constitutes counterfactual computation; see for example [29, 42, 28, 51, 27, 49, 52].
There have also been other applications of interaction-free measurement to quantum cryptography. For
example, Noh has proposed counterfactual quantum cryptography [45], where a secret key is distributed
between parties, even though a particle carrying secret information is not actually transmitted. More
recently, Brodutch et al. proposed an adaptive attack [13] on Wiesner’s quantum money scheme [53]; this
attack is directly based off Kwiat et al.’s solution of the Elitzur-Vaidman bomb testing problem [35].
Our Algorithm 5.9 is very similar to Kothari’s algorithm for the oracle identification problem [34],
and we refer to his analysis of the query complexity in our paper.
The projective query model we detail in Section 7 was, to our knowledge, first considered by Aaronson
in unpublished work in 2002 [1].
Discussion and outlook
Our work raises a number of open questions. The most obvious ones are those pertaining to the application
of our recipe for turning classical algorithms into bomb algorithms, Theorem 5.4.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 3
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
• Can we generalize our method to handle non-Boolean input and output? If so, we might be able to
find better upper bounds for the adjacency-list model, or to study graph problems with weighted
edges.
• Can our explicit (through Theorem 5.5) algorithm for maximum bipartite matching be made more
time efficient? The best known quantum algorithm for this task has time complexity O(n2 log n) in
the adjacency matrix model [5].
• Finally, can we find more upper bounds using Theorem 5.4? For example, could the query
complexity of the maximum matching problem on general nonbipartite graphs be improved with
Theorem 5.4, by analyzing the classical algorithm of Micali and Vazirani [39]?
Perhaps more fundamental, however, is the possibility that the bomb query complexity model will
help us understand the relationship between the classical randomized query complexity, R( f ), and the
quantum query complexity Q( f ). It is known [6] that for all total functions f , R( f ) = O(Q( f )6 ); the
current best known separation is R( f ) = Ω̃(Q( f )2.5 ) = Ω̃(B( f )1.125 ), for a function f discovered by
Ben-David [8, 2] after the initial appearance of our paper. Some more open questions, then, are the
following.
• Can we say something about the relationship between R( f ) and B( f ) for specific classes of
functions? For example, is R( f ) = O(B( f )2 ) for total functions?
• Referring to the notation of Theorem 5.4, we have B( f ) = O(T G). Is the quantity G related to
other measures used in the study of classical decision-tree complexity, for example the certificate
complexity, sensitivity [16], block sensitivity [44], or (exact or approximate) polynomial degree?
(For a review, see [14].)
• What about other query complexity models that might help us understand the relationship between
R( f ) and Q( f )? One possibility is the projective query complexity, P( f ), considered in Section 7.
Regev and Schiff [46] have shown (as a special case of their results) that even with such an oracle,
P(OR) = Θ(N) queries are needed to evaluate the OR function.
We hope that further study on the relationship between bomb and classical randomized complexity
will shed light on the power and limitations of quantum computation.
2 Preliminaries
2.1 Mathematical notation
We will assume that the reader is familiar with basic notations and concepts of quantum computing.
See [43] for a reference on quantum computing. We will use the bit-flip gate (the Pauli-X matrix)
0 1
X= (2.1)
1 0
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 4
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
and we define R(θ ) as the rotation matrix exp(−iθY ),
cos θ − sin θ
R(θ ) ≡ . (2.2)
sin θ cos θ
Note that π/(2θ ) applications of R(θ ) rotates |0i to |1i.
We now recall a few facts from matrix analysis. For more details, we refer to [12].
Definition 2.1 (matrix norms). We use k · k and k · kF to denote the spectral norm and the Frobenius
norm, respectively. The spectral norm is defined by
kAxk
kAk = max . (2.3)
|x|6=0 kxk
This is the largest singular value of the matrix. For a hermitian matrix, it is the maximum absolute value
of eigenvalues.
The Frobenius norm of a matrix is the square root of the sum of squared absolute values of its entries:
r q
kAkF = ∑ ∑ |Ai j |2 = tr(A† A) , (2.4)
i j
where † indicates conjugate-transpose.
Lemma 2.2. For any m, n > 0 and matrices X ∈ Cm×n , Y ∈ Cn×n , Z ∈ Cn×m , we have
| tr(XY Z)| ≤ kXkF kY kkZkF .
This lemma can be proved by using that
| tr(XY Z)| ≤ kY kkZXktr [12, Exercise IV.2.12], and
kZXktr ≤ kXkF kZkF [12, Corollary IV.2.6] ,
where k · ktr denotes the trace norm (sum of singular values). (The trace norm will see no further use in
this paper.) A more accessible proof is found online at [15].
In this paper, log always denotes the logarithm with base 2.
2.2 The Elitzur-Vaidman bomb testing problem
The Elitzur-Vaidman bomb testing problem [22] is a well-known thought experiment to demonstrate
how quantum mechanics differs drastically from our classical perceptions. This problem demonstrates
dramatically the possibility of interaction-free measurements, the possibility of a measurement on a
property of a system without disturbing the system.
The bomb-testing problem is explained as follows. Assume we have a bomb that is either a dud
(defective) or a live bomb. The only way to interact with the bomb is to probe it with a photon. If the
bomb is a dud, then the photon passes through unimpeded; if the bomb is live, then the bomb explodes.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 5
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
We would like to determine whether the bomb is live or not without exploding it. If we pass the photon
through a beamsplitter before probing the bomb, we can implement the controlled probe, pictured below.
|ci • |ci
(2.5)
|0i I or X explodes if 1
In this figure c ∈ {0, 1}, and the controlled gate is the identity I if the bomb is a dud, and the bit-flip
operation X if it is live. It was shown in [35] how to determine whether a bomb was live with arbitrarily
low probability of explosion by making use of the quantum Zeno effect [40]. Specifically, the following
circuit determines whether the bomb is live with failure probability O(θ ).
|0i R(θ ) • R(θ ) •
...
|0i I or X |0i I or X (2.6)
π/(2θ ) times in total
If the bomb is a dud, then the controlled probes do nothing, and repeated application of R(θ ) rotates
the control bit from |0i to |1i. If the bomb is live, the bomb explodes with O(θ 2 ) probability in each
application of the probe; in the likely event the bomb does not explode, the control bit is projected back
to |0i. After O(1/θ ) iterations the control bit stays in |0i, with only a O(θ ) probability of explosion.
Using O(1/θ ) operations, we can thus tell a dud bomb apart from a live one with only O(θ ) probability
of explosion.
2.3 Quantum query complexity
Throughout this paper, all functions f which we would like to calculate are assumed to have Boolean
input, i. e., the domain is D ⊆ {0, 1}N .
For a Boolean string x ∈ {0, 1}N , the quantum oracle Ox is a unitary operator that acts on a one-qubit
record register and an N-dimensional index register as follows (⊕ is the XOR function):
Ox |r, ii = |r ⊕ xi , ii (2.7)
This is represented by the following diagram.
|ri |r ⊕ xi i
Ox
|ii |ii
We want to determine the value of a Boolean function f (x) using as few queries to the quantum
oracle Ox as possible. Algorithms for f have the general form as the following circuit, where the Ut are
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 6
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
unitaries independent of x.
Ox Ox Ox
U0 U1 U2 ... UT
At the end of the circuit the first qubit is measured, and the result is the output of the circuit, which would
ideally be f (x) with high probability. The quantum query complexity Qδ ( f ) is the minimum number
of applications of Ox in the circuit required to determine f (x) with error not greater than δ for all x. By
gap amplification (e. g., by performing the circuit multiple rounds and doing majority voting), it can be
shown that the choice of δ only affects the query complexity by a log(1/δ ) factor. We therefore often set
δ = 0.01 and write Q0.01 ( f ) as Q( f ).
3 Bomb query complexity
In this section we introduce a new query complexity model, which we call the bomb query complexity. A
circuit in the bomb query model is a restricted quantum query circuit, with the following restrictions on
the usage of the quantum oracle.
1. We have an extra control register |ci used to control whether Ox is applied (we call the controlled
version COx ):
COx |c, 0, ii = |c, c · xi , ii ,
where · indicates Boolean AND.
2. The record register, i. e., the second register in the definition of COx above, must contain |0i before
COx is applied.
3. After COx is applied, the record register is immediately measured in the computational basis (giving
the answer c · xi ), and the algorithm terminates immediately if a 1 is measured (if c · xi = 1). We
refer to this as the bomb blowing up or the bomb exploding.
|ci • |ci
|0i bomb explodes if c · xi = 1 (3.1)
Ox
|ii |ii
We define the bomb query complexity Bε,δ ( f ) to be the minimum number of times the above circuit needs
to be applied in an algorithm such that the following hold for all input x.
• The algorithm reaches the end without the bomb exploding with probability at least 1 − ε. We refer
to the probability that the bomb explodes as the probability of explosion.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 7
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
• The total probability that the bomb either explodes or fails to output f (x) correctly is at most δ .
Note that this implies δ ≥ ε.
The above implies that the algorithm outputs the correct answer with probability at least 1 − δ .
The effect of circuit (3.1) is equivalent to applying the following projector on |c, ii.
Mx = CPx,0 = ∑ |0, iih0, i| + ∑ |1, iih1, i|
i∈[N] i:xi =0
= I − ∑ |1, iih1, i| .
i:xi =1
CPx,0 (which we will just call Mx in our proofs later on) is the controlled version of Px,0 , the projector
that projects onto the indices i on which xi = 0:
Px,0 = ∑ |iihi| .
i:xi =0
Thus Circuit 3.1 is equivalent to the following circuit.
|ci • |ci
|ii Px,0 (1 − c · xi )|ii
In this notation, the square of the norm of a state is the probability that the state has survived to this stage,
i. e., the algorithm has not terminated. The norm of (1 − c · xi )|xi i is 1 if c · xi = 0 (the state survives this
stage), and 0 otherwise (the bomb blows up).
A general circuit in this model looks like the following.
• • •
Px,0 Px,0 Px,0
U0 U1 U2 UT (3.2)
...
As usual, at the end of the circuit the first qubit is measured, and the result is the output of the circuit.
It is not at all clear that gap amplification can be done efficiently in the bomb query model to improve
the error δ ; repeating the circuit multiple times increases the chance that the bomb blows up. However, it
turns out that the complexity Bε,δ ( f ) is closely related to Qδ ( f ), and therefore the choice of δ affects
Bε,δ ( f ) by at most a log2 (1/δ ) factor as long as δ ≥ ε (see Corollary 4.2). We therefore often omit δ by
setting δ = 0.01, and write Bε,0.01 ( f ) as Bε ( f ). Sometimes we even omit the ε.
Finally, note that the definition of the bomb query complexity B( f ) is inherently asymmetric with
respect to 0 and 1 in the input: querying 1 causes the bomb to blow up, while querying 0 is safe. In
Section 5.1, we define a symmetric bomb query model and its corresponding query complexity, B̃ε,δ ( f ).
We prove that this generalized symmetric model is asymptotically equivalent to the original asymmetric
model, B̃ε,δ ( f ) = Θ(Bε,δ ( f )), in Lemma 5.1. This symmetric version of the bomb query complexity will
turn out to be useful in designing bomb query algorithms.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 8
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
4 Main result
Our main result is the following.
Theorem 4.1. For every function f with Boolean input alphabet, and every ε satisfying 0 < ε ≤ 0.01,
Q0.01 ( f )2
Bε,0.01 ( f ) = Θ .
ε
Here 0.01 can be replaced by any constant not greater than 1/10.
Proof. The upper bound Bε,δ ( f ) = O(Qδ ( f )2 /ε) is proved in Theorem 4.3. The lower bound Bε,δ ( f ) =
Ω(Q0.01 ( f )2 /ε) is proved in Theorem 4.5.
Corollary 4.2. For all functions f with Boolean input alphabet, and numbers ε, δ satisfying 0 < ε ≤
δ ≤ 1/10,
Bε,0.1 ( f ) = O(Bε,δ ( f )), Bε,δ ( f ) = O(Bε,0.1 ( f ) log2 (1/δ )) .
In particular, if δ is constant,
Bε,δ ( f ) = Θ(Bε,0.1 ( f )) .
Proof. Immediate from Theorem 4.3 and Q0.1 ( f ) = O(Qδ ( f )), Qδ ( f ) = O(Q0.1 ( f ) log(1/δ )).
Because of this result, we will often omit the 0.01 in Bε,0.01 and write simply Bε .
4.1 Upper bound
Theorem 4.3. For all functions f with Boolean input alphabet, and numbers ε, δ satisfying 0 < ε ≤ δ ≤
1/10,
Bε,δ ( f ) = O(Qδ ( f )2 /ε) .
The proof follows the solution of Elitzur-Vaidman bomb-testing problem ([35], or Section 2.2). By
taking advantage of the Quantum Zeno effect [40], using O(Q( f )/ε) calls to Mx , we can simulate one call
to Ox with probability of explosion O(ε/Q( f )). Replacing all Ox queries in (3.2) with this construction
results in a bounded error algorithm with probability of explosion O((ε/Q( f ))Q( f )) = O(ε).
Proof. Let θ = π/(2L) for some large positive integer L (chosen later), and recall that
cos θ − sin θ
R(θ ) = .
sin θ cos θ
We claim that with 2L calls to the bomb oracle Mx = CPx,0 , we can simulate Ox by the following circuit
with probability of explosion less than π 2 /(2L) and error O(1/L).
|ri X |r ⊕ xi i
|0i R(θ ) • • R(−θ ) • |0i (discard)
(4.1)
|ii Px,0 Px,0 |ii
repeat L times repeat L times
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 9
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
In words, we simulate Ox acting on |r, ii by the following steps.
1. Append an ancilla qubit |0i, changing the state into |r, 0, ii.
2. Repeat the following L times:
(a) apply R(θ ) on the second register;
(b) apply Mx on the third register controlled by the second register.
At this point, if the bomb hasn’t blown up, the second register should contain 1 − xi .
3. Apply CNOT on the first register controlled by the second register; this copies 1 − xi to the first
register.
4. Apply a NOT gate to the first register.
5. Repeat the following L times to uncompute the second (ancilla) register:
(a) apply R(−θ ) on the second register;
(b) apply Mx on the third register controlled by second register.
6. Discard the second (ancilla) register.
We now calculate explicitly the action of the circuit on an arbitrary state to confirm our claims above.
Consider how the circuit acts on the basis state |r, 0, ii (the second register being the appended ancilla).
We break into cases.
• If xi = 0, then Px,0 |ii = |ii, so the controlled projections do nothing. Thus in Step 2 the rotation
R(θ )L = R(π/2) is applied to the ancilla qubit, rotating it from 0 to 1. After Step 2 then, the state
is |r, 1, ii. Step 3 and 4 together do not change the state, while Step 5 rotates the ancilla back to 0,
resulting in the final state |r, 0, ii.
• If xi = 1, then Px,0 |ii = 0, and
Mx |0, ii = |0, ii, Mx |1, ii = 0 .
Therefore in Step 2 and Step 5, after each rotation R(±θ ), the projection CPx,0 projects the ancilla
back to 0:
Mx R(θ )|0, ii = Mx (cos θ |0i + sin θ |1i)|ii = cos θ |0, ii .
Each application of Mx R(θ ) thus has no change on the state other than to shrink its amplitude
by cos θ . The CNOT in Step 3 has no effect (since the ancilla stays in 0), and Step 4 maps |ri
to |r ⊕ 1i. Since there are 2L applications of this shrinkage (in Step 2 and 5), the final state is
cos2L θ |r ⊕ 1, 0, ii.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 10
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
We can now combine the two cases: by linearity, the application of the circuit on a general state
∑r,i ar,i |r, ii (removing the ancilla) is
∑ ar,i |r, ii → ∑ ar,i |r, ii + ∑ ar,i cos2L (θ )|r ⊕ 1, ii
r,i r∈{0,1},xi =0 r∈{0,1},xi =1
π
= ∑ ar,i cos2Lxi |r ⊕ xi , ii ≡ ψ 0 .
r,i 2L
Thus the effect of this construction simulates the usual quantum oracle |r, ii → |r ⊕ xi , ii with proba-
bility of explosion not greater than
2L
π2 π2
π
1 − cos4L ≤ 1− 1− 2 ≤ .
2L 4L 2L
Moreover, the difference between the output of our circuit, |ψ 0 i, and the output on the quantum oracle,
|ψi = ∑r,i ar,i |r ⊕ xi , ii, is
ψ 0 − |ψi = ∑ ar,i (1 − cos2L (θ ))|r ⊕ 1, ii
r∈{0,1},xi =1
π π2
≤ 1 − cos2L ≤ .
2L 4L
Given this construction, we can now prove our theorem. Suppose we are given a quantum algorithm
that finds f (x) with Qδ 0 ( f ) queries, making at most δ 0 = δ − ε error. We construct an algorithm using
bomb oracles instead by replacing each of the applications of the quantum oracle Ox by our circuit
construction (4.1), where we choose 2
π
L= Q 0( f ) .
2ε δ
Then the probability of explosion is not greater than
π2
Q 0( f ) ≤ ε
2L δ
E
and the difference between the final states, ψ f and ψ 0f , is at most
π2 ε
ψ 0f − ψ f ≤ Q 0( f ) ≤ . (4.2)
4L δ 2
Therefore for any projector P (in particular, the projector that projects onto the classical answer at the
end of the algorithm),
ψ 0f P ψ 0f − ψ f P ψ f ≤ ψ 0f P ψ 0f − ψ f P ψ 0f + ψ 0f P ψ f − ψ f P ψ f
ψ 0f P ψ 0f − ψ f + P ψ 0f − ψ f
≤ ψf
≤ ε/2 + ε/2 = ε
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 11
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
where the first inequality follows by the triangle inequality, the second by Cauchy-Schwarz, and the last
by (4.2). The algorithm accumulates at most ε extra error at the end, giving a total error not greater than
δ 0 + ε = δ . This algorithm makes
π2 2
2LQδ 0 ( f ) < Q 0 ( f ) + 2Qδ 0 ( f )
ε δ
queries to the bomb oracle, and therefore
π2 Qδ −ε ( f )2
2
Bε,δ ( f ) < Qδ −ε ( f ) + 2Qδ −ε ( f ) = O . (4.3)
ε ε
From this we can derive that Bε,δ ( f ) = O(Qδ ( f )2 /ε):
Bε,δ ( f ) < Bε/2,δ ( f )
!
Qδ −ε/2 ( f )2
=O , by (4.3),
ε
Qδ ( f )2
δ ε
=O , since ≤δ− .
ε 2 2
4.2 Lower bound
Theorem 4.5. For all functions f with Boolean input alphabet, and numbers ε, δ satisfying 0 < ε ≤ δ ≤
1/10,
Bε,δ ( f ) = Ω(Q0.01 ( f )2 /ε) .
Before we give the proof of the general result that B( f ) = Ω(Q( f )2 ) (Theorem 4.5), we will illustrate
the proof by means of an example, the special case where f is the AND function.
Theorem 4.4. For δ < 1/10, Bε,δ (AND) = Ω(N/ε).
Proof. Let ψt0 be the unnormalized state of the algorithm with x = 1n , and ψtk be the unnormalized
state with x = 1 · · · 101 · · · 1, xk = 0, right before the (t + 1)-th call to Mx . Then
E E
k
ψt+1 = Ut+1 Mx ψtk
for some unitary Ut+1 . For ease of notation, we’ll write M0 ≡ M1n and Mk = M1···101···1 , where the k-th
bit is 0 in the latter case. When acting on the control and index bits,
N
M0 = ∑ |0, iih0, i| ,
i=1
N
Mk = ∑ |0, iih0, i| + |1, kih1, k| , k = 1, · · · , N .
i=1
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 12
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
Since the operators Mi are projectors, Mi2 = Mi . Define
εti = ψti (I − Mi ) ψti , i = 0, 1, · · · , N . (4.4)
i |ψ i i = ψ i M 2 ψ i = ψ i M ψ i = hψ i |ψ i i − ε i , for all i = 0, · · · , N (including 0!),
Note that hψt+1 t+1 t i t t i t t t t
and hence
T −1
∑ εti = hψ0i |ψ0i i − hψTi |ψTi i ≤ ε .
t=0
We now define the progress function. Let
Wtk = hψt0 |ψtk i
and let the progress function be a sum over the W k :
N N
Wt = ∑ Wtk = ∑ hψt0 |ψtk i .
k=1 k=1
We can lower bound the total change in the progress function by
p
W0 −WT ≥ (1 − 2 δ (1 − δ ))N . (4.5)
(See Ambainis [3] for a proof; his proof equally applies to unnormalized states.)
We now proceed to upper bound W0 −WT . Note that
E
Wtk −Wt+1
k
= hψt0 |ψtk i − ψt0 M0 Mk ψtk
E E E
= ψt0 (I − M0 )Mk ψtk + ψt0 M0 (I − Mk ) ψtk + ψt0 (I − M0 )(I − Mk ) ψtk
and since M0 (I − Mk ) = 0, (I − M0 )Mk = |1, kih1, k|, we have
E
Wtk −Wt+1
k
≤ hψt0 |1, kih1, k|ψtk i + (I − M0 ) ψt0 (I − Mk ) ψtk
q
0
≤ h1, k|ψt i + εt0 εtk ,
where we used (4.4) in the second inequality. Summing over k and t, we obtain
T −1 N q
0 0 k
W0 −WT ≤ ∑ ∑ h1, k|ψt i + εt εt
t=0 k=1
s v
√ T −1 N N
uT −1 T −1
u
≤ TN ∑ ∑ hψt0 |1, kih1, k|ψt0 i + ∑ t ε0
∑ t ∑ t ε k0
t=0 k=1 k=1 t=0 t 0 =0
s
√ T −1
≤ TN ∑ ψt0 (I − M0 ) ψt0 + Nε
t=0
s
T −1
≤ T N ∑ εt0 + Nε
t=0
√
≤ εT N + Nε
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 13
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
where in the second line we used Cauchy-Schwarz twice, and in the third line we recalled that
T −1
∑ εti ≤ ε
t=0
for all i. Combined with (4.5), this gives
p
(1 − 2 δ (1 − δ ) − ε)2 N
T≥ .
ε
We now proceed to prove the general result. This proof follows the presentation given in A. Childs’s
online lecture notes [15], which we found quite illuminating.
Theorem 4.5. For all functions f with Boolean input alphabet, and numbers ε, δ satisfying 0 < ε ≤ δ ≤
1/10,
Bε,δ ( f ) = Ω(Q0.01 ( f )2 /ε) .
Proof. We prove the lower bound on Bε,δ by showing that it is lower bounded by Ω(Adv± ( f )2 /ε), where
Adv± ( f ) is the generalized (i. e., allowing negative weights) adversary bound [30] for f . We can then
derive our theorem from the result [36] that Q( f ) = O(Adv± ( f )).
We generalize the bound on the f = AND case to an adversary bound for Bε,δ on arbitrary f . Define
the projectors
N
Π0 = ∑ |0, iih0, i| ,
i=1
Πi = |1, iih1, i| , i = 1, · · · , N.
It is clear that
N
Π0 + ∑ Πi = I .
i=1
Note that Mx = CPx,0 is
Mx = Π0 + ∑ Πi .
i:xi =0
Define |ψtx i as the state of the algorithm right before the (t + 1)-th query with input x; then
x
ψt+1 = Ut+1 Mx |ψtx i
for some unitary Ut+1 . Now if we let
εtx = hψtx |(I − Mx )|ψtx i
then it follows that hψtx |ψtx i − hψt+1
x |ψ x i = ε x , and thus
t+1 t
T −1
∑ εtx = hψ0x |ψ0x i − hψTx |ψTx i ≤ ε .
t=0
We proceed to define the progress function. Let D be the set of allowable input strings x. Let Γ be an
adversary matrix, i. e., an |D| × |D| matrix such that
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 14
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
1. Γxy = Γyx ∀x, y ∈ D; and
2. Γxy = 0 if f (x) = f (y).
Let a be the normalized eigenvector of Γ with eigenvalue ±kΓk, where ±kΓk is the largest (by absolute
value) eigenvalue of Γ. Define the progress function
Wt = ∑ Γxy a∗x ay hψtx |ψty i .
x,y∈D
For ε ≤ δ < 1/10 we have that1 (see [30] for a proof; their proof applies equally well to unnormalized
states) p
|W0 −WT | ≥ (1 − 2 δ (1 − δ ) − 2δ )kΓk .
We now proceed to upper bound |W0 −WT | ≤ ∑t |Wt −Wt−1 |. Note that
Wt −Wt+1 = ∑ Γxy a∗x ay hψtx |ψty i − hψt+1
x y
|ψt+1 i
x,y∈D
= ∑ Γxy a∗x ay hψtx |ψty i − hψtx |Mx My ψty
x,y∈D
= ∑ Γxy a∗x ay hψtx |(I − Mx )My ψty + hψtx |Mx (I − My ) ψty + hψtx |(I − Mx )(I − My ) ψty
x,y∈D
(4.6)
We bound the three terms separately. For the first two terms, use
(I − Mx )My = ∑ Πi = (I − Mx ) ∑ Πi .
i:xi =1,yi =0 i:xi 6=yi
Define the |D| × |D| matrix Γi as (
Γxy if xi 6= yi ,
Γi =
0 if xi = yi .
The first term of (4.6) is
N
∑ ∑ Γxy a∗x ay hψtx |(I − Mx )Πi ψty = ∑ ∑ (Γi )xy a∗x ay hψtx |(I − Mx )Πi ψty
x,y∈D i:xi 6=yi x,y∈D i=1
N
= ∑ tr(Qi Γi Q̃†i )
i=1
where
Qi = ∑ ax Πi |ψtx ihx| ,
x∈D
Q̃i = ∑ ax Πi (I − Mx )|ψtx ihx| .
x∈D
1 As described in [30], the 2δ term can be removed if the output is Boolean (0 or 1).
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 15
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
Although both Qi and Q̃i depend on t, we suppress the t dependence in the notation. Similarly, the second
term of (4.6) is equal to
N
∑ tr Q̃i Γi Q†i .
i=1
We can also rewrite the third term of (4.6) as
∑ Γxy a∗x ay hψtx |(I − Mx )(I − My ) ψty = tr(Q0 ΓQ0† )
x,y∈D
where
Q0 = ∑ ax (I − Mx )|ψtx ihx| .
x∈D
Therefore, adding absolute values,
N h i
|Wt −Wt+1 | ≤ ∑ tr(Qi Γi Q̃†i ) + tr(Q̃i Γi Q†i )) + tr(Q0 ΓQ0† ) . (4.7)
i=1
Then by Lemma 2.2,
N N
∑ tr(Qi Γi Q̃†i ) ≤ ∑ kΓi kkQi kF kQ̃i kF . (4.8)
i=1 i=1
We can calculate
N N
∑ kQi k2F = ∑ ∑ |ax |2 kΠi |ψtx ik2
i=1 i=1 x∈D
N
= ∑ |ax |2 hψtx | ∑ Πi |ψtx i
x∈D i=1
2
≤ ∑ |ax |
x∈D
=1
and
N N
∑ kQ̃i k2F = ∑ ∑ |ax |2 kΠi (I − Mx )|ψtx ik2
i=1 i=1 x∈D
!
N
2
=∑ |ax | hψtx |(I − Mx ) ∑ Πi (I − Mx )|ψtx i
x∈D i=1
2
≤∑ |ax | hψt |(I − Mx )|ψtx i
x
x∈D
= ∑ |ax |2 εtx .
x∈D
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 16
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
Then by Cauchy-Schwarz,
N r
∑ kQi kF kQ̃i kF ≤ ∑ |ax |2 εtx . (4.9)
i=1 x∈D
Therefore by (4.8) and (4.9),
N r
∑ tr(Qi Γi Q̃†i ) ≤ ∑ |ax |2 εtx max
i∈[N]
kΓi k .
i=1 x∈D
Similarly for tr(Q0 ΓQ0† ), we have
kQ0 k2F = ∑ |ax |2 k(I − Mx )|ψtx ik2
x∈D
= ∑ |ax |2 hψtx |(I − Mx )|ψtx i
x∈D
= ∑ |ax |2 εtx
x∈D
and using Lemma 2.2,
tr(Q0 ΓQ0† ) ≤ kQ0 k2F kΓk = ∑ |ax |2 εtx kΓk .
x∈D
Thus continuing from (4.7) we have that
r
|Wt −Wt+1 | ≤ 2 ∑ |ax |2 εtx max kΓi k + ∑ |ax |2 εtx kΓk .
x∈D i∈[N] x∈D
Finally, if we sum the above over t we obtain
T −1 r T −1
|W0 −WT | ≤ 2 max kΓi k ∑
i∈[N]
∑ |ax |2 εtx + ∑ ∑ |ax |2 εtx kΓk .
t=0 x∈D t=0 x∈D
The first term can be bounded using Cauchy-Schwarz:
s
T −1 r T −1 √
2ε x ≤
∑ ∑ x t |a | T ∑ ∑ |ax |2 εtx ≤ εT
t=0 x∈D t=0 x∈D
where we used ∑t εtx ≤ ε and ∑x∈D |ax |2 = 1. The second term can be summed easily:
T −1
∑ ∑ |ax |2 εtx kΓk ≤ ∑ |ax |2 εkΓk = εkΓk .
t=0 x∈D x∈D
Therefore √
|W0 −WT | ≤ 2 εT max kΓi k + εkΓk .
i∈[N]
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 17
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
p
Combined with our lower bound |W0 −WT | ≥ (1 − 2 δ (1 − δ ) − 2δ )kΓk, this immediately gives
p
(1 − 2 δ (1 − δ ) − 2δ − ε)2 kΓk2
T≥ .
4ε maxi∈[N] kΓi k2
Recalling from [30] that
kΓk
Adv± ( f ) = max ,
Γ maxi∈[N] kΓi k
we obtain2 p
(1 − 2 δ (1 − δ ) − 2δ − ε)2
T≥ Adv± ( f )2 .
4ε
We now use the tight characterization of the quantum query complexity by the general weight
adversary method, given in [36, Theorem 1.1].
Theorem 4.6 (Lee, Mittal, Reichardt, Špalek, Szegedy). Let f : D → E, D ⊆ {0, 1}N . Then Q0.01 ( f ) =
O(Adv± ( f )).
Combined with our result above, we obtain
Q0.01 ( f )2
Bε,δ ( f ) = Ω .
ε
5 Generalizations and applications
We now discuss applications of the result Bε ( f ) = Θ(Q( f )2 /ε) that could be useful.
5.1 Generalizing the bomb query model
We consider modifying the bomb query model as follows. We require that the input string x can only be
accessed by the following circuit.
|ci • • |ci
|0i bomb explodes if 1
Ox
|ii |ii
|ai •
Compare with Circuit 3.1; the difference is that there is now an extra register |ai, and the bomb explodes
only if both xi 6= a and the control bit is 1. In other words, the bomb explodes if c · (xi ⊕ a) = 1. The three
registers c, i, and a are allowed to be entangled, however. If we discard the second register afterwards,
the effect of this circuit, written as a projector, is
ex =
M ∑ |0, i, aih0, i, a| + ∑ |1, i, aih1, i, a| . (5.1)
i∈[N],a∈{0,1} i,a:xi =a
2 For Boolean output (0 or 1) the 2δ term can be dropped, as we previously noted (Footnote 1).
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 18
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
Let B̃ε,δ ( f ) be the required number of queries to this modified bomb oracle M ex to calculate f (x) with
error not greater than δ , with a probability of explosion not greater than ε. Using Theorem 4.1, we show
that B̃ and B are equivalent up to a constant.
Lemma 5.1. If f : D → E, where D ⊆ {0, 1}N , δ ≤ 1/10 is a constant, and ε ≤ δ is arbitrary, then
Bε,δ ( f ) = Θ(B̃ε,δ ( f )).
Proof. It should be immediately obvious that Bε,δ ( f ) ≥ B̃ε,δ ( f ), since a query in the asymmetric model
can easily be simulated by a query in the symmetric model by simply setting a = 0. In the following we
show that Bε,δ ( f ) = O(B̃ε,δ ( f )).
For each string x ∈ {0, 1}N , define the string x̃ ∈ {0, 1}2N by concatenating two copies of x and
flipping every bit of the second copy. In other words,
(
xi if i ≤ N,
x̃i = (5.2)
1 − xi−N if i > N.
Let D̃ = {x̃ : x ∈ D}. Given a function f : D → {0, 1}, define f˜ : D̃ → {0, 1} by f˜(x̃) = f (x).
We claim that a query in the symmetric model to x can be simulated by a query in the original
asymmetric model to x̃. This can be seen by comparing M ex (Equation (5.1)) and the projector Mx̃ , defined
as follows.
Mx̃ = ∑ 0, ĩ 0, ĩ + ∑ 1, ĩ 1, ĩ .
ĩ∈[2N] ĩ∈[2N]:x̃ĩ =0
Recalling the definition of x̃ in (5.2), we see that these two projectors are exactly equal if we encode ĩ as
(i, a), where i ≡ ĩ mod N and a = bi/Nc.
Since f˜(x̃) = f (x), we thus have B̃ε,δ ( f ) = Bε,δ ( f˜). Our result then readily follows; it can easily be
checked that Q( f ) = Q( f˜), and therefore by Theorem 4.1,
Q( f˜)2 Q( f )2
˜
B̃ε,δ ( f ) = Bε,δ ( f ) = Θ =Θ .
ε ε
There are some advantages to allowing the projector M ex instead of Mx . First of all, the inputs 0 and 1
in x are finally manifestly symmetric, unlike that in Mx (the bomb originally blew up if xi = 1, but not if
xi = 0). Moreover, we now allow the algorithm to guess an answer a to the query xi (this answer may be
entangled with the index register i), and the bomb blows up only in the case c · (a ⊕ i) = 1: the guess is
wrong, and the control bit c is 1. This flexibility may allow more leeway in designing algorithms for the
bomb query model, as we soon utilize.
5.2 Using classical algorithms to design bomb query algorithms
bounds on Q( f ) for some
We now demonstrate the possibility that we can prove non-constructive upper p
functions f , by creating bomb query algorithms and using that Q( f ) = Θ( εBε ( f )). Consider for
example the following classical algorithm for the OR function.
Algorithm 5.2 (Classical algorithm for OR). Pick some arbitrary ordering of the N bits, and query them
one by one, terminating as soon as a 1 is seen. Return 1 if a 1 was seen; otherwise return 0.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 19
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
We can convert this immediately to a bomb query algorithm for OR, by using the construction in the
proof of Theorem 4.3. That construction allows us to implement the operation Ox in O(ε −1 ) queries,
with O(ε) error and probability of explosion if xi = 1, but no error if xi = 0. Thus we have the following
algorithm.
Algorithm 5.3 (Bomb algorithm for OR). Query the N bits one-by-one, and apply the construction of
Theorem 4.3 one bit at a time, using O(1/ε) operations each time. Terminate as soon as a 1 is seen, and
return 1; otherwise return 0 if all bits are 0.
Since the algorithm ends as soon as a 1 is found, the algorithm only accumulates ε error in total. Thus
this shows Bε (OR) = O(N/ε). p
Note, however, that we have already shown that Q( f ) = Θ( √εBε ( f )) for Boolean f . An O(N/ε)
bomb √ query algorithm for OR therefore implies that Q(OR) = O( N). We have shown the existence of
an O( N) quantum algorithm for the OR function, without actually constructing one!
We formalize the intuition in the above argument by the following theorem.
Theorem 5.4. Let f : D → E, where D ⊆ {0, 1}N . Suppose there is a classical randomized query
algorithm A, that makes at most T queries, and evaluates f with bounded error. Let the query results of
A on random seed sA be x p1 , x p2 , . . . , x pT̃ (x) , T̃ (x) ≤ T , where x is the hidden query string.
Suppose there is another (not necessarily time-efficient) randomized algorithm G, with random seed
sG , which takes as input x p1 , . . . , x pt−1 and sA , and outputs a guess for the next query result x pt of A. Note
that G is given the random seed sA of A as well as all past query results, so it can predict the next query
index of A. Assume that G does not make more than an expected total of G mistakes (for all inputs x), i. e.,
( )
T̃ (x)
IEsA ,sG ∑ G(x p , . . . , x p , sA , sG ) − x p
1 t−1 t ≤G ∀x . (5.3)
t=1
√
Then Bε ( f ) = O(T G/ε), and thus (by Theorem 4.1) Q( f ) = O( T G).
As an example, in our simple classical example for OR we have T = N (the algorithm takes at most
N steps) and G = 1 (the guessing algorithm always guesses the next query to be 0; since the algorithm
terminates on a 1, it makes at most one mistake).
Proof. For the purposes of this proof, we use the characterization of B by the modified bomb construction
given in Section 5.1. This proof is substantially similar to that of Theorem 4.3.
The following circuit finds xi with zero probability of explosion if xi = a, and with an O(1/L)
probability of explosion if xi 6= a (in both cases the value of xi found by the circuit is always correct).
|0i R(θ ) R(θ ) X |xi i
...
|ii M
ex M
ex |ii
(5.4)
|ai • |ai
L times in total
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 20
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
where θ = π/(2L) for some large number L to be picked later, and
cos θ − sin θ
R(θ ) = .
sin θ cos θ
ex (R(θ ) ⊗ I ⊗ I)]L , applied to the state |0, i, ai. We can
The boxed part of the circuit is then simply [M
analyze this circuit by breaking into cases.
• If xi = a, then Mex |ψi|i, ai = |ψi|i, ai for any state |ψi in the control register. Thus the operators
Mex act as identities, and the circuit simply applies the rotation R(θ )L = R(π/2) to the control
register, rotating it from 0 to 1. We thus obtain the state |1, i, ai; the final CNOT and X gates add
a ⊕ 1 = xi ⊕ 1 to the first register, giving |xi , i, ai.
• If xi 6= a, then
ex |0, i, ai = |0, i, ai ,
M ex |1, i, ai = 0 .
M
Therefore after each rotation R(θ ), the projection M
ex projects the control qubit back to 0:
ex (cos θ |0i + sin θ |1i)|i, ai = cos θ |0, i, ai (for xi 6= a) .
ex (R(θ ) ⊗ I ⊗ I)|0, i, ai = M
M
In this case the effect of M ex (R(θ ) ⊗ I ⊗ I) is to shrink the amplitude by cos(θ ); L applications
L
results in the state cos (θ )|0, i, ai. The final CNOT and X gates add a ⊕ 1 = xi to the first register,
giving |xi , i, ai.
The probability of explosion is 0 if xi = a. If xi 6= a, the probability of explosion is
π π2
1 − cos2L ≤ .
2L 4L
Pick 2
π G
L= .
4ε
Then the probability of explosion is 0 if xi = a, and not greater than ε/G if xi 6= a. If the bomb does not
explode, then the circuit always finds the correct value of xi .
We now construct the bomb query algorithm based on A and G. The bomb query algorithm follows
A, with each classical query replaced by the above construction. There are at most T L ≈ π 2 T G/(4ε)
bomb queries. At each classical query, we pick the guess a to be the guess provided by G. The bomb only
has a chance of exploding if the guess is incorrect; hence for all x, the total probability of explosion is not
greater than ( )
T̃ (x)
ε
IEs ,s
G A G t=1 ∑ G(x p1 , · · · , x pt−1 , sA , sG ) − x pt ≤ ε .
Thus replacing the classical queries of A with our construction gives a bomb query algorithm with
probability of explosion not greater than ε; aside from the probability of explosion, this bomb algorithm
makes no extra error over the classical algorithm A. The number of queries this algorithm uses is
2
π G
B̃ε,δ +ε ( f ) ≤ T,
4ε
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 21
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
where δ is the error rate of the classical algorithm. Therefore by Lemma 5.1 and Lemma 4.2,
Bε ( f ) = O(Bε,δ +ε ( f )) = O(B̃ε,δ +ε ( f )) = O (T G/ε) .
5.3 Explicit quantum algorithm for Theorem 5.4
In this section we give an explicit quantum algorithm, in the setting of Theorem 5.4, that reproduces the
given query complexity. This algorithm is very similar to the one given by Robin Kothari for the oracle
identification problem [34].
Theorem 5.5. Under√the assumptions of Theorem 5.4, there is an explicit quantum algorithm for f with
query complexity O( T G).
Proof. We will construct this algorithm (Algorithm 5.9) shortly. We need the following quantum search
algorithm as a subroutine.
Theorem 5.6 (Finding the first marked element in a list). Suppose there is an ordered list of N elements,
and each element is either marked or unmarked. Then there is a bounded-error quantum algorithm that
finds the first marked element in the list (or determines that no marked elements exist), such that the
following hold.
√
• If the first marked element is the d-th element of the list, then the algorithm uses an expected O( d)
queries.
√
• If there are no marked elements, then the algorithm uses O( N) queries, but always determines
correctly that no marked elements exist.
This algorithm has been used by Kothari in [34].
Proof. We give an algorithm that has the stated properties. We first recall a quantum algorithm for finding
the minimum in a list of items.
√ a function g : [N] → R, there is a quantum algorithm that finds
Theorem 5.7 (Dürr–Høyer [21]). Given
the minimum of g with expected O( N) evaluations of g, making δ < 1/10 error.
We now give our algorithm for finding the first marked element in a list. For simplicity, assume that
N is a power of 2 (i. e., log2 N is an integer).
Algorithm 5.8.
1. For ` = 20 , 21 , 22 , · · · , 2log2 N = N:
• Find the first marked element within the first ` elements, or determine no marked element
exists. This can be done by defining
(
∞ if i is unmarked,
g(i) =
i if i is marked,
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 22
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
√ √
and using Theorem 5.7 to find the minimum of g. This takes O( `) = O( d) queries and
makes δ < 1/10 error for each `. If a marked element i∗ is found, the algorithm outputs i∗
and stops.
2. If no marked element was found in Step 1, the algorithm decides that no marked element exists.
We now claim that Algorithm 5.8 has the desired properties. Let us break into cases.
• If no marked elements exist, then no marked element can possibly be found in Step 1, so the
algorithm correctly determines that no marked elements exist in Step 2. The number of queries
used is !
log2 N √ √
O ∑ 2i = O( N)
i=0
as desired.
• Suppose the first marked element is the d-th item in the list. Then in Step 1(a), if ` ≥ d, there is at
least a 1 − δ probability that the algorithm will detect that a marked element exists in the first `
elements and stop the loop. Letting α = dlog2 de, the total expected number of queries is thus
! !
α−1 √ √ log2 N √ √
i−α 2α/2 − 1 √ α 1
i
O ∑ 2 + d+ ∑ δ 2 ≤O √
i + 2 √ + d
i=0 i=α 2−1 1 − 2δ
√ √
= O( 2α ) + O( d)
√
= O( d) .
The probability of not finding the marked element at the first ` ≥ d is at most δ , and thus the total
error of the algorithm is bounded by δ .
We now give our explicit quantum algorithm.
Algorithm 5.9 (Simulating a classical query algorithm by a quantum one).
Input. Classical randomized algorithm A that computes f with bounded error. Classical randomized
algorithm G that guesses queries of A. Oracle Ox for the hidden string x.
Output. f (x) with bounded error.
The quantum algorithm proceeds by attempting to produce the list of queries and results that A would
have made. More precisely, given a random seed sA , the quantum algorithm outputs (with constant error)
a list of pairs (p1 (x), x p1 (x) ), . . . , (pTe(x) (x), x pTe(x) (x) ). This list is such that on random seed sA , the i-th
query of algorithm A is made at the position pi (x), and the query result is x pi (x) . The quantum algorithm
then determines the output of A using this list.
The main idea for the algorithm is this. We first assume that the guesses made by G are correct.
By repeatedly feeding the output of G back into A and G, we can obtain a list of query values for A
without any queries to the actual black box. We then search for the first deviation of the string x from the
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 23
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
√
predictions of G; assuming the first deviation is the d1 -th query, by Theorem 5.6 the search takes O( d1 )
queries (ignoring error for now). We then know that all the guesses made by G are correct up to the
(d1 − 1)-th query, and incorrect for the d1 -th query.
With the corrected result of the first d1 queries, we now continue by assuming again the guesses made
by G are correct starting
√ from the (d1 + 1)-th query, and search for the location of the next deviation,
d2 . This takes O( d2 − d1 ) queries; we then know that all the guesses made by G are correct from the
(d1 + 1)-th to (d2 − 1)-th query, and incorrect for the d2 -th one. Continuing in this manner, we eventually
determine all query results of A after an expected G iterations.
We proceed to spell out our algorithm. For the time being, we assume that algorithm for Theorem 5.6
has no error and thus requires no error reduction.
1. Initialize random seeds sA and sG for A and G. We will simulate the behavior of A and G on these
seeds. Initialize d = 0. d is such that we have determined the values of all query results of A up to
the d-th query. Initialize an empty list L of (query position, query result) pairs.
2. Repeat until either all query results of A are determined, or 100G iterations of this loop have been
executed.
(a) Assuming that G always guesses correctly starting from the (d + 1)-th query, compute from A
and G a list of at most T − d query positions pd+1 , pd+2 , . . . and results ãd+1 , ãd+2 , . . .. This
requires no queries to the black box.
(b) Using our algorithm for finding the first marked element (Theorem 5.6, Algorithm 5.8), find
the first index d ∗ > d such that the actual query result of
∗
√A differs from the guess by G, i. e.,
x pd 6= ã√ ∗
d ; or return that no such d exists. This takes O( d − d) queries in the former case,
and O( T − d) queries in the latter.
(c) We break into cases.
i. If an index d ∗ was found in Step 2b, then the algorithm decides the next mistake made by
G is at position d ∗ . It thus adds the pairs (pd+1 , ãd+1 ), . . . , (pd ∗ −1 , ãd ∗ −1 ), and the pair
(pd ∗ , 1 − ãd ∗ ), to the list L. Also set d = d ∗ .
ii. If no index d ∗ was found in Step 2b, the algorithm decides that all remaining guesses
by G are correct. Thus the query pairs (pd+1 , ãd+1 ), . . . , (pT̃ (x) , ãT̃ (x) ) are added to L,
where T̃ (x) ≤ T is the number of queries made by A.
3. If the algorithm found all query results of A in 100G iterations of Step 2, use L to calculate the
output of A; otherwise the algorithm fails.
We now count the total number of queries. Suppose g ≤ 100G is the number of iterations of Step 2; if
all query results have been determined, g is the number of wrong guesses by G. Say the list of indices
d ∗ found is d0 = 0, d1 , . . . , dg . Let dg+1 = T . Step 2 is executed for g + 1 times, and the total number of
queries is !
g+1 p p √
O ∑ di − di−1 = O Tg = O TG
i=1
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 24
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
by the Cauchy-Schwarz inequality.
We now analyze the error in our algorithm. The first source of error is cutting off the loop in Step 2:
by Markov’s inequality, for at least 99% of random seeds sA , sG , G does not make more than 100G wrong
guesses. For these random seeds all query results of A are determined. Cutting off the loop thus gives at
most 0.01 error.
The other source of error is the error of Algorithm 5.8 used in Step 2b: we had assumed that it could
be treated as zero-error, but we now remove this assumption. Assuming each iteration gives error δ 0 , the
total error accrued could be up to O(gδ 0 ). It seems as if we would need to set δ 0 = O(1/G) for the total
error to be constant, and thus gain an extra logarithmic factor in the query complexity.
However, in his paper for oracle identification [34], Kothari showed that multiple calls to Algo-
rithm 5.8 can be composed to obtain a bounded-error algorithm based on span programs without an extra
logarithmic factor in the query complexity; we refer to [34, Section 3] for the details. Therefore we
can replace the iterations of Step
√ 2 with Kothari’s span program construction and get a bounded error
algorithm with complexity O( T G).
√
Note that while Algorithm 5.9 has query complexity O( T G), the time complexity may be much
higher. After all, Algorithm 5.9 proceeds by simulating A query-by-query, although the number of actual
queries to the oracle is smaller. Whether or not we can get an algorithm faster than A using this approach
may depend on the problem at hand.
6 Improved upper bounds on quantum query complexity
We now use Theorem 5.5 to improve the quantum query complexity of certain graph problems.
6.1 Single source shortest paths for unweighted graphs
Problem 6.1 (Single source shortest paths (SSSP) for unweighted graphs). The adjacency matrix of a
directed n-vertex graph G is provided as a black box; a query on the pair (v, w) returns 1 if there is an
edge from v to w, and 0 otherwise. We are given a fixed vertex vstart . Call the length of a shortest path
from vstart to another vertex w the distance dw of w from vstart ; if no path exists, define dw = ∞. Our task
is to find dw for all vertices w in G.
In this section we shall show the following result.
Theorem 6.2. The quantum query complexity of single-source shortest paths in an unweighted graph is
Θ(n3/2 ) in the adjacency matrix model.
Proof. The lower bound of Ω(n3/2 ) is known [20]. We show the upper bound by applying Theorem 5.5
to a classical algorithm. The following well-known classical algorithm (commonly known as breadth first
search, BFS) solves this problem.
Algorithm 6.3 (Classical algorithm for unweighted SSSP).
1. Initialize dw := ∞ for all vertices w 6= vstart , dvstart := 0, and L := (vstart ). L is the ordered list
of vertices for which we have determined the distances, but whose outgoing edges we have not
queried.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 25
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
2. Repeat until L is empty:
• Let v be the first (in order of time added to L) vertex in L. For all vertices w such that dw = ∞:
– Query (v, w).
– If (v, w) is an edge, set dw := dv + 1 and add w to the end of L.
• Remove v from L.
We omit the proof of correctness of this algorithm (see for example [17]). This algorithm uses up to
T = O(n2 ) queries. If the guessing algorithm
√ always guesses that (v, w) is not an edge, then it makes at
most G = n − 1 mistakes; hence Q( f ) = O( T G) = O(n3/2 ).3
The previous best known quantum algorithm for unweighted SSSP, to our best knowledge, was given
by Furrow [24]; that algorithm has query complexity O(n3/2 log n).
We now consider the quantum query complexity of unweighted k-source shortest paths (finding k
shortest-path trees rooted from k beginning vertices). If we apply Algorithm 6.3 on k different starting
vertices, then the expected number of wrong guesses is not greater than G = k(n − 1); however, the total
number of edges we query need not exceed T = O(n2 ), since an edge never needs to be queried more
than once. Therefore
Corollary 6.4. The quantum query complexity of unweighted k-source shortest paths in the adjacency
matrix model is O(k1/2 n3/2 ), where n is the number of vertices.
We use this idea—that T need not exceed O(n2 ) when dealing with graph problems – again in the
following section.
6.2 Maximum bipartite matching
Problem 6.5 (Maximum bipartite matching). We are given as black box the adjacency matrix of an
n-vertex bipartite graph G = (V = X ∪Y, E), where the undirected set of edges E only run between the
bipartite components X and Y . A matching of G is a list of edges of G that do not share vertices. Our task
is to find a maximum matching of G, i. e., a matching that contains the largest possible number of edges.
In this section we show that
Theorem 6.6. The quantum query complexity of maximum bipartite matching is O(n7/4 ) in the adjacency
matrix model, where n is the number of vertices.
Proof. Once again we apply Theorem 5.5 to a classical algorithm. Classically, this problem is solved
in O(n5/2 ) time by the Hopcroft-Karp [26] algorithm (here n = |V |). We summarize the algorithm as
follows. (This summary roughly follows that of [5].)
Algorithm 6.7 (Hopcroft-Karp algorithm for maximum bipartite matching [26]).
1. Initialize an empty matching M. M is a matching that will be updated until it is maximum.
3 It seems difficult to use our method to give a corresponding result for the adjacency list model; the result of a query is much
harder to guess when the input alphabet is non-Boolean.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 26
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
2. Repeat the following steps until M is a maximum matching:
(a) Define the directed graph H = (V 0 , E 0 ) as follows:
V 0 = X ∪Y ∪ {s,t} ,
E 0 = {(s, x) | x ∈ X, (x, y) 6∈ M for all y ∈ Y }
∪ {(x, y) | x ∈ X, y ∈ Y, (x, y) ∈ E, (x, y) 6∈ M}
∪ {(y, x) | x ∈ X, y ∈ Y, (x, y) ∈ E, (x, y) ∈ M}
∪ {(y,t) | y ∈ Y, (x, y) 6∈ M for all x ∈ X}
where s and t are two extra auxiliary vertices. Note that if (s, x1 , y1 , x2 , y2 , . . . , x` , y` ,t) is a
path in H from s to t, then xi ∈ X and yi ∈ Y for all i. Additionally, the edges (aside from
the first and last) alternate from being in M and not being in M: (xi , yi ) 6∈ M, (yi , xi+1 ) ∈ M.
Such a path is called an augmenting path in the literature.
We note that a query to the adjacency matrix of E 0 can be simulated by a query to the
adjacency matrix of E.
(b) Using the breadth-first search algorithm (Algorithm 6.3), in the graph H, find the length of
the shortest path, or distance, of all vertices from s. Let the distance from s to t be 2` + 1.
(c) Find a maximal set S of vertex-disjoint shortest paths from s to t in the graph H. In other
words, S should be a list of paths from s to t such that each path has length 2` + 1, and no
pair of paths share vertices except for s and t. Moreover, all other shortest paths from s to t
share at least one vertex (except for s and t) with a path in S. We describe how to find such a
maximal set in Algorithm 6.8.
(d) If S is empty, i. e., there are no paths from s to t in the graph H, then it follows that M is a
maximum matching, and we terminate. Otherwise continue to Step 2(e):
(e) Let (s, x1 , y1 , x2 , y2 , . . . , x` , y` ,t) be a path in S. Remove the ` − 1 edges (xi+1 , yi ) from M, and
insert the ` edges (xi , yi ) into M. This increases |M| by 1. Repeat for all paths in S; there are
no conflicts since the paths in S are vertex-disjoint.
Once again, we omit the proof of correctness of this algorithm; the correctness is guaranteed by
Berge’s Lemma [10], which states that a matching is maximum if there are no more augmenting paths for
√
the matching. Moreover, O( n) iterations of Step 2 suffice [26].
We now describe how to find a maximal set of shortest-length augmenting paths in Step 2(c). This
algorithm is essentially a modified version of depth-first search.
Algorithm 6.8 (Finding a maximal set of vertex-disjoint shortest-length augmenting paths).
Input. The directed graph H defined in Algorithm 6.7, as well as the distances dv of all vertices v from s
(calculated in Step 2(b) of Algorithm 6.7).
/ set of vertices R := {s}, and a stack4 of vertices L := (s). L contains
1. Initialize a set of paths S := 0,
the ordered list of vertices that we have begun, but not yet finished, processing. R is the set of
4 A stack is a data structure such that elements that are first inserted into the stack are removed last. We say that the last
vertex added to (and still in) the stack is at the top of the stack; removing the top element is popping from the stack.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 27
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
vertices that we have processed. S is the set of vertex-disjoint shortest-length augmenting paths
that we have found.
2. Repeat until L is empty:
(a) If the top vertex of L (i. e., the last vertex added to, and still in, L) is t, we have found a new
vertex-disjoint path from s to t:
• Trace the path from t back to s by removing elements from the front of L until s is at the
front. Add the corresponding path to S.
• Start again from the beginning of Step 2.
(b) Let v be the top vertex of L (i. e., the vertex last added to, and still in, L). Recall the distance
from s to v is dv .
(c) Find w such that w 6∈ R, dw = dv + 1, and (v, w) (as an edge in H) has not been queried in
this algorithm. If no such vertex w exists, pop (remove) v from L and start from the beginning
of Step 2.
(d) Query (v, w) on the graph H.
(e) If (v, w) is an edge, push w into L. If w 6= t, add w to R.
3. Output S, the maximal set of vertex-disjoint shortest-length augmenting paths.
We now return to Algorithm 6.7 and count T and G. There is obviously no need to query the same
edge more than once, so T = O(n2 ). If the algorithm always guesses, on a query (v, w), that there is no
edge between (v, w), then it makes at most G = O(n3/2 ) mistakes: in Step 2(b) there are at most O(n)
mistakes (see Algorithm 6.3), while in Step 2(c)/Algorithm 6.8 for each vertex v 6= t there is at most one
queried edge pointing to v, and edges pointing to t can be computed without queries to the adjacency
√
matrix of H. Since Step 2 is executed O( n) times, our counting follows.
√
Thus there is a quantum query algorithm with complexity Q = O( T G) = O(n7/4 ).
To our knowledge, this is the first known nontrivial upper bound on the query complexity of maximum
bipartite matching.5 The time complexity of this problem was studied by Ambainis and Špalek in [5];
they gave an upper bound of O(n2 log n) time in the adjacency matrix model. A lower bound of Ω(n3/2 )
for the query complexity of this problem was given in [11, 54].
For readers familiar with network flow, the arguments in this section also apply to Dinic’s algorithm
for maximum flow [18] on graphs with unit capacity, i. e., where the capacity of each edge is 0 or 1.
On graphs with unit capacity, Dinic’s algorithm is essentially the same as Hopcroft-Karp’s, except that
augmenting paths are over a general, nonbipartite flow network. (The set S in Step 2(c) of Algorithm 6.7
is generally referred to as a blocking flow in this context.) It can be shown that only O(min{m1/2 , n2/3 })
iterations of Step 2 are required [32, 23], where m is the number of edges of the graph. Thus T = O(n2 ),
G = O(min{m1/2 , n2/3 }n), and therefore
Theorem 6.9. The quantum query complexity of the maximum flow problem in graphs with unit capacity is
O(min{n3/2 m1/4 , n11/6 }), where n and m are the number of vertices and edges in the graph, respectively.
5 The trivial upper bound is O(n2 ), where all pairs of vertices are queried.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 28
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
It is an open question whether a similar result for maximum matching in a general nonbipartite graph
can be proven, perhaps by applying Theorem 5.5 to the classical algorithm of Micali and Vazirani [39].
7 Projective query complexity
We end this paper with a brief discussion on another query complexity model, which we will call the
projective query complexity. This model is similar to the bomb query model in that the only way of
accessing xi is through a classical measurement; however, in the projective query model the algorithm
does not terminate if a 1 is measured. Our motivation for considering the projective query model is that
its power is intermediate between the classical and quantum query models. To the best of our knowledge,
this model was first considered in 2002 in unpublished results by Scott Aaronson [1].
A circuit in the projective query complexity model is a restricted quantum query circuit, with the
following restrictions on the use of the quantum oracle.
1. We have an extra control register |ci used to control whether Ox is applied (we call the controlled
version COx ):
COx |c, r, ii = |c, r ⊕ (c · xi ), ii .
where · indicates Boolean AND.
2. The record register, |ri in the definition of COx above, must contain |0i before COx is applied.
3. After COx is applied, the record register is immediately measured in the computational basis, giving
the answer c · xi . The result, a classical bit, can then be used to control further quantum unitaries
(although only controlling the next unitary is enough, since the classical bit can be stored).
|ci • |ci
|0i c · xi (7.1)
Ox
|ii |ii
We wish to evaluate a function f (x) with as few calls to this projective oracle as possible. Let the number
of oracle calls required to evaluate f (x), with at most δ error, be Pδ ( f ). By gap amplification, the choice
of δ affects Pδ ( f ) by at most a factor of log(1/δ ), and thus we will often omit δ .
We can compare the definition in this section with the definition of the bomb query complexity in
Section 3; the only difference is that if c · xi = 1, the algorithm terminates in the bomb model, while the
algorithm can continue in the projective model. Therefore the following is evident.
Observation 7.1. Pδ ( f ) ≤ Bε,δ ( f ), and therefore P( f ) = O(Q( f )2 ).
Moreover, it is clear that the projective query model has power intermediate between classical and
quantum (a controlled query in the usual quantum query model can be simulated by appending a 0 to the
input string), and therefore letting Rδ ( f ) be the classical randomized query complexity,
Observation 7.2. Qδ ( f ) ≤ Pδ ( f ) ≤ Rδ ( f ).
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 29
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
For explicit bounds on P, Regev and Schiff [46] have shown that for computing the OR function, the
projective query complexity loses the Grover speedup.6
Theorem 7.3 (Regev–Schiff). P(OR) = Ω(N).
Note that this result says nothing about P(AND), since the definition of P( f ) is asymmetric with
respect to 0 and 1 in the input—in Circuit 7.1 the bit c · xi is measured, and this is asymmetric with respect
to xi being 0 and 1.7
We observe that there could be a separation in both parts of the inequality Q ≤ P ≤ B.
√
Q(OR) = Θ( N), P(OR) = Θ(N), B(OR) = Θ(N)
Q(PARITY) = Θ(N), P(PARITY) = Θ(N), B(PARITY) = Θ(N 2 ) .
In the latter equation we used the fact that Q(PARITY) = Θ(N) [6]. It therefore seems difficult to adapt
our lower bound method in Section 4.2 to P( f ).
It is also worth noting that Ben-David recently discovered a total function f such that R( f ) =
Ω̃(Q( f )2.5 ) [8, 2] , and thus R( f ) = Ω̃(P( f )1.125 ). A separation between R and P is therefore possible
even for total functions—this fact is perhaps surprising considering the separation between P(OR) and
Q(OR), i. e., that Grover’s algorithm breaks down in the projective query model.
It would be interesting to find a general lower bound for P( f ), or to establish more clearly the
relationship between Q( f ), P( f ), and R( f ).
Acknowledgements
We are grateful to Scott Aaronson and Aram Harrow for many useful discussions, and Scott Aaronson
and Shelby Kimmel for valuable suggestions on a preliminary draft. We also thank Andrew Childs
for giving us permission to make use of his online proof of the general adversary lower bound in [15].
Special thanks to Robin Kothari for pointing us to his paper [34], and in particular his analysis showing
that logarithmic factors can be removed from the query complexity of Algorithm 5.9. We also thank the
anonymous referees from QIP, CCC, and ToC for their helpful comments. This work is supported by the
ARO grant Contract Number W911NF-12-0486. CYL gratefully acknowledges support from the Natural
Sciences and Engineering Research Council of Canada.
References
[1] S COTT A ARONSON: Personal communication, 2014. 3, 29
6 More precisely, Regev and Schiff [46] studied the following oracle model for the Grover problem: for each oracle application
with probability (1 − p) the oracle is applied correctly, and with probability p the identity is applied instead. Claim 2 in their
paper shows that for p = 1/2, their model is equivalent to the projective query model.
7 We could have defined a symmetric version of P, say P̃, by allowing an extra guess on the measurement result, similar to
our construction of B̃ in Section 5.1. Unfortunately, Regev and Schiff’s result, Theorem 7.3, does not apply to this case, and we
see no obvious equivalence between P and P̃.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 30
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
[2] S COTT A ARONSON , S HALEV B EN -DAVID , AND ROBIN KOTHARI: Separations in query
complexity using cheat sheets. In Proc. 48th STOC, pp. 863–876. ACM Press, 2016.
[doi:10.1145/2897518.2897644, arXiv:1511.01937] 4, 30
[3] A NDRIS A MBAINIS: Quantum lower bounds by quantum arguments. J. Comput. System Sci.,
64(4):750–767, 2002. Preliminary version in STOC’00. [doi:10.1006/jcss.2002.1826, arXiv:quant-
ph/0002066] 2, 13
[4] A NDRIS A MBAINIS: Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210–
239, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447311, arXiv:quant-
ph/0311001] 2
[5] A NDRIS A MBAINIS AND ROBERT Š PALEK: Quantum algorithms for matching and network flows.
In Proc. 23rd Symp. Theoretical Aspects of Comp. Sci. (STACS’06), volume 3884 of LNCS, pp.
172–183. Springer, 2006. [doi:10.1007/11672142_13, arXiv:quant-ph/0508205] 3, 4, 26, 28
[6] ROBERT B EALS , H ARRY B UHRMAN , R ICHARD C LEVE , M ICHELE M OSCA , AND RONALD
DE W OLF : Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary
version in FOCS’98. [doi:10.1145/502090.502097, arXiv:quant-ph/9802049] 2, 4, 30
[7] A LEKSANDRS B ELOVS: Span programs for functions with constant-sized 1-certificates: extended
abstract. In Proc. 44th STOC, pp. 77–84. ACM Press, 2012. [doi:10.1145/2213977.2213985,
arXiv:1105.4024] 2
[8] S HALEV B EN -DAVID: A super-Grover separation between randomized and quantum query com-
plexities. Electron. Colloq. on Comput. Complex. (ECCC), 2015. ECCC. [arXiv:1506.08106] 4,
30
[9] C HARLES H. B ENNETT, E THAN B ERNSTEIN , G ILLES B RASSARD , AND U MESH V. VAZIRANI:
Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997.
[doi:10.1137/S0097539796300933, arXiv:quant-ph/9701001] 2
[10] C LAUDE B ERGE: Two theorems in graph theory. Proc. Nat. Acad. Sci. U.S.A., 43(9):842–844,
1957. [doi:10.1073/pnas.43.9.842] 27
[11] A IJA B ERZINA , A NDREJ D UBROVSKY, RUSINS F REIVALDS , L ELDE L ACE , AND O KSANA
S CEGULNAJA: Quantum query complexity for some graph problems. In Proc. 30th Conf. Current
Trends Theory and Pract. Comput. Sci. (SOFSEM’04), volume 2932 of LNCS, pp. 140–150. Springer,
2004. [doi:10.1007/978-3-540-24618-3_11] 28
[12] R AJENDRA B HATIA: Matrix Analysis. Springer, 1997. [doi:10.1007/978-1-4612-0653-8] 5
[13] A HARON B RODUTCH , DANIEL NAGAJ , O R S ATTATH , AND D OMINIQUE U NRUH: An adap-
tive attack on Wiesner’s quantum money. Quantum Inf. Comput., 16(11&12):1048–1070, 2016.
[arXiv:1404.1507] 3
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 31
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
[14] H ARRY B UHRMAN AND RONALD DE W OLF: Complexity measures and decision tree complexity:
a survey. Theoret. Comput. Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X] 4
[15] A NDREW C HILDS: The adversary method, 2013. Available at author’s website. 5, 14, 30
[16] S TEPHEN A. C OOK , C YNTHIA DWORK , AND R ÜDIGER R EISCHUK: Upper and lower time bounds
for parallel random access machines without simultaneous writes. SIAM J. Comput., 15(1):87–97,
1986. [doi:10.1137/0215006] 4
[17] T HOMAS H. C ORMEN , C HARLES E. L EISERSON , RONALD L. R IVEST, AND C LIFFORD S TEIN:
Introduction to Algorithms (3. ed.). MIT Press, 2009. Available at publisher’s website. 26
[18] Y EFIM A. D INITZ: Algorithm for solution of a problem of maximum flow in a network with power
estimation. Soviet Math. Doklady, 11(5):1277–1280, 1970. Available at author’s website. 28
[19] S EBASTIAN D ÖRN: Quantum algorithms for matching problems. Theory Comput. Syst., 45(3):613–
628, 2009. [doi:10.1007/s00224-008-9118-x] 3
[20] C HRISTOPH D ÜRR , M ARK H EILIGMAN , P ETER H ØYER , AND M EHDI M HALLA: Quantum query
complexity of some graph problems. SIAM J. Comput., 35(6):1310–1328, 2006. Preliminary version
in ICALP’04. [doi:10.1137/050644719, arXiv:quant-ph/0401091] 25
[21] C HRISTOPH D ÜRR AND P ETER H ØYER: A quantum algorithm for finding the minimum, 1996.
[arXiv:quant-ph/9607014] 3, 22
[22] AVSHALOM C. E LITZUR AND L EV VAIDMAN: Quantum mechanical interaction-free measure-
ments. Found. Phys., 23(7):987–997, 1993. [doi:10.1007/BF00736012, arXiv:hep-th/9305002] 2,
5
[23] S HIMON E VEN AND ROBERT E NDRE TARJAN: Network flow and testing graph connectivity. SIAM
J. Comput., 4(4):507–518, 1975. Preliminary version in STOC’74. [doi:10.1137/0204043] 28
[24] BARTHOLOMEW F URROW: A panoply of quantum algorithms. Quantum Inf. Comput., 8(8):834–
859, 2008. ACM DL. [arXiv:quant-ph/0606127] 3, 26
[25] L OV K. G ROVER: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC,
pp. 212–219. ACM Press, 1996. [doi:10.1145/237814.237866, arXiv:quant-ph/9605043] 2
[26] J OHN E. H OPCROFT AND R ICHARD M. K ARP: An n5/2 algorithm for maximum matchings
in bipartite graphs. SIAM J. Comput., 2(4):225–231, 1973. Preliminary version in SWAT’71.
[doi:10.1137/0202019] 26, 27
[27] O NUR H OSTEN AND PAUL G. K WIAT: Weak measurements and counterfactual computation, 2006.
[arXiv:quant-ph/0612159] 3
[28] O NUR H OSTEN , M ATTHEW T. R AKHER , J ULIO T. BARREIRO , N ICHOLAS A. P ETERS , AND
PAUL G. K WIAT: Counterfactual computation revisited, 2006. [arXiv:quant-ph/0607101] 3
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 32
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
[29] O NUR H OSTEN , M ATTHEW T. R AKHER , J ULIO T. BARREIRO , N ICHOLAS A. P ETERS , AND
PAUL G. K WIAT: Counterfactual quantum computation through quantum interrogation. Nature,
439:949–952, 2006. [doi:10.1038/nature04523] 3
[30] P ETER H ØYER , T ROY L EE , AND ROBERT Š PALEK: Negative weights make adversaries stronger.
In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867, arXiv:quant-
ph/0611054] 2, 14, 15, 18
[31] S TACEY J EFFERY, ROBIN KOTHARI , AND F RÉDÉRIC M AGNIEZ: Nested quantum walks with
quantum data structures. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13),
pp. 1474–1485. ACM Press, 2013. [doi:10.1137/1.9781611973105.106, arXiv:1210.1199] 2
[32] A LEXANDER V. K ARZANOV: O nakhozhdenii maksimal’nogo potoka v setyakh spetsial’nogo vida
i nekotorykh prilozheniyakh (“On finding maximum flow in networks of a special kind and in certain
applications,” in Russian). In Matematicheskie Voprosy Upravleniya Proizvodstvom (Mathematical
Questions of Management), volume 5, pp. 81–94. Moscow State Univ. Press, 1973. 28
[33] S HELBY K IMMEL: Quantum adversary (upper) bound. Chicago J. Theor. Comput. Sci., 2013(4),
2013. Preliminary version in ICALP’12. [doi:10.4086/cjtcs.2013.004, arXiv:1101.0797] 2
[34] ROBIN KOTHARI: An optimal quantum algorithm for the oracle identification problem. In Proc.
31st Symp. Theoretical Aspects of Comp. Sci. (STACS’14), volume 25 of LIPIcs, pp. 482–493.
Schloss Dagstuhl, 2014. [doi:10.4230/LIPIcs.STACS.2014.482, arXiv:1311.7685] 3, 22, 25, 30
[35] PAUL K WIAT, H ARALD W EINFURTER , T HOMAS H ERZOG , A NTON Z EILINGER , AND
M ARK A. K ASEVICH: Interaction-free measurement. Phys. Rev. Lett., 74(24):4763–4766, 1995.
[doi:10.1103/PhysRevLett.74.4763] 2, 3, 6, 9
[36] T ROY L EE , R AJAT M ITTAL , B EN W. R EICHARDT, ROBERT Š PALEK , AND M ARIO S ZEGEDY:
Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp.
Soc. Press, 2011. [doi:10.1109/FOCS.2011.75, arXiv:1011.3020] 2, 14, 18
[37] C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN: Upper bounds on quantum query complexity
inspired by the Elitzur-Vaidman bomb tester. In Proc. 30th IEEE Conf. on Computational Complexity
(CCC’15), pp. 537–566. IEEE Comp. Soc. Press, 2015. [doi:10.4230/LIPIcs.CCC.2015.537,
arXiv:1410.0932] 1
[38] F RÉDÉRIC M AGNIEZ , A SHWIN NAYAK , J ÉRÉMIE ROLAND , AND M IKLOS S ANTHA: Search
via quantum walk. SIAM J. Comput., 40(1):142–164, 2011. Preliminary version in STOC’07.
[doi:10.1137/090745854, arXiv:quant-ph/0608026] 2
p
[39] S ILVIO M ICALI AND V IJAY V. VAZIRANI: An O( |V | · |E|) algorithm for finding maximum
matching in general graphs. In Proc. 21st FOCS, pp. 17–27. IEEE Comp. Soc. Press, 1980.
[doi:10.1109/SFCS.1980.12] 4, 29
[40] BAIDYANATH M ISRA AND E. C. G EORGE S UDARSHAN: The Zeno’s paradox in quantum theory.
J. Math. Phys., 18(4):756–763, 1977. [doi:10.1063/1.523304] 2, 6, 9
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 33
C EDRIC Y EN -Y U L IN AND H AN -H SUAN L IN
[41] G RAEME M ITCHISON AND R ICHARD J OZSA: Counterfactual computation. Proc. Royal Soc. A,
457(2009):1175–1194, 2001. [doi:10.1098/rspa.2000.0714, arXiv:quant-ph/9907007] 3
[42] G RAEME M ITCHISON AND R ICHARD J OZSA: The limits of counterfactual computation, 2006.
[arXiv:quant-ph/0606092] 3
[43] M ICHAEL A. N IELSEN AND I SAAC L. C HUANG: Quantum Computation and Quantum Information.
Cambridge Univ. Press, 2000. 4
[44] N OAM N ISAN: CREW PRAMs and decision trees. SIAM J. Comput., 20(6):999–1007, 1991.
Preliminary version in STOC’89. [doi:10.1137/0220062] 4
[45] TAE -G ON N OH: Counterfactual quantum cryptography. Phys. Rev. Lett., 103(23):230501, 2009.
[doi:10.1103/PhysRevLett.103.230501, arXiv:0809.3979] 3
[46] O DED R EGEV AND L IRON S CHIFF: Impossibility of a quantum speed-up with a faulty oracle. In
Proc. 35th Internat. Colloq. on Automata, Languages and Programming (ICALP’08), volume 5125
of LNCS, pp. 773–781. Springer, 2008. [doi:10.1007/978-3-540-70575-8_63, arXiv:1202.1027] 3,
4, 30
[47] B EN W. R EICHARDT: Span programs and quantum query complexity: The general adversary bound
is nearly tight for every boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc.
Press, 2009. [doi:10.1109/FOCS.2009.55, arXiv:0904.2759] 2
[48] B EN W. R EICHARDT: Reflections for quantum query algorithms. In Proc. 22nd Ann.
ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. ACM Press, 2011.
[doi:10.1137/1.9781611973082.44, arXiv:1005.1601] 2
[49] H ATIM S ALIH , Z HENG -H ONG L I , M. A L -A MRI , AND M. S UHAIL Z UBAIRY: Protocol
for direct counterfactual quantum communication. Phys. Rev. Lett., 110(17):170502, 2013.
[doi:10.1103/PhysRevLett.110.170502, arXiv:1206.2042] 3
[50] M ARIO S ZEGEDY: Quantum speed-up of Markov chain based algorithms. In Proc. 45th FOCS, pp.
32–41. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.53] 2
[51] L EV VAIDMAN: The impossibility of the counterfactual computation for all possible outcomes. Phys.
Rev. Lett., 98(16):160403, 2007. [doi:10.1103/PhysRevLett.98.160403, arXiv:quant-ph/0610174] 3
[52] L EV VAIDMAN: Comment on “Protocol for direct counterfactual quantum communication”. Phys.
Rev. Lett., 112(20):208901, 2014. [doi:10.1103/PhysRevLett.112.208901, arXiv:1304.6689] 3
[53] S TEPHEN W IESNER: Conjugate coding. ACM SIGACT News, 15(1):78–88, 1983.
[doi:10.1145/1008908.1008920] 3
[54] S HENGYU Z HANG: On the power of Ambainis lower bounds. Theoret. Comput. Sci., 339(2-
3):241–256, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.01.019, arXiv:quant-
ph/0311060] 28
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 34
Q UANTUM Q UERY C OMPLEXITY B OUNDS I NSPIRED BY THE E LITZUR –VAIDMAN B OMB T ESTER
AUTHORS
Cedric Yen-Yu Lin
Joint Center for Quantum Information and Computer Science
University of Maryland, College Park, MD
cedricl umiacs umd edu
Han-Hsuan Lin
Centre for Quantum Technologies
National University of Singapore, Singapore
han manatsummit gmail com
ABOUT THE AUTHORS
C EDRIC Y EN -Y U L IN received his Ph. D. in Physics from MIT in 2015, under the super-
vision of Edward Farhi. His research interests are quantum algorithms and complexity,
including query complexity, quantum algorithms for algebraic problems, Hamiltonian
complexity, and quantum structural complexity. He is currently a postdoctoral fellow at
the Joint Center for Quantum Information and Computer Science at the University of
Maryland.
H AN -H SUAN L IN received his Ph. D. from MIT in 2015 under the supervision of Edward
Farhi. His research interests include quantum algorithms and quantum query complexity.
He currently holds a short-term postdoctoral position at the Institute of Information
Science, Academia Sinica in Taiwan. He will join the Centre for Quantum Technologies
in Singapore on December 2, 2016 as a research fellow.
This work was completed while the authors were at the Center for Theoretical Physics, MIT.
T HEORY OF C OMPUTING, Volume 12 (18), 2016, pp. 1–35 35