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

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.

14 pages, 3 figures, v2: substantially rewritten with clearer analysis, v3: using better discretization we have obtained an optimal algorithm. to appear in FOCS'07

References in corpus (2)

• A Quantum Algorithm for the Hamiltonian NAND Tree
• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas

Cited by in corpus (11)

• Quantum algorithms for algebraic problems
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Quantum Walks
• Span-program-based quantum algorithm for evaluating formulas
• Quantum Computation Beyond the Circuit Model
• Efficient discrete-time simulations of continuous-time quantum query algorithms
• Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
• Quantum Slide and NAND Tree on a Photonic Chip
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• How to Compile Some NAND Formula Evaluators
• Quantum Algorithms for Evaluating MIN-MAX Trees