# Is it possible to demonstrate a quadratic speed-up of a quantum algorithm on a classical computer?

In article Quantum computational finance: Monte Carlo pricing of financial derivatives the authors said that:

Firstly:

While a practical quantum computer has yet to become a reality, we can exhibit the speedup of our quantum algorithm for options pricing numerically, and compare its performance with the classical Monte Carlo method.

Secondly:

However, to showcase the quadratic speed up, we here perform phase estimation by using a single qubit rotated according to $$\mathrm{e}^{i\theta\sigma_x /2}$$, where $$\theta$$ is the predetermined phase.

If my understanding is correct, it is possible to simulate efficiently a circuit consisting only of Clifford gates. Since an inverse QFT is employed in the circuit, at least one $$\mathrm{T}$$ should be use here (QFT for three or more qubits). However, in the second quotation the authors claim that they used only a single qubit gate for phase estimation which reduced number of qubits in the inverse QFT and avoided the use of non-Clifford gates.

So my questions is: Have the authors used Clifford gates only in their construction or am I missing something? So far, I have thought that simulation of quantum computer cannot bring any speedup even in case only Clifford gates are employed.

• Note that the classical simulation of Clifford gates can incur a polynomial overhead. Hence a quadratic speedup with a quantum Clifford circuit is not excluded. Mar 3, 2020 at 12:45