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/0702144

A Quantum Algorithm for the Hamiltonian NAND Tree

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Published Feb 14, 2007• 169 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.quant-ph/0702144

Related papers

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•55 citations

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

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.

arXiv:quant-ph/0702160•Theory of Computing•Jan 1, 2009•52 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•50 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•2 citations

Continuous-time quantum search on balanced trees

Pascal Philipp, Luís Domingues Tomé Jardim Tarrataca, Stefan Boettcher

We examine the effect of network heterogeneity on the performance of quantum search algorithms. To this end, we study quantum search on a tree for the oracle Hamiltonian formulation employed by continuous-time quantum walks. We use analytical and numerical arguments to show that the exponent of the asymptotic running time $\ensuremath{\sim}{N}^{\ensuremath{\beta}}$ changes uniformly from $\ensuremath{\beta}=0.5$ to $\ensuremath{\beta}=1$ as the searched-for site is moved from the root of the tree towards the leaves. These results imply that the time complexity of the quantum search algorithm on a balanced tree is closely correlated with certain path-based centrality measures of the searched-for site.

arXiv:1601.01154•Physical Review A•Mar 4, 2016•34 citations
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+ǫ).
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.
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.
We examine the effect of network heterogeneity on the performance of quantum search algorithms. To this end, we study quantum search on a tree for the oracle Hamiltonian formulation employed by continuous-time quantum walks. We use analytical and numerical arguments to show that the exponent of the asymptotic running time $\ensuremath{\sim}{N}^{\ensuremath{\beta}}$ changes uniformly from $\ensuremath{\beta}=0.5$ to $\ensuremath{\beta}=1$ as the searched-for site is moved from the root of the tree towards the leaves. These results imply that the time complexity of the quantum search algorithm on a balanced tree is closely correlated with certain path-based centrality measures of the searched-for site.