Span Programs are Equivalent to Quantum Query Algorithms
Author:
- Ben W. ReichardtBRBen W. Reichardt
- 1 January 2014
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 43 (3) , 1206-1219
Abstract
Span programs form a linear-algebraic model of computation that is studied to prove classical lower bounds. Quantum query complexity is a coherent generalization for quantum algorithms of decision-tree complexity. It is characterized by a semidefinite program known as the general adversary bound. We connect these classical and quantum models by proving that for any boolean function, the optimal “witness size” of a span program equals the general adversary bound. Therefore, span program witness size and quantum query complexity are equivalent measures. In particular, quantum algorithms can be designed based on span programs.Keywords
This publication has 33 references indexed in Scilit:
- Unbounded-error quantum query complexityTheoretical Computer Science, 2011
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum ComputerSIAM Journal on Computing, 2010
- Polynomial degree vs. quantum query complexityJournal of Computer and System Sciences, 2006
- Learning intersections and thresholds of halfspacesJournal of Computer and System Sciences, 2004
- Learning DNF in time 2Õ(n1/3)Journal of Computer and System Sciences, 2004
- A note on monotone complexity and the rank of matricesInformation Processing Letters, 2003
- Complexity measures and decision tree complexity: a surveyTheoretical Computer Science, 2002
- Quantum lower bounds by polynomialsJournal of the ACM, 2001
- On the Monte carlo boolean decision tree complexity of read‐once formulaeRandom Structures & Algorithms, 1995
- Lower bounds on probabilistic linear decision treesTheoretical Computer Science, 1985