Kamil Korzekwa

We present a classical algorithm capable of estimating Born rule probabilities of quantum circuits consisting of matchgate/Fermionic linear optical (FLO) unitaries and non-FLO controlled-phase gates with arbitrary phases. Our algorithm has asymptotic runtime linear in an (in general) exponentially large quantity we have named the “FLO-extent”, and is at most polynomial all other parameters. The FLO-extent is defined in a similar way to the stabilizer extent known from the literature on quantum simulation using stabilizer decompositions. The FLO extent is sub-multiplicative, and the multiplicative upper bound leads to a runtime for our algorithm which doubles for each swap gate, or controlled-Z gate added to the circuit. Controlled-phase gates with different phases have lower extent, smoothly interpolating between 1 and 2. These numbers can be compared with the prior state of-the-art for this task, the runtime of which is multiplied by a factor 9 for each CZ-gate. This dramatic difference in performance is due to our use of methods we have developed to perform tasks in the FLO subtheory in a phase-sensitive way, allowing us to decompose the relevant “magic states” at the level of statevectors rather than density operators. Our results are formulated for quantum circuits, directly extending the class of quantum computations that can be simulated using current classical computers. However, the FLO subtheory also naturally represents the evolution of non-interacting Fermions, while the addition of non-FLO unitaries to the circuit can represent interactions between Fermions. We therefore expect that our results will be applicable to classical simulations of weakly interacting Fermions, with potential applications in condensed matter and quantum chemistry research. In addition to practical simulation our work is part of the ongoing effort to understand the differences between the computational power of classical and that of quantum mechanics. By extending classical simulation methods to new areas we can focus attention on those features of quantum computations which are necessary for meaningful "quantum advantage".

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=10^5 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.