Quantum query complexity
= Quantum query complexity
The quantum query complexity of a task counts uses of an input oracle by a <quantum circuit>, for a specified success probability. Known gates and workspace operations are not counted as oracle queries, although they contribute to the circuit's full runtime. An efficient query bound therefore need not, by itself, be an efficient gate bound.