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

SIAM Journal on Computing

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, Robert Špalek, S. Zhang

Published Jan 1, 2010• 122 citations
Publisher

Abstract

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.

DOI
10.1137/080712167

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•19 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

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•125 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

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

Faster quantum algorithm for evaluating game trees

Ben W. Reichardt

We give an O(sqrt n log n)-query quantum algorithm for evaluating size-n AND-OR formulas. Its running time is poly-logarithmically greater after efficient preprocessing. Unlike previous approaches, the algorithm is based on a quantum walk on a graph that is not a tree. Instead, the algorithm is based on a hybrid of direct-sum span program composition, which generates tree-like graphs, and a novel tensor-product span program composition method, which generates graphs with vertices corresponding to minimal zero-certificates. For comparison, by the general adversary bound, the quantum query complexity for evaluating a size-n read-once AND-OR formula is at least Omega(sqrt n), and at most O(sqrt{n} log n / log log n). However, this algorithm is not necessarily time efficient; the number of elementary quantum gates applied between input queries could be much larger. Ambainis et al. have given a quantum algorithm that uses sqrt{n} 2^{O(sqrt{log n})} queries, with a poly-logarithmically greater running time.

arXiv:0907.1623•Jul 9, 2009•1 citation

Span-program-based quantum algorithm for evaluating formulas

Ben W. Reichardt, Robert Špalek

We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense. The main new tool is a correspondence between a classical linear-algebraic model of computation, “span programs,” and weighted bipartite graphs. A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A quantum computer can therefore evaluate the span program by applying spectral estimation to the graph. For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal. In contrast, our algorithm generalizes the optimal quantum AND-OR formula evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.

arXiv:0710.2630•Theory of Computing•Jan 1, 2012•42 citations
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.
We give an O(sqrt n log n)-query quantum algorithm for evaluating size-n AND-OR formulas. Its running time is poly-logarithmically greater after efficient preprocessing. Unlike previous approaches, the algorithm is based on a quantum walk on a graph that is not a tree. Instead, the algorithm is based on a hybrid of direct-sum span program composition, which generates tree-like graphs, and a novel tensor-product span program composition method, which generates graphs with vertices corresponding to minimal zero-certificates. For comparison, by the general adversary bound, the quantum query complexity for evaluating a size-n read-once AND-OR formula is at least Omega(sqrt n), and at most O(sqrt{n} log n / log log n). However, this algorithm is not necessarily time efficient; the number of elementary quantum gates applied between input queries could be much larger. Ambainis et al. have given a quantum algorithm that uses sqrt{n} 2^{O(sqrt{log n})} queries, with a poly-logarithmically greater running time.
We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense. The main new tool is a correspondence between a classical linear-algebraic model of computation, “span programs,” and weighted bipartite graphs. A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A quantum computer can therefore evaluate the span program by applying spectral estimation to the graph. For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal. In contrast, our algorithm generalizes the optimal quantum AND-OR formula evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.