Lecture 9. Quantum circuits simulation

In this Lecture we discussed the notion of simulation of quantum circuits and some simple methods of simulation. It is often useful to study the possibility of simulating a quantum system on a classical computer. This can be formalized as solving some quantum circuit simulation problem. If some quantum circuit is given, the problem of weak simulation is the problem of constructing a random variable which would reproduce outcome statistics of the quantum circuit. The strong simulation problem is the problem of estimating the probability of a given outcome. If a strong simulator of quantum circuits is available, we can efficiently generate the outcome of some quantum circuit by successively tossing biased coins and generating bits of the outcome. At the same time, if we are able to solve a weak simulation problem, then the probability of a given outcome can be estimated using statistics, but this gives only a low precision. There are two simple methods for strong simulation of quantum circuits - Schrödinger simulation and Feynman simulation. In Schrödinger simulation, we keep all the amplitudes of some state in the computer and update them. In the case of Feynman simulation, the circuit evolution is partitioned into many possible paths, and the amplitudes of the paths are summed. It is easy to calculate the amplitude of each path, but the number of paths grows extremely fast. Combining these two methods of simulation, it is possible to obtain very effective methods for computation of quantum systems on high-performance computers.