Span-program-based quantum algorithm for evaluating formulas
arXiv:0710.2630 · doi:10.4086/toc.2012.v008a013
Abstract
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.
42 pages, new appendix on four-bit functions
References in corpus (8)
- Negative weights make adversaries stronger
- Quantum query complexity of state conversion
- A Quantum Algorithm for the Hamiltonian NAND Tree
- A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
- Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
- Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
- Tight adversary bounds for composite functions
- Quantum search with variable times
Cited by in corpus (18)
- Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
- Discrete spacetime, quantum walks and relativistic wave equations
- Continuous Limit of Discrete Quantum Walks
- Quantum Speedup Based on Classical Decision Trees
- Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions
- Variations on Quantum Adversary
- Taming Quantum Time Complexity
- NAND-Trees, Average Choice Complexity, and Effective Resistance
- Quantum Algorithms for Graph Connectivity and Formula Evaluation
- Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
- The quantum query complexity of composition with a relation
- Quantum divide and conquer
- Quantum Lower Bounds by Sample-to-Query Lifting
- Superlinear advantage for exact quantum algorithms
- Quantum Algorithm for Monotonicity Testing on the Hypercube
- Space-Efficient Quantum Error Reduction without log Factors
- The General Adversary Bound: A Survey
- Improved Quantum Query Upper Bounds Based on Classical Decision Trees