PIRSA:21030043

Fast estimation of outcome probabilities for quantum circuits

Pashayan, H. (2021). Fast estimation of outcome probabilities for quantum circuits. Perimeter Institute. https://pirsa.org/21030043

Pashayan, Hakop. Fast estimation of outcome probabilities for quantum circuits. Perimeter Institute, Mar. 31, 2021, https://pirsa.org/21030043 

          @misc{ pirsa_PIRSA:21030043,
            doi = {10.48660/21030043},
            url = {https://pirsa.org/21030043},
            author = {Pashayan, Hakop},
            keywords = {Quantum Information},
            language = {en},
            title = {Fast estimation of outcome probabilities for quantum circuits},
            publisher = {Perimeter Institute},
            year = {2021},
            month = {mar},
            note = {PIRSA:21030043 see, \url{https://pirsa.org}}
          }

Hakop Pashayan Freie Universität Berlin

DOI 10.48660/21030043
Collection
Talk Type Scientific Series
Subject

Abstract

We present two classical algorithms for the simulation of universal quantum circuits on n qubits constructed from c instances of Clifford gates and t arbitrary-angle Z-rotation gates such as T gates. Our algorithms complement each other by performing best in different parameter regimes. The Estimate algorithm produces an additive precision estimate of the Born rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (which scales like ≈1.17^t for T gates). Our algorithm is state-of-the-art for this task:

as an example, in approximately 25 hours (on a standard desktop computer), we estimated the Born rule probability to within an additive error of 0.03, for a 50 qubit, 60 non-Clifford gate quantum circuit with more than 2000 Clifford gates. The Compute algorithm calculates the probability of a chosen measurement outcome to machine precision with run-time O(2^t−r(t−r)t) where r is an efficiently computable, circuit-specific quantity. With high probability, r is very close to min{t,n−w} for random circuits with many Clifford gates, where w is the number of measured qubits. Compute can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+T circuits with n=55, w=5, c=105 and t=80 T-gates, and then compute the Born rule probability with a run-time consistently less than 104 seconds using a single core of a standard desktop computer. We provide a C+Python implementation of our algorithms.