IQI Weekly Seminar

Abstract: Quantum circuit is 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 include depolarizing noise as a special case. We study this problem by combining tensor network representation and fourier analysis of boolean function. This exhibits that tensor network provides an elegant pictorial reasoning tool and unleashes the power of fourier transformation in analyzing noisy quantum systems.

First, I will prove for most of random quantum circuits, the measurement statistics is very close (exponentially decay with the strength of noise and circuit depth) to uniform distribution. This questions complexity-theoretic foundation of quantum supremacy by chaotic quantum circuit. Second, I will prove 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. Third, I will construct an example such that a large size noisy quantum circuit can be simulated by small scale quantum computers. Different from other effort along this direction, we consider a scenario without explicit restriction on the entanglement among different sub-systems.

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.