In the article Is Quantum Search Pratical the authors emphasized that a complexity of an oracle is often neglected when advantages of Grover search are discussed. In the end, a total complexity of the search can be given mostly by the oracle complexity.

Let's assume that we are able to prepare an oracle composed from Clifford gates only (i.e. CNOT, Hadamard gate $H$, phase gate $S$ and Pauli gates $X$, $Y$ and $Z$). Naturaly, such oracle would be very simple, for example XOR function implemented by CNOT gate.

Now, turn to Grover diffusion operator. The operator is composed of Hadamard gates and $X$ gates. These are Clifford ones. But the issue is controled $Z$ gate. For two qubits Grover operator CZ gate can be implemented with two Hadamards and CNOT. Therefore, in this simple case, Grover operator is composed of Clifford gates only.

To sum up, my ideas so far, for simple "Cliffordian" oracle and two qubits case, only Clifford gates are employed in the Grover search. According to Gottesman-Knill theorem, such circuit can be simulated efficiently on a classical computer.

However, what about $n$ qubit Grover diffusion operator? It seems to me that to implement controlled $Z$ gates with $n-1$ controlling qubits we would need to employ non-Clifford gates (e.g. Toffoli), hence it would not be possible to simulate Grover search efficiently on a classical computer.

So, my question is if this statement is right: Two qubits Grover search with an Oracle implemented with Clifford gates only can be efficiently simulated on a classical computer. For three qubits or non-Cliffordian oracle, the efficient simulation of Grover search on a classical computer is impossible.

  • 1
    $\begingroup$ I think that younare right, moreover the oracle will probably also need non-clifford gates $\endgroup$ – BrockenDuck Dec 5 '20 at 14:28

The diffusion operator is a multi controlled not operation (modulo some hadamards). It's not a Clifford operation.

Also any useful oracle you'd use with Grover's algorithm won't be Clifford operations either, since any Clifford oracle accepts 0%, 50%, or 100% of all inputs which makes search trivial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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