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$ Commented Dec 5, 2020 at 14:28

1 Answer 1


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.

  • $\begingroup$ Why does any Clifford oracle accept $0, 50$ or $100$ percent of all inputs? And why does it make the search trivial --- is it just that you will use a Deutsch-Jozsa type algorithm to determine whether you are in the $0%$ or the $100%$ case (constant) or the $50%$ case (balanced), and if you are in the former, just trivially check by one query whether you are in the $0%$ or the $100%$ case? $\endgroup$
    – BlackHat18
    Commented Sep 7, 2021 at 20:04
  • 1
    $\begingroup$ @BlackHat18 Try proving it classically with circuits made up of just NOTs and CNOTs. Any bit you can prepare will have an equation like "not b1 xor b3 xor b4": a bunch of terms xor'd together. A parity function. Such expressions always match 50% of inputs, or are vacuous (equal to False or equal to True). $\endgroup$ Commented Sep 7, 2021 at 21:24

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.