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.
\[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.