Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2202.01233

More Optimal Simulation of Universal Quantum Computers

Lucas Kocia, Genele Tulloch

Published Feb 2, 2022• 1 citation
arXivHTMLPDF

Abstract

Validating whether a quantum device confers a computational advantage often requires classical simulation of its outcomes. The worst-case sampling cost of $L_1$-norm based simulation has plateaued at $\le(2+\sqrt{2})ξ_t δ^{-1}$ in the limit that $t \rightarrow \infty$, where $δ$ is the additive error and $ξ_t$ is the stabilizer extent of a $t$-qubit magic state. We reduce this prefactor 68-fold by a leading-order reduction in $t$ through correlated sampling. The result exceeds even the average-case of the prior state-of-the-art and current simulators accurate to multiplicative error. Numerical demonstrations support our proofs. The technique can be applied broadly to reduce the cost of $L_1$ minimization.

DOI
10.48550/arxiv.2202.01233

Related papers

Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling

Lucas Kocia

Bounding the cost of classically simulating the outcomes of universal quantum circuits to additive error $δ$ is often called weak simulation and is a direct way to determine when they confer a quantum advantage. Weak simulation of the $T$+Clifford gateset is $BQP$-complete and is expected to scale exponentially with the number $t$ of $T$ gates. We constructively tighten the upper bound on the worst-case $L_1$ norm sampling cost to next order in $t$ from $\mathcal O(ξ^t δ^{-2})$ if $δ^2 \gg ξ^{-t}$ to $\mathcal O((ξ^t{-}t) δ^{-2} )$ if $δ^2 \gg (ξ^t -t)^{-1}$, where $ξ^t = 2^{\sim 0.228 t}$ is the stabilizer extent of the $t$-tensored $T$ gate magic state. We accomplish this by replacing independent $L_1$ sampling in the popular SPARSIFY algorithm used in many weak simulators with correlated $L_1$ sampling. As an aside, this result demonstrates that the $T$ gate magic state's approximate stabilizer state decomposition is not multiplicative with respect to $t$, for finite values, despite the multiplicativity of its stabilizer extent. This is the first weak simulation algorithm that has lowered this bound's dependence on finite $t$ in the worst-case to our knowledge and establishes how to obtain further such reductions in $t$.

arXiv:2104.07250•Apr 15, 2021•0 citations

Asymptotically Tight Simulation of Universal Quantum Circuits.

Lucas Kocia

We are rapidly reaching the point with today's quantum computers where we will be unable to verify their outcomes with our current classical computers.Arguably, in some applications, this threshold has already been reached [1].Soon this may also be the case with fault-tolerant or near-term intermediate-scale quantum (NISQ) computers [2] that implement useful quantum algorithms.Validating the performance of NISQ devices and establishing a clearly-dened threshold for when they can outperform current computers is accomplished by directly simulating their outcomes on classical computers.The community needs more ecient classical algorithms and they need to know how much more ecient they can get.This last desired quality is often missing in currently available methods.Here, we accomplish both of these goals.Universal quantum computation requires a universal gateset, appropriate initial states and set of measurements.A common universal set that is widely used consists of stabilizer states, the Cliord+T gateset, and Pauli measurements.For classical computers, simulating everything other than the T gates can be done very eciently in polynomial time [3].On the other hand, T gates have been found to be exponentially dicult to simulate.Fortunately, classical simulation of universal quantum outcomes is made easier somewhat by the fact that quantum computers only produce output up to additive error [4], and so there is a priori no reason to simulate their outcomes beyond this.Simulating a given state as it undergoes Cliord and T gate unitary evolution up to some additive error is an L 1 minimization problem, which are known to scale more favorably compared to L 0 or L 2 minimizations appropriate when there are more stringent error constraints.The most natural state decomposition that is used for such classical simulation is the stabilizer state decomposition, because classical computers can calculate their inner products especially eciently.The corresponding number of these stabilizer states sucient for additive error decompositions is called the stabilizer extent.Current state-of-the-art classical simulators of quantum outcomes from this gateset scale as O(ξ t δ -2 ) [57] and O(ξ t δ -1 ) [8], where ξ t ≡ 2 ∼0.228t is the stabilizer extent of the T gate magic state and δ is the additive error.Furthermore, it is conjectured [6] that this asymptotic scaling is tight w.r.t.t.The most promising route to nd reductions in this algorithm is to look for at the next-order terms.f t : Reduction Relative Reduction Compared to i.d.d.Sampling w.r.t.t t FIG. 1. [From Technical Paper #1] The relative improvement in scaling w.r.t.t produced by correlated sampling with dierent 0 ≤ ft ≤ O(ξ 2t/3 ) compared to the state-of-the-art.In practice, the desired δ determines which ft you can attain:Despite their dimunitive name, next-order eects can oer signicant improvements for the intermediate (nonasymptotic) t regime, which is precisely the regime that NISQ devices are in.For a sense of this, see Figure 1 for a preview of the relative improvement in scaling that can be attained from including such next-order terms.Unfortunately, existing methods all saturate the asymptotic conjectured lower bound w.r.t.t even when they are not in the asymptotic limit of t → ∞ and it is not immediately clear how to extend them to next order in t.We take a rst crack at this problem in [9] (attached Technical Paper #2) and introduce the tool of correlated L 1 sampling.The main technique that we use is supplementing independent L 1 sampling with correlated samples of dissimilar states that lead to a better average.Given an ensemble of M independently sampled states, which have an SAND2021-13613CThis paper describes objective technical results and analysis.Any subjective views or opinions that might be expressed in the paper do not necessarily represent the views of the U.S.

•Oct 1, 2021•4 citations

Fast classical simulation algorithms for free-fermion dynamics with magic input

Jiwon Heo, Oliver Reardon-Smith, Michał Oszmaniec +2 more

The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of $n$ copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost $O(2^n)$ per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in $n$ and the inverse additive-error, for input states formed by products of $n$ four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.

quant-pharXiv:2609.40187•Oct 1, 2026•0 citations

Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits

Shigeo Hakkaku, Keisuke Fujii

Noise in quantum operations often negates the advantage of quantum computation. However, most classical simulations of quantum computers calculate the ideal probability amplitudes by either storing full state vectors or using sophisticated tensor-network contractions. Here we investigate sampling-based classical simulation methods for noisy quantum circuits. Specifically, we characterize the simulation costs of two major schemes, stabilizer-state sampling of magic states and Heisenberg propagation, for quantum circuits subject to stochastic Pauli noise, such as depolarizing and dephasing noise. To this end, we introduce several techniques for the stabilizer-state sampling to reduce the simulation costs under such noise. It is revealed that in the low-noise regime, stabilizer-state sampling results in a smaller sampling cost, while Heisenberg propagation is better in the high-noise regime. Furthermore, for a high depolarizing noise rate of approximately 10%, these methods provide better scaling than that given by the low-rank stabilizer decomposition. We believe that this knowledge of classical simulation costs is useful to achieve possible quantum advantage on near-term noisy quantum devices as well as efficient classical simulation methods.

arXiv:2011.06233•Physical Review Applied•Jun 10, 2021•4 citations

Weak Simulation v.0.1

Lucas Kocia

The SPARSIFY algorithm implemented by the code allows for classical simulation of universal quantum computer sample outcomes. The code sparsifies the stabilizer decomposition of a qubit t-tensored T gate magic state to some additive error. This is accomplished by either independent L1 sampling or with correlated L1 sampling to supplement an independent subset, which offers a more efficient decomposition: for a given t, a sparser decomposition is sufficient with correlated L1 sampling to satisfy a given additive error. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525. SAND2021-8296 O

•Jan 1, 2021•0 citations

Efficient Classical Simulation of Quantum Circuits beyond the Stabilizer Formalism

Patrick Rall, James E. Troupe

Bulletin of the American Physical Society•Mar 7, 2018•0 citations
Validating whether a quantum device confers a computational advantage often requires classical simulation of its outcomes. The worst-case sampling cost of L1L_1L1​-norm based simulation has plateaued at ≤(2+2)ξtδ−1\le(2+\sqrt{2})ξ_t δ^{-1}≤(2+2​)ξt​δ−1 in the limit that t→∞t \rightarrow \inftyt→∞, where δδδ is the additive error and ξtξ_tξt​ is the stabilizer extent of a ttt-qubit magic state. We reduce this prefactor 68-fold by a leading-order reduction in ttt through correlated sampling. The result exceeds even the average-case of the prior state-of-the-art and current simulators accurate to multiplicative error. Numerical demonstrations support our proofs. The technique can be applied broadly to reduce the cost of L1L_1L1​ minimization.
Improved Weak Simulation of Universal Quantum Circuits by Correlated L1L_1L1​ Sampling
Bounding the cost of classically simulating the outcomes of universal quantum circuits to additive error δδδ is often called weak simulation and is a direct way to determine when they confer a quantum advantage. Weak simulation of the TTT+Clifford gateset is BQPBQPBQP-complete and is expected to scale exponentially with the number ttt of TTT gates. We constructively tighten the upper bound on the worst-case L1L_1L1​ norm sampling cost to next order in ttt from O(ξtδ−2)\mathcal O(ξ^t δ^{-2})O(ξtδ−2) if δ2≫ξ−tδ^2 \gg ξ^{-t}δ2≫ξ−t to O((ξt−t)δ−2)\mathcal O((ξ^t{-}t) δ^{-2} )O((ξt−t)δ−2) if δ2≫(ξt−t)−1δ^2 \gg (ξ^t -t)^{-1}δ2≫(ξt−t)−1, where ξt=2∼0.228tξ^t = 2^{\sim 0.228 t}ξt=2∼0.228t is the stabilizer extent of the ttt-tensored TTT gate magic state. We accomplish this by replacing independent L1L_1L1​ sampling in the popular SPARSIFY algorithm used in many weak simulators with correlated L1L_1L1​ sampling. As an aside, this result demonstrates that the TTT gate magic state's approximate stabilizer state decomposition is not multiplicative with respect to ttt, for finite values, despite the multiplicativity of its stabilizer extent. This is the first weak simulation algorithm that has lowered this bound's dependence on finite ttt in the worst-case to our knowledge and establishes how to obtain further such reductions in ttt.
We are rapidly reaching the point with today's quantum computers where we will be unable to verify their outcomes with our current classical computers.Arguably, in some applications, this threshold has already been reached [1].Soon this may also be the case with fault-tolerant or near-term intermediate-scale quantum (NISQ) computers [2] that implement useful quantum algorithms.Validating the performance of NISQ devices and establishing a clearly-dened threshold for when they can outperform current computers is accomplished by directly simulating their outcomes on classical computers.The community needs more ecient classical algorithms and they need to know how much more ecient they can get.This last desired quality is often missing in currently available methods.Here, we accomplish both of these goals.Universal quantum computation requires a universal gateset, appropriate initial states and set of measurements.A common universal set that is widely used consists of stabilizer states, the Cliord+T gateset, and Pauli measurements.For classical computers, simulating everything other than the T gates can be done very eciently in polynomial time [3].On the other hand, T gates have been found to be exponentially dicult to simulate.Fortunately, classical simulation of universal quantum outcomes is made easier somewhat by the fact that quantum computers only produce output up to additive error [4], and so there is a priori no reason to simulate their outcomes beyond this.Simulating a given state as it undergoes Cliord and T gate unitary evolution up to some additive error is an L 1 minimization problem, which are known to scale more favorably compared to L 0 or L 2 minimizations appropriate when there are more stringent error constraints.The most natural state decomposition that is used for such classical simulation is the stabilizer state decomposition, because classical computers can calculate their inner products especially eciently.The corresponding number of these stabilizer states sucient for additive error decompositions is called the stabilizer extent.Current state-of-the-art classical simulators of quantum outcomes from this gateset scale as O(ξ t δ -2 ) [57] and O(ξ t δ -1 ) [8], where ξ t ≡ 2 ∼0.228t is the stabilizer extent of the T gate magic state and δ is the additive error.Furthermore, it is conjectured [6] that this asymptotic scaling is tight w.r.t.t.The most promising route to nd reductions in this algorithm is to look for at the next-order terms.f t : Reduction Relative Reduction Compared to i.d.d.Sampling w.r.t.t t FIG. 1. [From Technical Paper #1] The relative improvement in scaling w.r.t.t produced by correlated sampling with dierent 0 ≤ ft ≤ O(ξ 2t/3 ) compared to the state-of-the-art.In practice, the desired δ determines which ft you can attain:Despite their dimunitive name, next-order eects can oer signicant improvements for the intermediate (nonasymptotic) t regime, which is precisely the regime that NISQ devices are in.For a sense of this, see Figure 1 for a preview of the relative improvement in scaling that can be attained from including such next-order terms.Unfortunately, existing methods all saturate the asymptotic conjectured lower bound w.r.t.t even when they are not in the asymptotic limit of t → ∞ and it is not immediately clear how to extend them to next order in t.We take a rst crack at this problem in [9] (attached Technical Paper #2) and introduce the tool of correlated L 1 sampling.The main technique that we use is supplementing independent L 1 sampling with correlated samples of dissimilar states that lead to a better average.Given an ensemble of M independently sampled states, which have an SAND2021-13613CThis paper describes objective technical results and analysis.Any subjective views or opinions that might be expressed in the paper do not necessarily represent the views of the U.S.
The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of nnn copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost O(2n)O(2^n)O(2n) per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in nnn and the inverse additive-error, for input states formed by products of nnn four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.
Noise in quantum operations often negates the advantage of quantum computation. However, most classical simulations of quantum computers calculate the ideal probability amplitudes by either storing full state vectors or using sophisticated tensor-network contractions. Here we investigate sampling-based classical simulation methods for noisy quantum circuits. Specifically, we characterize the simulation costs of two major schemes, stabilizer-state sampling of magic states and Heisenberg propagation, for quantum circuits subject to stochastic Pauli noise, such as depolarizing and dephasing noise. To this end, we introduce several techniques for the stabilizer-state sampling to reduce the simulation costs under such noise. It is revealed that in the low-noise regime, stabilizer-state sampling results in a smaller sampling cost, while Heisenberg propagation is better in the high-noise regime. Furthermore, for a high depolarizing noise rate of approximately 10%, these methods provide better scaling than that given by the low-rank stabilizer decomposition. We believe that this knowledge of classical simulation costs is useful to achieve possible quantum advantage on near-term noisy quantum devices as well as efficient classical simulation methods.
The SPARSIFY algorithm implemented by the code allows for classical simulation of universal quantum computer sample outcomes. The code sparsifies the stabilizer decomposition of a qubit t-tensored T gate magic state to some additive error. This is accomplished by either independent L1 sampling or with correlated L1 sampling to supplement an independent subset, which offers a more efficient decomposition: for a given t, a sparser decomposition is sufficient with correlated L1 sampling to satisfy a given additive error. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525. SAND2021-8296 O