Span-program-based quantum algorithm for evaluating unbalanced formulas
arXiv:0907.1622
Abstract
The formula-evaluation problem is defined recursively. A formula's evaluation is the evaluation of a gate, the inputs of which are themselves independent formulas. Despite this pure recursive structure, the problem is combinatorially difficult for classical computers. A quantum algorithm is given to evaluate formulas over any finite boolean gate set. Provided that the complexities of the input subformulas to any gate differ by at most a constant factor, the algorithm has optimal query complexity. After efficient preprocessing, it is nearly time optimal. The algorithm is derived using the span program framework. It corresponds to the composition of the individual span programs for each gate in the formula. Thus the algorithm's structure reflects the formula's recursive structure.
28 pages, 1 figure
References in corpus (15)
- Strengths and Weaknesses of Quantum Computing
- Creating superpositions that correspond to efficiently integrable probability distributions
- Negative weights make adversaries stronger
- Quantum Search on Bounded-Error Inputs
- Quantum vs. Classical Communication and Computation
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Tradeoffs in the Quantum Search Algorithm
- A fast quantum mechanical algorithm for database search
- Bounds for Small-Error and Zero-Error Quantum Algorithms
- A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
- Tight adversary bounds for composite functions
- On the power of Ambainis's lower bounds
- The quantum query complexity of certification
- All Quantum Adversary Methods are Equivalent
- Efficient Circuits for Quantum Walks