January 09, 2025
talk, Joint Mathematics Meetings (JMM), Seattle, WA
Slides (PDF)
Quantum computing is an active area of research which has the potential to revolutionize fields such as cryptography, optimization, and simulation of quantum systems. In order to verify the correctness and performance of new quantum algorithms, researchers have turned to the classical simulation of quantum systems. However quantum systems are highly susceptible to noise and decoherence, both of which are expensive processes to classically simulate . So in an effort to develop computationally efficient methods to simulate quantum noise we explore three methods that leverage the Gottesman-Knill theorem, which provides efficient simulation of circuits containing only Clifford gates. First, we explore methods to decompose a noise operator into a sum of Clifford gates via mixed integer linear programming, using these decompositions to classically simulate noisy quantum circuits within the stabilizer formalism first proposed by Aaronson and Gottesman (2004). We find that the a Clifford decomposition is not guaranteed to have low rank decompositions and that at best the runtime of simulating noise using Clifford decompositions would be $O(2^k)$, where $k$ is the number of Kraus operators applied. Second, we explore the process of dilating our noise operators into a higher dimensional Hilbert space. Specifically we formailze two unitary dilation based algorithms for simulating noise; Sz.-Nagy and Stinespring’s dilation algorithms. The two algorithms yield respective run-times of $O\left(\dfrac{1}{\delta \Delta^2} s n^3 \eta^{-2} 1.17^t\right)$ and $O\left(n^2 \prod_{i=1}^k \lvert\xi_i\rvert + n^3 \sum_{i=1}^k \lvert\xi_i\rvert^3\right)$. Third we propose a theoretical “K-gadget” framework for generalizing the T-Gadget approach developed by Bravyi and Gosset (2016). Through numerical simulation, we show that the K-gadget approach provides an exponential speed up over traditional approaches when simulating certain quantum circuits. In particular, we show empirically that one can simulate over ten thousand non-Clifford amplitude dampening channels using the K-gadget method on a 29TB system. This generalized approach can be used to simulate noisy circuits with significantly more efficient runtime and space complexity then previously proposed methods.
