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):
Meeting ID: 94552545103
If you encounter any problems with connecting to the Zoom meeting, please email me email@example.com directly.