Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0702160 · Theory of Computing

Discrete-query quantum algorithm for NAND trees

Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David Yonge-Mallo

Published Jan 1, 2009• 33 citations
arXivHTMLPDF

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 Computing 4 (2008) 169-190. That paper gave a quantum algorithm for evaluating nand trees with running time $O(\sqrt{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.

DOI
10.4086/toc.2009.v005a005

Related papers

Discrete-query quantum algorithm for NAND trees. (arXiv:quant-ph/0702160v2 UPDATED)

Andrew M. Childs, Richard Cleve, Stephen P. Jordan +1 more

Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0.

•Sep 9, 2019•0 citations

Discrete-query quantum algorithm for NAND trees

Andrew M. Childs, Richard Cleve, Stephen P. Jordan +1 more

Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating nand trees that runs in time O ( √ N log N) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N 1/2+ǫ) queries in the conventional quantum query model, for any fixed ǫ> 0. A nand tree of depth n is a balanced binary tree whose internal vertices represent nand gates. Placing bits x1,...,x2 n at the leaves, the root of the nand tree evaluates to the function fn(x1,...,x2 n), where fn: {0, 1} 2n → {0, 1} is defined recursively as follows. For n = 0, f0(x) = x, and for n> 0, fn(x1,..., x2 n) = ¬ ( fn−1(x1,..., x 2 n−1) ∧ fn−1(x 2 n−1 +1,...,x2 n)). (1) The goal of the nand tree problem is to evaluate fn(x1,..., x2 n), making as few queries to the bits x1,..., x2 n as possible. The optimal classical randomized algorithm for this problem makes Θ(N 0.753) queries, where N = 2 n [7, 8, 9]. Until now, no better quantum algorithm was known, whereas the best known quantum lower bound is only Ω ( √ N) [1]. Here we show that for any fixed ǫ> 0, the quantum query complexity of evaluating nand trees is O(N 1/2+ǫ).

•Feb 16, 2007•54 citations

A nearly optimal discrete query quantum algorithm for evaluating NAND formulas

Andris Ambainis

We present an O(\sqrt{N}) discrete query quantum algorithm for evaluating balanced binary NAND formulas and an O(N^{{1/2}+O(\frac{1}{\sqrt{\log N}})}) discrete query quantum algorithm for evaluating arbitrary binary NAND formulas.

arXiv:0704.3628•Apr 26, 2007•30 citations

A Quantum Algorithm for the Hamiltonian NAND Tree

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

We give a quantum algorithm for the binary NAND tree problem in the Hamiltonian oracle model. The algorithm uses a continuous time quantum walk with a run time proportional to sqrt N. We also show a lower bound of sqrt N for the NAND tree problem in the Hamiltonian oracle model.

arXiv:quant-ph/0702144•Feb 14, 2007•71 citations

Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer

Andrew M. Childs, Ben W. Reichardt, Robert Špalek +1 more

For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas can be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the (2-o(1))-th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.

arXiv:quant-ph/0703015•Mar 2, 2007•22 citations

A quantum dot implementation of the quantum NAND algorithm

Jacob M. Taylor

We propose a physical implementation of the quantum NAND tree evaluation algorithm. Our approach, based on continuous time quantum walks, uses the wave interference of a single electron in a heirarchical set of tunnel coupled quantum dots. We find that the query complexity of the NAND tree evaluation does not suffer strongly from disorder and dephasing, nor is it directly limited by temperature or restricted dimensionality for 2-d structures. Finally, we suggest a potential application of this algorithm to the efficient determination of high-order correlation functions of complex quantum systems.

arXiv:0708.1484•Aug 10, 2007•0 citations
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 Computing 4 (2008) 169-190. That paper gave a quantum algorithm for evaluating nand trees with running time O(N)O(\sqrt{N})O(N​) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using N1/2+o(1)N^{1/2 + o(1)}N1/2+o(1) queries in the conventional (discrete) quantum query model.
Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating nand trees that runs in time O ( √ N log N) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N 1/2+ǫ) queries in the conventional quantum query model, for any fixed ǫ> 0. A nand tree of depth n is a balanced binary tree whose internal vertices represent nand gates. Placing bits x1,...,x2 n at the leaves, the root of the nand tree evaluates to the function fn(x1,...,x2 n), where fn: {0, 1} 2n → {0, 1} is defined recursively as follows. For n = 0, f0(x) = x, and for n> 0, fn(x1,..., x2 n) = ¬ ( fn−1(x1,..., x 2 n−1) ∧ fn−1(x 2 n−1 +1,...,x2 n)). (1) The goal of the nand tree problem is to evaluate fn(x1,..., x2 n), making as few queries to the bits x1,..., x2 n as possible. The optimal classical randomized algorithm for this problem makes Θ(N 0.753) queries, where N = 2 n [7, 8, 9]. Until now, no better quantum algorithm was known, whereas the best known quantum lower bound is only Ω ( √ N) [1]. Here we show that for any fixed ǫ> 0, the quantum query complexity of evaluating nand trees is O(N 1/2+ǫ).
We propose a physical implementation of the quantum NAND tree evaluation algorithm. Our approach, based on continuous time quantum walks, uses the wave interference of a single electron in a heirarchical set of tunnel coupled quantum dots. We find that the query complexity of the NAND tree evaluation does not suffer strongly from disorder and dephasing, nor is it directly limited by temperature or restricted dimensionality for 2-d structures. Finally, we suggest a potential application of this algorithm to the efficient determination of high-order correlation functions of complex quantum systems.