## Sunday, 8 September 2013

### Quantum Query Complexity

Just as in the classical context, the amount of queries needed in an algorithm to some function $f:\{0,1\}^n\rightarrow\{0,1\}^m$ may be of interest. Since the operators in the quantum model must be reversible and unitary, a quantum black-box can be defined as the unitary operator expressed as a controlled gate in terms of the function $f$ as
$c-U_f: \left|x\right>\left|y\right>\mapsto \left|x\right>\left|y\oplus f(x)\right>.$
for all $x\in\{0,1\}^n$ and $y\in\{0,1\}^m$. Here, $\oplus$ denotes addition modulo $2$ defined on bitstrings. By extending this operator to satisfy linearity, arbitrary superpositions of states can be mapped. By setting $y=0$, $c-U_f\left|x\right>\left|0\right>=\left|x\right>\left|f(x)\right>$, and enough information is retained to define the inverse operation of $c-U_f$ despite the fact that the function $f$ itself may not be invertible.

If some bounds to the number of queries made to a quantum black-box are obtained, and the black-box is made into a white-box by specifying the unitary operators that actually implement the gate $c-U_f$, then bounds in the circuit complexity of the algorithm can be obtained. Many of the algorithms presented here will be in the black-box model, and some algorithms will also explicitly provide constructions that turn the black-boxes into white-boxes.