Span programs and quantum time complexity

Understand

Span programs are an important model of quantum computation due to their tight correspondence with quantum query complexity.

• For any decision problem $f$, the minimum complexity of a span program for $f$ is equal, up to a constant factor, to the quantum query complexity of $f$.
• Moreover, this correspondence is constructive.
• A span program for $f$ with complexity $C$ can be compiled into a bounded error quantum algorithm for $f$ with query complexity $O(C)$, and vice versa.