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

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, Shengyu Zhang

Published Mar 2, 2007• 50 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0703015

Related papers

Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer

Andris Ambainis, Andrew M. Childs, Ben W. Reichardt +2 more

For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) 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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•143 citations

Every NAND formula on N variables can be evaluated in time O(N^{1/2+eps})

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

For every NAND formula on N variables, there is a bounded-error O(N^{1/2+eps})-time quantum algorithm that evaluates this formula on a black-box input, for eps>0 an arbitrarily small constant. It follows that the (2-eps)-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.

•Mar 2, 2007•7 citations

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

Andris Ambainis, Andrew M. Childs, Ben W. Reichardt +2 more

Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

SIAM Journal on Computing•Jan 1, 2010•135 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•55 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•37 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•169 citations
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.
Any AND-OR Formula of Size N Can Be Evaluated in Time N1/2+o(1)N^{1/2+o(1)}N1/2+o(1) on a Quantum Computer
Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time N1/2+o(1)N^{1/2+o(1)}N1/2+o(1). In particular, approximately balanced formulas can be evaluated in O(N)O(\sqrt{N})O(N​) queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.
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+ǫ).