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?

  • $\begingroup$ 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?" $\endgroup$
    – Dmitry
    Mar 19, 2023 at 17:14


Your Answer

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