One of the core research questions in the theory of quantum computing is to find out to what precise extent the classical simulation of a noisy quantum circuits is possible and where potential quantum advantages can set in. In this work, we introduce a unified framework for the classical simulation of quantum circuits based on frame theory, encompassing and generalizing a broad class of existing simulation strategies. Within this framework, the computational cost of a simulation algorithm is determined by the one-norm of an associated quasi-probability distribution, providing a common quantitative measure across different simulation approaches. This enables a comprehensive perspective on common methods for the simulation of noisy circuits based on different quantum resources, such as entanglement or non-stabilizerness. It further provides a clear scheme for generating novel classical simulation algorithms. Indeed, by exploring different choices of frames within this formalism and resorting to tools of convex optimization, we are able not only to obtain new insights and improved bounds for existing methods -- such as stabilizer state simulation or Pauli back-propagation -- but also to discover a new approach with an improved performance based on a generalization of the Pauli frame. We, thereby, show that classical simulation techniques can directly benefit from a perspective -- that of frames -- that goes beyond the traditional classification of quantum resources.
One of the core research questions in the theory of quantum computing is to find out to what precise extent the classical simulation of a noisy quantum circuits is possible and where potential quantum advantages can set in. In this work, we introduce a unified framework for the classical simulation of quantum circuits based on frame theory, encompassing and generalizing a broad class of existing simulation strategies. Within this framework, the computational cost of a simulation algorithm is determined by the one-norm of an associated quasi-probability distribution, providing a common quantitative measure across different simulation approaches. This enables a comprehensive perspective on common methods for the simulation of noisy circuits based on different quantum resources, such as entanglement or non-stabilizerness. It further provides a clear scheme for generating novel classical simulation algorithms. Indeed, by exploring different choices of frames within this formalism and resorting to tools of convex optimization, we are able not only to obtain new insights and improved bounds for existing methods -- such as stabilizer state simulation or Pauli back-propagation -- but also to discover a new approach with an improved performance based on a generalization of the Pauli frame. We, thereby, show that classical simulation techniques can directly benefit from a perspective -- that of frames -- that goes beyond the traditional classification of quantum resources.
We develop analytical and algorithmic techniques that enable efficient simulation of a broad class of noisy stabilizer circuits. We derive closed-form expressions of expectation values for tensor product of Paulis in circuits with non-deterministic Pauli measurements, yielding an efficient strong simulation method that avoids explicit density matrix construction and enables direct noise parameter sweeps. We introduce a circuit compression framework that reduces the per-sample cost of weak simulation in general noisy stabilizer circuits, including deterministic measurements, by separating parameter-independent preprocessing from sampling. Finally, we extend the analytical framework beyond its standard domain to include a small number of deterministic measurements, general rotations, and non-diagonal noise channels. Our results provide a unified framework for both strong and weak simulation of noisy stabilizer circuits and corresponds to an extension of the noisy stabilizer formalism introduced in \cite{PhysRevA.107.032424}. They offer applications ranging from calculation of the expectation values of entanglement witnesses, determination of reduced states, to energy evaluation.
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.
As quantum devices continue to improve in scale and precision, a central challenge is how to effectively utilize noisy hardware for meaningful computation. Most existing approaches aim to recover noiseless circuit outputs from noisy ones through error mitigation or correction. Here, we show that noisy quantum devices can be directly leveraged as computational resources to enhance the classical simulation of quantum circuits. We introduce the Noisy-device-enhanced Classical Simulation (NDE-CS) protocol, which improves stabilizer-based classical Monte Carlo simulation methods by incorporating data obtained from noisy quantum hardware. Specifically, NDE-CS uses noisy executions of a target circuit together with noisy Clifford circuits to learn how the target circuit can be expressed in terms of Clifford circuits under realistic noise. The same learned relation can then be reused in the noiseless Clifford limit, enabling accurate estimation of ideal expectation values with substantially reduced sampling cost. Numerical simulations on Trotterized Ising circuits demonstrate that NDE-CS achieves orders-of-magnitude reductions in sampling cost compared to the underlying purely classical Monte Carlo approaches from which it is derived, while maintaining the same accuracy. We also compare NDE-CS with Sparse Pauli Dynamics (SPD), a powerful classical framework capable of simulating quantum circuits at previously inaccessible scales, and provide an example where the cost of SPD scales exponentially with system size, while NDE-CS scales much more favorably. These results establish NDE-CS as a scalable hybrid simulation approach for quantum circuits, where noise can be harnessed as a computational asset.
It is widely believed that quantum computation has the potential to offer an ex- ponential speedup over classical devices. However, there is currently no definitive proof of this separation in computational power. Such a separation would in turn imply that quantum circuits cannot be efficiently simulated classically. However, it is well known that certain classes of quantum computations nonetheless admit an efficient classical description. Recent work has also argued that efficient classical simulation of quantum circuits would imply the collapse of the Polynomial Hierarchy, something which is commonly invoked in clas- sical complexity theory as a no-go theorem. This suggests a route for studying this ‘quantum advantage’ through classical simulations. This project looks at the problem of classically simulating quantum circuits through decompositions into stabilizer circuits. These are a restricted class of quantum computation which can be efficiently simulated classically. In this picture, the rank of the decomposition determines the temporal and spatial complexity of the simulation. We approach the problem by considering classical simulations of stabilizer circuits, introducing two new representations with novel features compared to previous meth- ods. We then examine techniques for building these so-called ‘stabilizer rank’ decom- positions, both exact and approximate. Finally, we combine these two ingredients to introduce an improved method for classically simulating broad classes of circuits using the stabilizer rank method.
It is one of the most fundamental objectives in quantum information science to understand the boundary between the computational power of classical and quantum computers. One possible avenue to explore this boundary is to identify classes of quantum circuits that can be efficiently simulated on a classical computer. Instead of simulating a general quantum circuit with a classical device, new schemes have recently emerged to simulate them on a quantum device that is restricted in some manner. As such, these techniques allow us to study how the restrictions impact the computational power of the device. One such technique is called quasiprobability simulation (QPS) and it estimates the result of a quantum circuit with a Monte Carlo procedure that randomly replaces circuit elements with ones that can be executed on the restricted quantum device. The main focus of this thesis is dedicated to the QPS-based simulation of nonlocal quantum computation using local quantum operations. On the practical side, this enables the simulation of large quantum circuits using multiple smaller quantum devices - a procedure that is sometimes called circuit knitting. We uncover a rich mathematical formalism with many connections to the resource theory of entanglement. We characterize the optimal simulation overhead for a broad range of practically relevant nonlocal states and channels and we explicitly provide achieving protocols. Moreover, we also investigate the utility of classical communication between the local parties. Our results address both the single-shot and asymptotic regime. We frame QPS in a quantum resource theoretic framework, which highlights similarities that arise in the different instantiations of the technique. Furthermore, we study the importance of classical side information in the QPS procedure and how it impacts the overhead and expressibility of QPS.
Accurately estimating observables on noisy quantum devices remains a central challenge for near-term quantum algorithms. While quantum error mitigation techniques can reduce noise-induced bias, they often rely on unverifiable assumptions about the circuit noise, and cannot guarantee the magnitude of residual bias error. Here, rather than using classical resources to mitigate a noisy quantum circuit execution, we propose a hybrid algorithm that uses quantum resources to improve the accuracy of approximate classical Pauli-path simulation. Our protocol, Quantum Enhanced Pauli Propagation (QuEPP), uses Clifford perturbation theory (CPT) to construct a classically simulable ensemble of Clifford circuits from the low-order terms in CPT, which directly provide the approximate classical Pauli-path simulation of the target circuit. Noisy quantum expectation values of this ensemble are then used to infer a global rescaling factor that corrects quantum execution of the target circuit, providing higher-order contributions absent from the truncated low-order classical simulation. This approach requires no noise characterization, applies to arbitrary circuits, and provides a provable route to asymptotically unbiased estimates. Using IBM Heron hardware, we demonstrate QuEPP on 2D random mirror circuits of up to 49 qubits and circuit depth 80, as well as Trotterized Hamiltonian evolution, showing consistent improvements beyond classical CPT and unmitigated quantum results. QuEPP offers a simple, scalable, and model-free framework for enabling accurate quantum computation in the pre-fault-tolerant era.