Whether a class of quantum circuits can be efficiently simulated with a classical computer, or is provably hard to simulate, depends quite critically on the precise notion of “classical simulation”. We focus on two important notions of simulator, that we refer to as poly-boxes and EPSION-simulators and, discuss how other notions of simulation relate to these. A poly-box is a classical algorithm that outputs additive 1/poly precision estimates of Born probabilities and marginals. We present a general framework used to construct poly-boxes. This framework generalizes a number of recent works on simulation. As an application, we use the general framework to construct a classical additive 1/poly precision Born rule probability estimation algorithm for Clifford plus T circuits. Our algorithm scales exponentially in the number of T gates but polynomially in all other parameters and is intended to be state of the art for this estimation task. We expect this result to be particularly useful in the characterization and verification of near term quantum devices. We argue that the notion of classical simulation we call EPSION-simulation, captures the essence of possessing “equivalent computational power” to the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an EPSION-simulator from one possessing the simulated quantum system. We relate EPSION-simulation to various alternative notions of simulation predominantly focusing on its relation to poly-boxes. Accepting some plausible computational theoretic assumptions, we show that EPSION-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to EPSION-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution (poly-sparsity).
Whether a class of quantum circuits can be efficiently simulated with a classical computer, or is provably hard to simulate, depends quite critically on the precise notion of “classical simulation”. We focus on two important notions of simulator, that we refer to as poly-boxes and EPSION-simulators and, discuss how other notions of simulation relate to these. A poly-box is a classical algorithm that outputs additive 1/poly precision estimates of Born probabilities and marginals. We present a general framework used to construct poly-boxes. This framework generalizes a number of recent works on simulation. As an application, we use the general framework to construct a classical additive 1/poly precision Born rule probability estimation algorithm for Clifford plus T circuits. Our algorithm scales exponentially in the number of T gates but polynomially in all other parameters and is intended to be state of the art for this estimation task. We expect this result to be particularly useful in the characterization and verification of near term quantum devices. We argue that the notion of classical simulation we call EPSION-simulation, captures the essence of possessing “equivalent computational power” to the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an EPSION-simulator from one possessing the simulated quantum system. We relate EPSION-simulation to various alternative notions of simulation predominantly focusing on its relation to poly-boxes. Accepting some plausible computational theoretic assumptions, we show that EPSION-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to EPSION-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution (poly-sparsity).
Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of ``classical simulation'' and in particular on the required accuracy. We argue that a notion of classical simulation, which we call EPSILON-simulation (or ϵ -simulation for short), captures the essence of possessing ``equivalent computational power'' as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an ϵ -simulator from one possessing the simulated quantum system. We relate ϵ -simulation to various alternative notions of simulation predominantly focusing on a simulator we call a poly-box . A poly-box outputs 1/poly precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that ϵ -simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to ϵ -simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution ( poly-sparsity ).
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.
Determining the quantum-classical boundary between quantum circuits that can be efficiently simulated classically and those that cannot remains a fundamental question. One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented matrix product state (CAMPS), which, via a disentangling algorithm, decomposes the wave function into Clifford and MPS components, and from which Pauli expectation values can be computed in time polynomial in the MPS bond dimension. In this work, we develop an optimization-free disentangling (OFD) algorithm for Clifford circuits either doped with T gates or, equivalently, preceded by multiqubit gates of the form α I + β P . We give a simple and easily computed algebraic criterion that characterizes the individual quantum circuits for which OFD generates an efficient CAMPS—the bond dimension is exponential in the null space of a Galois binary field GF(2) matrix induced by a tableau of the twisted Pauli strings P . This significantly increases the number of circuits with rigorous polynomial-time classical simulations. We also give evidence that the typical N qubit random Clifford circuit doped with N uniformly distributed T gates of polylogarithmic depth or greater has a CAMPS with polynomial bond dimension. In addition, we compare OFD against disentangling by optimization. We further explore the representability of CAMPS for random Clifford circuits doped with more than N T gates. We also propose algorithms for sampling, probability, and amplitude estimation of bitstrings, and evaluation of entanglement Rényi entropy from CAMPS, which, though still having exponential complexity, are more efficient than standard MPS simulations. This work establishes a versatile framework for understanding classical simulatability of Clifford + T circuits and explores the interplay between quantum entanglement and quantum magic in quantum systems.
We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained for quantum circuits which---without the additional sparsity promise---are considered hard to simulate. Our results apply in particular to a family of Fourier sampling circuits (which have structural similarities to Shor's factoring algorithm) but also to several other circuit families, such as IQP circuits. Our results provide examples of quantum circuits that cannot achieve exponential speed-ups due to the presence of too much destructive interference i.e. too many cancelations of amplitudes. The crux of our classical simulation is an efficient algorithm for approximating the significant Fourier coefficients of a class of states called computationally tractable states. The latter result may have applications beyond the scope of this work. In the proof we employ and extend sparse approximation techniques, in particular the Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits.
We study the classical simulability of a polynomial-size quantum circuit Cn on n qubits followed by sparse classical post-processing (SCP) on m bits, where m≤n≤poly(m). The SCP is described by a non-zero Boolean function fm that is classically computable in polynomial time and is sparse, i.e., has a peaked Fourier spectrum. First, we provide a necessary and sufficient condition on Cn such that, for any SCP fm, Cn followed by fm is classically simulable. This characterization extends the result of Van den Nest and implies that various quantum circuits followed by SCP are classically simulable. Examples include IQP circuits, Clifford Magic circuits, and the quantum part of Simon's algorithm, even though these circuits alone are hard to simulate classically. Then, we consider the case where Cn has constant depth d. While it is unlikely that, for any SCP fm, Cn followed by fm is classically simulable, we show that it is simulable by a polynomial-time probabilistic algorithm with access to commuting quantum circuits on n+1 qubits. Each such circuit consists of at most deg(fm) commuting gates and each commuting gate acts on at most 2d+1 qubits, where deg(fm) is the Fourier degree of fm. This provides a better understanding of the hardness of simulating constant-depth quantum circuits followed by SCP.
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 (with scaling approximately equal to 1.17 t for T gates).Our algorithm is state of the art for this task: as an example, in approximately 13 h (on a standard desktop computer), we estimate 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.Our second algorithm, COMPUTE, calculates the probability of a chosen measurement outcome to machine precision with run time O 2 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 10 min using a single core of a standard desktop computer.We provide a C+Python implementation of our algorithms and benchmark them using random circuits, the hidden-shift algorithm, and the quantum approximate optimization algorithm.