A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
arXiv:0704.3628
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.
21 pages, 2 figures
References in corpus (2)
Cited by in corpus (14)
- On the relationship between continuous- and discrete-time quantum walk
- Quantum algorithms for algebraic problems
- Span-program-based quantum algorithm for evaluating formulas
- Quantum Computation Beyond the Circuit Model
- Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
- Entanglement Theory and the Quantum Simulation of Many-Body Physics
- Quantum Slide and NAND Tree on a Photonic Chip
- New Developments in Quantum Algorithms
- The quantum query complexity of certification
- Quantum algorithms for formula evaluation
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- How to Compile Some NAND Formula Evaluators
- Quantum Algorithms for Evaluating MIN-MAX Trees
- Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs