turkmath.org

It has been known since the early days of the stabilizer formalism that while Clifford circuits with stabilizer state inputs can be simulated efficiently in the number of qubits and operations, more general circuits can be simulated with an overhead growing exponentially with, for example, the number of T gates, or some other "magic" resource. Quantifiers of magic resource known as magic monotones formalize the notion that some states/operations are harder to simulate than others, and various classical simulation algorithms have been proposed where performance guarantees depend explicitly on some magic monotone. A sequence of works on stabilizer rank culminated in the powerful simulator of Ref. [1], which reduces runtime by replacing an exact stabilizer decomposition with a sparsified approximation, but is largely restricted to simulating pure state evolution. Meanwhile, a parallel avenue of research developed links between quasiprobability simulation methods and robustness-type monotones [2, 3], yielding the insight that noisier circuits can be easier to simulate. Simulators of this type admit mixed initial states and more general quantum channels, but tend to be slower than stabilizer rank-based methods. In this seminar I will outline how stabilizer rank methods can be extended to deal with mixed magic states [4] and noisy non-Clifford operations [5], in the process improving on the runtime bounds of Ref. [1]. I will also discuss how this method (and the others introduced in Ref. [4]) can be situated within a broader framework of simulators for general quantum circuits on qubits, each with an associated magic monotone, showing that stabilizer rank and quasiprobability methods are more closely related than they first appear.
[1] Bravyi, Browne, Calpin, Campbell, Gosset & Howard (2019) arxiv:1808.00128

[2] Pashayan, Wallman & Bartlett (2015) arxiv:1503.07525

[3] Howard & Campbell (2017) arxiv:1609.07488

[4] Seddon, Regula, Pashayan, Ouyang and Campbell (2021) arxiv:2002.06181

[5] Seddon (2022) https://discovery.ucl.ac.uk/id/eprint/10146361/