Span Programs are Equivalent to Quantum Query Algorithms

Author:
  • BRBen W. Reichardt
    Ben W. Reichardt

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.

This publication has 33 references indexed in Scilit: