1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – smapers
    Commented Mar 3, 2020 at 12:45

1 Answer 1

Reset to default
3
+50
$\begingroup$

I have not read the full details of the paper, but have attempted to skim over the most relevant bits to the question (i.e. I could easily have missed something).

As I read the paper, they are doing some calculation with a fixed size of input, and they repeat it many times (see equation 58). They ask how many times do you have to repeat it to get the same level of confidence in the output as you would with a classical Monte-Carlo. I believe that it is this "scaling" that the authors are referring to as giving a quadratic improvement.

This bears no relation to what we usually think about scaling: how the running time scales with increasing size of input because the input is of fixed size. So, in principle, there's no problem with simulating what they want to simulate, whether it uses Clifford gates or not. So long as it fits in the memory of the computer, you can run it and repeat it many times, and you can count the number of repetitions required.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If I understand it correcty, it means that a quantum algorithm shows same speed-up regardless it run on quantum computer or it is simulated. However, the simulation is possible for small number of qubits because of exponentially rising consumption of memory. In the paper, the number of qubits is small and fixed, hence it is possible to show speed-up of quantum algorithm. Am I righ? $\endgroup$
    – Martin Vesely
    Commented Mar 11, 2020 at 5:12
  • $\begingroup$ Yes, that’s how I interpret it. $\endgroup$
    – DaftWullie
    Commented Mar 11, 2020 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.