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.
