Consumption of magic states promotes the stabilizer model of computation to universal quantum computation.Here, we propose three different classical algorithms for simulating such universal quantum circuits, and characterize them by establishing precise connections with a family of magic monotones.Our first simulator introduces a new class of quasiprobability distributions and connects its runtime to a generalized notion of negativity.We prove that this algorithm has significantly improved exponential scaling compared to all prior quasiprobability simulators for qubits.Our second simulator is a new variant of the stabilizer-rank simulation algorithm, extended to work with mixed states and with significantly improved runtime bounds.Our third simulator trades precision for speed by discarding negative quasiprobabilities.We connect each algorithm's performance to a corresponding magic monotone and, by comprehensively characterizing the monotones, we obtain a precise understanding of the simulation runtime and error bounds.Our analysis reveals a deep connection between all three seemingly unrelated simulation techniques and their associated monotones.For tensor products of single-qubit states, we prove that our monotones are all equal to each other, multiplicative and efficiently computable, allowing us to make clear-cut comparisons of the simulators' performance scaling.Furthermore, our monotones establish several asymptotic and nonasymptotic bounds on state interconversion and distillation rates.Beyond the theory of magic states, our classical simulators can be adapted to other resource theories under certain axioms, which we demonstrate through an explicit application to the theory of quantum coherence.
Quantum circuit simulation is paramount to the verification and optimization of quantum algorithms, and considerable research efforts have been made towards efficient simulators. While circuits often contain high-level gates such as oracles and multi-controlled X ( C k X ) gates, existing simulation methods require compilation to a low-level gate-set before simulation. This, however, increases circuit size and incurs a considerable (typically exponential) overhead, even when the number of high-level gates is small. Here we present a gadget-based simulator which simulates high-level gates directly, thereby allowing to avoid or reduce the blowup of compilation. Our simulator uses a stabilizer decomposition of the magic state of non-stabilizer gates, with improvements in the rank of the magic state directly improving performance. We then proceed to establish a small stabilizer rank for a range of high-level gates that are common in various quantum algorithms. Using these bounds in our simulator, we improve both the theoretical complexity of simulating circuits containing such gates, and the practical running time compared to standard simulators found in IBM's Qiskit Aer library. We also derive exponential lower-bounds for the stabilizer rank of some gates under common complexity-theoretic hypotheses. In certain cases, our lower-bounds are asymptotically tight on the exponent.
Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits
n, even approximately. We reduce the problem to solving a
3-\class{SAT} instance on
n2 variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.
In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of m copies of the magic state | T ⟩ = 2 − 1 ( | 0 ⟩ + e i π / 4 | 1 ⟩ ) in the limit of large m . In particular, we show that | T ⟩ ⊗ m can be exactly expressed as a superposition of at most O ( 2 α m ) stabilizer states, where α ≤ 0.3963 , improving on the best previously known bound α ≤ 0.463 . This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an n -qubit Clifford + T circuit U with m uses of the T gate to within a given inverse polynomial relative error using a runtime p o l y ( n , m ) 2 α m . We also provide improved upper bounds on the stabilizer rank of symmetric product states | ψ ⟩ ⊗ m more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and m instances of any (fixed) single-qubit Z -rotation gate with runtime poly ( n , m ) 2 m / 2 . We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.
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.