In quantum computation it is often assumed that if $f$ denotes some (classical) Boolean circuit $\{0,1\}^n \rightarrow \{0,1\}$, then a quantum circuit can have oracle access to $f$, that is the quantum algorithm can query in superposition via,

$$\lvert x, y\rangle\ \mapsto\ \lvert x, f(x)\oplus y\rangle$$

What evidence is there that this (i.e. querying in superposition) is indeed a physically reasonable assumption? Given blackbox access to some $f$ how would one go about integrating this into a quantum circuit?


1 Answer 1


If you had a physical implementation of Grover's algorithm that took a physical black box as input, the box would have to contain a quantum circuit.

As far as I know, saying the circuit is "classical" in this context means nothing more than that the quantum gates in it are permutations in the computational basis, or perhaps that the function computed by the whole circuit is a permutation.

Oracles in complexity theory aren't meant to model anything in the real world. They're only introduced because they make proofs easier. Grover's algorithm has been proven optimal in the quantum black-box model, but if you're allowed to open the box then we don't even know that the problem isn't in P. A lower bound for the real problem would be preferable, but a lower bound for the oracle version is better than nothing.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.