In the context quantum computation, what is the evidence that querying classical oracles in superposition makes sense?

Question

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, yrangle mapsto lvert x, f(x)oplus yrangle$$
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?

benrg · Answer

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.

In the context quantum computation, what is the evidence that querying classical oracles in superposition makes sense?

One Answer

Add your own answers!

Ask a Question