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$.
Improved Weak Simulation of Universal Quantum Circuits by Correlated L1 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 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 L1 norm sampling cost to next order in t from O(ξtδ−2) if δ2≫ξ−t to O((ξt−t)δ−2) if δ2≫(ξt−t)−1, where ξt=2∼0.228t is the stabilizer extent of the t-tensored T gate magic state. We accomplish this by replacing independent L1 sampling in the popular SPARSIFY algorithm used in many weak simulators with correlated L1 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.
Validating whether a quantum device confers a computational advantage often requires classical simulation of its outcomes. The worst-case sampling cost of L1-norm based simulation has plateaued at ≤(2+2)ξtδ−1 in the limit that t→∞, 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 L1 minimization.
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.
We find a scaling reduction in the stabilizer rank of the twelve-qubit tensored T gate magic state. This lowers its asymptotic bound to 2∼0.463t for multi-Pauli measurements on t magic states, improving over the best previously found bound of 2∼0.468t. We numerically demonstrate this reduction. This constructively produces the most efficient strong simulation algorithm of the Clifford+T gateset to relative or multiplicative error. We then examine the cost of Pauli measurement in terms of its Gauss sum rank, which is a slight generalization of the stabilizer rank and is a lower bound on its asymptotic scaling. We demonstrate that this lower bound appears to be tight at low t-counts, which suggests that the stabilizer rank found at the twelve-qubit state can be lowered further to 2∼0.449t and we prove and numerically show that this is the case for single-Pauli measurements. Our construction directly shows how the reduction at 12 qubits is iteratively based on the reduction obtained at 6, 3, 2, and 1 qubits. This explains why novel reductions are found at tensor factors for these number of qubit primitives, an explanation lacking previously in the literature. Furthermore, in the process we observe an interesting relationship between the T gate magic state's stabilizer rank and decompositions that are Clifford-isomorphic to a computational sub-basis tensored with single-qubit states that produce minimal unique stabilizer state inner products -- the same relationship that allowed for finding minimal numbers of unique Gauss sums in the odd-dimensional qudit Wigner formulation of Pauli measurements.
One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from O(elln2) to O(mn2), where ell is the total number of gates in the circuit, and m is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever ellggm. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of ketpsiotimesm, where ketpsi is either a magic state or an equatorial state. \nFor any single qubit magic state ketpsi, we find stabilizer decompositions of ketpsiotimesm with 2mlog2(3)/4 terms. This improves on the best known bound of 2mlog2(7)/6. \nSimilarly, for any single qubit equatorial state ketpsi, we give a stabilizer decomposition of ketpsiotimesm with 2m/2 terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail, d-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo d>2. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd d, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even d case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.
Bravyi and Gosset [S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016)] recently gave classical simulation algorithms for quantum circuits dominated by Clifford operations. These algorithms scale exponentially with the number of T gates in the circuit, but polynomially in the number of qubits and Clifford operations. Here we extend their algorithm to qudits of odd prime dimension. We generalize their approximate stabilizer rank method for weak simulation to qudits and obtain the scaling of the approximate stabilizer rank with the number of single-qudit magic states. We also relate the canonical form of qudit stabilizer states to Gauss sum evaluations and give an O(n3) algorithm for calculating the inner product of two n-qudit stabilizer states.
Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T -gate layer or merely replacing all T gates with T 1 / 2 , the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1 / poly ( n ) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log ( n ) -sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.