All reports by Author Ben Reichardt:

__
TR10-110
| 14th July 2010
__

Ben Reichardt#### Span programs and quantum query algorithms

__
TR10-075
| 22nd April 2010
__

Ben Reichardt#### Least span program witness size equals the general adversary lower bound on quantum query complexity

Ben Reichardt

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower ... more >>>

Ben Reichardt

Span programs form a linear-algebraic model of computation, with span program "size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these ... more >>>