Faster classical estimation of Born rule probabilities for Clifford + T circuits

We present a classical algorithm for computing additive precision estimates of Born-rule probabilities associated with universal quantum circuits. Our algorithm estimates the probability obtained from starting a system on n qubits in the computational basis state, evolving it through c Clifford gates and t T (magic) gates, and measuring w < n qubits in the computational basis. The runtime scales exponentially in t, but polynomially in all other parameters, and is state-of-the-art for this estimation task. Along the way we develop several novel techniques for handling these circuits which may be useful more broadly.

__________________________________________________________________
Zoom meeting details

Topic: Quantum Information and Quantum Computing Working Group
Time: October 22, 2020, 4:00 PM Warsaw

Join Zoom Meeting link (NEW LINK):
https://tinyurl.com/quantum-ctp

Meeting ID: 94552545103
Passcode: 323395

If you encounter any problems with connecting to the Zoom meeting, please email me maciejewski@cft.edu.pl directly.

‍