Classical simulation of noisy quantum circuits

Quantum circuits are believed to be hard to simulate by classical computers. In realistic situations, there is always noise, which makes the quantum gates imperfect. In this talk, I consider classical simulation of several different ensembles of quantum circuits without fault-tolerance, such that the strength of the noise is regarded as a constant (not scaling with the system size). The noise model we consider is mixture of Pauli errors, which includes depolarizing noise as a special case. We study this problem by combining tensor network representations with Fourier analysis of boolean functions. This demonstrates that tensor networks provide an elegant pictorial reasoning tool and unleashes the power of Fourier transformation in analyzing noisy quantum systems.

 

In this talk, I will prove that the average complexity of approximating random quantum circuits in some generic and reasonable ensembles is in P. Concretely, for a large proportion (say 99%) of ideal “classical” gates + noisy single qubit gates, there exists a polynomial classical algorithm simulating the measurement result to any constant additive error (say 0.01). The “classical” gates can be Clifford gates, classical reversible gates, etc and even combinations among some of them in restricted ways. The single qubit gates are chosen from a gate set randomly (e.g., according to Haar measure) and independently.

 

This result might be a step towards understanding the computational complexity of analog quantum simulation and designing classical algorithm for simulating more physical noisy quantum systems. The result also introduces a question: for which kind of quantum evolution, the “quantumness” is robust to noise from computational point of view.