Authors Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David Yonge-Mallo,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 119–123
www.theoryofcomputing.org
NOTE
Discrete-Query Quantum Algorithm
for NAND Trees
Andrew M. Childs Richard Cleve Stephen P. Jordan
David Yonge-Mallo
Received: September 30, 2008; published: July 1, 2009.
Abstract: This is a comment on the article “A Quantum Algorithm for the Hamiltonian
NAND Tree” by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, Theory of Comput-
ing 4 (2008) 169–190.
√ That paper gave a quantum algorithm for evaluating NAND trees with
running time O( N) in the Hamiltonian query model. In this note, we point out that their
algorithm can be converted into an algorithm using N 1/2+o(1) queries in the conventional
(discrete) quantum query model.
ACM Classification: F.1.2, F.2.2
AMS Classification: 68Q10, 81P68
Key words and phrases: Quantum computation, quantum query complexity, formula evaluation, quan-
tum walk, Hamiltonian simulation
A NAND tree of depth n is a balanced binary tree whose internal vertices represent NAND gates. Placing
bits x1 , . . . , x2n at the leaves, the root of the NAND tree evaluates to the function fn (x1 , . . . , x2n ), where
n
fn : {0, 1}2 → {0, 1} is defined recursively as follows. For n = 0, f0 (x) = x, and for n > 0,
fn (x1 , . . . , x2n ) = ¬ fn−1 (x1 , . . . , x2n−1 ) ∧ fn−1 (x2n−1 +1 , . . . , x2n ) . (1)
The goal of the NAND tree problem is to evaluate fn (x1 , . . . , x2n ), making as few queries to the bits
x1 , . . . , x2n as possible. The optimal classical randomized algorithm for this problem makes Θ(N 0.753 )
queries, where N = 2n [9, 10, 11]. Until √ now, no better quantum algorithm was known, whereas the best
known quantum lower bound is only Ω( N) [2]. Here we show the following.
2009 Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2009.v005a005
A NDREW M. C HILDS , R ICHARD C LEVE , S TEPHEN P. J ORDAN , AND DAVID YONGE -M ALLO
Theorem.√ The bounded-error quantum query complexity of evaluating balanced binary NAND trees is
N 1/2+O(1/ log N) .
Very recently, Farhi,
√ Goldstone, and Gutmann [6] proposed a quantum algorithm that evaluates
NAND trees in time O( N), albeit in the unconventional Hamiltonian oracle model [7, 8] rather than
the conventional quantum query model. In their version of the Hamiltonian oracle model, we are given
access to a Hamiltonian HO acting on n + 1 qubits as
HO |b, ki = −xk |¬b, ki (2)
for all b ∈ {0, 1} and k ∈ {0, 1}n , and the goal is to perform the computation using evolution according
to HO + HD (t) for as short a time as possible, where HD (t) is an arbitrary driving Hamiltonian (that is
possibly time-dependent and may act on an extended Hilbert space).
In the conventional quantum query model, the input is accessible via unitary operations of the form
UO |k, ai = |k, a ⊕ xk i , (3)
again acting on n + 1 qubits. Two queries of UO can be used to implement evolution according to HO
for an arbitrary time t, which can be seen as follows. The procedure acts on states of the form |b, k, ai
(where the last register is an ancilla qubit) as follows. First, apply UO to the second and third registers.
Then apply a controlled-R(t) gate with the first register as the target and the third register as the control,
where
cost i sint
R(t) = . (4)
i sint cost
Finally, apply UO to the second and third registers again. With the ancilla qubit initially in the |0i state,
the net effect of this procedure is the mapping |b, k, 0i 7→ cos(xk t)|b, k, 0i + i sin(xk t)|¬b, k, 0i, which
corresponds to evolution by HO for time t (that is, the unitary operation e−iHOt ).
This simulation of HO does not imply that any fast algorithm in the Hamiltonian oracle model can
be turned into an algorithm with small query complexity in the conventional quantum query model.
Accurate simulation of the evolution according to HO + HD (t) apparently requires many interleaved
evolutions of HO and HD (t) each for a small time, yet each of which requires two unitary queries to
simulate. Nevertheless, it turns out that a Hamiltonian of the kind used in [6] can be simulated in the
conventional quantum query model with only small overhead.
Proof of Theorem. In the algorithm of [6], HD (t) is time-independent, so the evolution for time t is given
by e−i(HO +HD )t . Such evolution according to a sum of time-independent Hamiltonians can be simulated
using a high-order approximation of the exponential of a sum in terms of a product of exponentials of the
individual terms. As noted in [3, 4], by using a pth order approximation, the simulation can be performed
with error at most ε in at most
52p (2ht)1+1/2p
2 (5)
ε 1/2p
steps, where h = kHO + HD k ≤ 3. This yields a simulation with bounded error in O(t 1+1/2p ) steps for
any positive integer p, where the constant implied by the √ big O notation depends on ε and p. Moreover,
√ 1+O(1/ logt) on the number of steps. Since the algorithm
setting p = logt in Eq. 5, we obtain
√ the bound t
of [6] applies H for time t = O( N), the Theorem follows.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 119–123 120
D ISCRETE -Q UERY Q UANTUM A LGORITHM FOR NAND T REES
Remark 1. This result can also be deduced by noting that, given query access to the inputs via UO
(Eq. 3), one can easily simulate an oracle for the matrix elements of the underlying Hamiltonian HO +HD
used in [6], and then applying results in [3, 4] for simulating sparse Hamiltonians.
Remark 2. After the first version of this note appeared [5], the algorithm of [7] was generalized to eval-
uate an arbitrary AND - OR formula in N 1/2+o(1) (discrete) queries [1]. Indeed, by using a discrete-time
quantum walk, [1] shows that the bounded-error
√ quantum query complexity of evaluating “approxi-
mately balanced”
√ formulas is only O( N). In particular, this improves the above Theorem to show that
only O( N) discrete quantum queries suffice to evaluate a balanced binary NAND tree.
Acknowledgments
AMC received support from the U.S. NSF under grant no. PHY-0456720, from the U.S. ARO under
grant no. W911NF-05-1-0294, from Canada’s MITACS and NSERC, and from the U.S. ARO/DTO.
RC received support from Canada’s CIAR, MITACS, NSERC, and the U.S. ARO/DTO. SPJ received
support from the U.S. ARO/DTO’s QuaCGR program. DY received support from Canada’s MITACS,
NSERC, and the U.S. ARO/DTO.
References
[1] A. A MBAINIS , A. M. C HILDS , B. W. R EICHARDT, R. Š PALEK , AND S. Z HANG: Any AND-OR
formula of size N can be evaluated in time N 1/2+o(1) on a quantum computer. In Proc. 48th IEEE
FOCS, pp. 363–372. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.57, arXiv:quant-
ph/0703015, arXiv:0704.3628]. 121
[2] H. BARNUM AND M. S AKS: A lower bound on the quantum query complexity of read-once func-
tions. J. Comput. System Sci., 69(2):244–258, 2004. [doi:10.1016/j.jcss.2004.02.002, arXiv:quant-
ph/0201007]. 119
[3] D. W. B ERRY, G. A HOKAS , R. C LEVE , AND B. C. S ANDERS: Efficient quantum al-
gorithms for simulating sparse Hamiltonians. Comm. Math. Phys., 270(2):359–371, 2007.
[doi:10.1007/s00220-006-0150-x, arXiv:quant-ph/0508139]. 120, 121
[4] A. M. C HILDS: Quantum information processing in continuous time. PhD thesis, Massachusetts
Institute of Technology, 2004. 120, 121
[5] A NDREW M. C HILDS , R ICHARD C LEVE , S TEPHEN P. J ORDAN , AND DAVID Y EUNG: Discrete-
query quantum algorithm for NAND trees. Technical report, Arxiv.org, 2007. [arXiv:quant-
ph/0702160]. 121
[6] E. FARHI , J. G OLDSTONE , AND S. G UTMANN: A quantum algorithm for the Hamiltonian NAND
tree. Theory of Computing, 4(1):169–190, 2008. [doi:10.4086/toc.2008.v004a008]. 120, 121
[7] E. FARHI AND S. G UTMANN: Quantum computation and decision trees. Phys. Rev. A, 58:915–
928, 1998. [doi:10.1103/PhysRevA.58.915, arXiv:quant-ph/9706062]. 120, 121
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 119–123 121
A NDREW M. C HILDS , R ICHARD C LEVE , S TEPHEN P. J ORDAN , AND DAVID YONGE -M ALLO
[8] C. M OCHON: Hamiltonian oracles. Phys. Rev. A, 75(4):042313, 2007.
[doi:10.1103/PhysRevA.75.042313, arXiv:quant-ph/0602032]. 120
[9] M. S AKS AND A. W IGDERSON: Probabilistic Boolean decision trees and the complexity of eval-
uating game trees. In Proc. 27th FOCS, pp. 29–38. IEEE Comp. Soc. Press, 1986. 119
[10] M. S ANTHA: On the Monte Carlo Boolean decision tree complexity of read-once formulae. Ran-
dom Structures Algorithms, 6(1):75–87, 1995. [doi:10.1002/rsa.3240060108]. 119
[11] M. S NIR: Lower bounds on probabilistic linear decision trees. Theoret. Comput. Sci., 38:69–82,
1985. [doi:10.1016/0304-3975(85)90210-5]. 119
AUTHORS
Andrew M. Childs
Department of Combinatorics & Optimization and Institute for Quantum Computing
University of Waterloo
amchilds uwaterloo.ca
http://www.math.uwaterloo.ca/∼amchilds
Richard Cleve
David R. Cheriton School of Computer Science and Institute for Quantum Computing
University of Waterloo
and Perimeter Institute for Theoretical Physics
cleve cs.uwaterloo.ca
http://www.cs.uwaterloo.ca/∼cleve
Stephen P. Jordan
Institute for Quantum Information
California Institute of Technology
sjordan caltech.edu
http://www.its.caltech.edu/∼sjordan
David Yonge-Mallo
David R. Cheriton School of Computer Science and Institute for Quantum Computing
University of Waterloo
davinci iqc.ca
http://www.iqc.ca/people/person.php
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 119–123 122
D ISCRETE -Q UERY Q UANTUM A LGORITHM FOR NAND T REES
ABOUT THE AUTHORS
A NDREW C HILDS has been at Waterloo since 2007. Previously, he was a postdoc at the
Caltech Institute for Quantum Information. He received his Ph. D. in physics in 2004
at MIT under the supervision of Eddie Farhi, writing a thesis on Quantum Information
Processing in Continuous Time. He is interested in quantum algorithms.
R ICHARD C LEVE has been based in Waterloo since 2004. He received his Ph. D. in 1989
from the University of Toronto under the supervision of Charles Rackoff, specializing in
(non-quantum) cryptography and complexity theory. He became curious about quantum
computing around 1994, and now works mostly in this field.
S TEPHEN J ORDAN recieved his Ph. D. in 2008 from MIT’s physics department under the
advising of Eddie Farhi. His thesis was on Quantum Computation Beyond the Circuit
Model. His current research interests include quantum algorithms and alternative meth-
ods of quantum computation such as the adiabatic and topological models.
DAVID YONGE -M ALLO has been a graduate student at the David R. Cheriton School of
Computer Science at the University of Waterloo since 2004.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 119–123 123