Abstract
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.
A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
Related papers
Ranked by semantic similarity — how closely each paper's abstract matches this one (100% = near-identical topic).
- Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer (2011)82% match
- Discrete-query Quantum Algorithm For NAND Trees (2007)81% match
- Quantum algorithms for formula evaluation (2010)79% match
- How to Compile Some NAND Formula Evaluators (2007)77% match
- A Quantum Algorithm For The Hamiltonian NAND Tree (2007)76% match
- Faster quantum algorithm for evaluating game trees (2009)75% match
- Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure (2011)74% match
- A quantum dot implementation of the quantum NAND algorithm (2007)74% match