Low Rank Density Matrix Evolution for Noisy Quantum Circuits

Quantum circuit simulators validate the accuracy of quantum computing hardware and facilitate the invention of quantum algorithms and the deployment of quantum solutions on real world problems. In this work, we present an algorithm for simulating noisy quantum circuits based on the fact that the effective dimensionality of a density matrix is low when the noise level is reasonable small. Under certain conditions on the noise level and circuit depth, we proof that the numerical rank of a density matrix grows only linearly with the number of qubits. This allow us to track the evolution of a compressed representation of a density matrix with exponentially less computational resource. We implement this algorithm in an in-house simulator, Quasar, showing that the low rank algorithm speeds up simulations more than two orders of magnitude against the standard full density matrix method, with a trade-off of small amount of error. We benchmark the performance of the algorithm with different noise channels, noise strength and circuit types. Finally, we implement instances of Grover’s search algorithm, showing that the low rank evolution benefits not only random circuit simulations, but also structured quantum algorithms.