5
$\begingroup$

So it is clear that the Grover algorithm offers a quadratic speedup over the classical algorithms; my question is, is it known how to simulate Grover at the most quadratic time? To clarify my question, assume that the Grover runs at time $O(N)$. Then, is there a classical algorithm that computes Grover at time $O(N^2)$?

If the answer is negative, do we have a reason to believe we couldn't do that? (For example, if 3-SAT were expected to be a QMA-hard problem, then it is clear that we shouldn't expect that, But as far I know, that is not the case).

$\endgroup$
1
  • 4
    $\begingroup$ Are you actually looking for a classical simulation of Grover's algorithm, or a classical algorithm that has the correct run-time for returning an answer to the same search problem? $\endgroup$
    – DaftWullie
    Apr 25, 2023 at 13:19

2 Answers 2

5
$\begingroup$

If you have an implementation of Grover which uses a classical circuit to construct the oracle for f(x) (via phase kick-back), and you want to find a satisfying assignment x (as does Grover), then trivially: Yes (at least if you allow for randomized computation).

To this end, you simply run the circuit for f(x) classically on randomly chosen inputs (here, each application of f(x) takes the same time as on the quantum computer), and after an average of N/K tries (where K is the number of satisfying assingments), you have found a solution -- as compared to $O(\sqrt{N/K})$ iterations for Grover.

$\endgroup$
1
  • $\begingroup$ ... unless you mean something else by "computes Grover", but then you would have to specify what precisely you mean. $\endgroup$ Apr 25, 2023 at 20:37
1
$\begingroup$

Yes, the simulation is a classical algorithm doing the same thing as the Grover. We now that this algorithm (i.e. check each item in a database serially) is linearly complex.

However, if you want to efficiently simulate the Grover circuit on a classical computer, you can do so only for two-qubit case because under this setting only Clifford's gates are involved. However, once more than two qubits are used, you need Toffoli gates which are non-Clifford ones, hence the classical simulation became non-efficient.

$\endgroup$

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.