2009/07/09 by Ben W. Reichardt, Reichardt, Ben W.
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.0907.1622
28 pages, 1 figure
arxiv created 2009/07/09 · openalex publication_date 2009/07/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.