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.
Fermionic Gaussian circuits can be simulated efficiently on a classical computer, but become universal when supplemented with non-Gaussian operations. Similar to stabilizer circuits augmented with non-stabilizer resources, these non-Gaussian circuits can be simulated classically using rank- or extent-based methods. These methods decompose non-Gaussian states or operations into Gaussian ones, with runtimes that scale polynomially with measures of non-Gaussianity such as the rank and the extent -- quantities that typically grow exponentially with the number of non-Gaussian resources. Current fermionic rank- and extent-based simulators have mostly been limited to Gaussian circuits with magic-state injection. Extending them to mixed states and non-unitary channels has been hindered by the lack of known extent-optimized decompositions for physically relevant gates and noisy channels. In this work, we address this gap. First, we derive analytic decompositions for key non-Gaussian gates and channels, including decompositions for arbitrary two-qubit fermionic gates which are provably optimal for diagonal gates or those acting on Jordan-Wigner-adjacent qubit pairs. Second, we show that stochastic Pauli noise can reduce the effective extent of non-Gaussian rotation gates, but that fermionic magic is substantially more robust to such noise than stabilizer magic. Finally, we demonstrate how these decompositions can accelerate classical sampling from the output distribution of a quantum circuit. This involves a generalization of existing sparsification methods, previously limited to convex-unitary channels, to circuits involving intermediate measurements and feed-forward. Our decompositions also yield speedups for emulating noisy Pauli rotations with quasiprobability simulators in the large-angle/arbitrary-strength-noise and small-angle/low-noise parameter regimes.
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.
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.
The Gottesman-Knill theorem says that a stabilizer circuit---that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates---can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely available program called CHP (CNOT-Hadamard-phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class $\ensuremath{\bigoplus}\mathsf{L}$, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any
n-qubit stabilizer circuit into a ``canonical form'' that requires at most
O(n2∕logn) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.