Quantum search with input as a classical circuit

Grover's algorithm assumes $$U_f$$ computing a function $$f$$ as an oracle input. But in practice, an oracle isn't given. Instead a circuit computing $$f$$ is given. So let's assume a reversible circuit, $$C \colon \{0, 1\}^{N + 1} \mapsto \{0, 1\}^{N+1}$$ that computes $$C(x, y) = (x, y \oplus f(x))$$, where $$f \colon \{0, 1\}^N \mapsto \{0, 1\}$$, $$x$$ is an $$N$$ bit register, and $$y$$ is a $$1$$ bit output register. Since $$C$$ is reversible, it can also be viewed as a quantum circuit.

Of course, Grover's algorithm can be run here. Define $$U_C |x, y \rangle = |C(x, y) \rangle$$. Then by this reduction, we can run Grover's algorithm on this oracle/circuit.

But can we do better? We have the structure of the circuit here, which isn't present in the original algorithm. Does knowing the structure provide any benefit?

• Are you asking if there are known results? Because P vs NP (namely, the hardness of SAT) is basically the question "Does knowing the structure provide any benefit?" Commented Mar 19, 2023 at 17:14