Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1905.10724

Empirical determination of the simulation capacity of a near-term quantum computer

Rich Rines, Kevin Obenland, Isaac L. Chuang

Published May 26, 2019• 2 citations
arXivHTMLPDF

Abstract

Experimentally realizable quantum computers are rapidly approaching the threshold of quantum supremacy. Quantum Hamiltonian simulation promises to be one of the first practical applications for which such a device could demonstrate an advantage over all classical systems. However, these early devices will inevitably remain both noisy and small, precluding the use of quantum error correction. We use high-performance classical tools to construct, optimize, and simulate quantum circuits subject to realistic error models in order to empirically determine the "simulation capacity" of near-term simulation experiments implemented via quantum signal processing (QSP), describing the relationship between simulation time, system size, and resolution of QSP circuits which are optimally configured to balance algorithmic precision and external noise. From simulation capacity models, we estimate maximum tolerable error rate for meaningful simulation experiments on a near-term quantum computer. By exploiting symmetry inherent to the QSP circuit, we further demonstrate that its capacity for quantum simulation can be increased by at least two orders of magnitude if errors are systematic and unitary. We find that a device with $ε^2=10^{-5}$ systematic amplitude errors could meaningfully simulate systems up to $n\approx16$ with an expected failure rate below $10\%$, whereas the largest system a device with a stochastic error rate of $p_ε=10^{-5}$ could meaningfully simulate with the same rate of failure is between $n=3$ and $n=5$ (depending on the stochastic channel). Extrapolating from empirical results, we estimate that one would typically need a stochastic error rate below $p_ε=10^{-8}$ to perform a meaningful $n=50$ simulation experiment with a failure rate below $10\%$, while the same experiment could tolerate systematic unitary errors with strength $ε^2\approx10^{-6}$.

DOI
10.48550/arxiv.1905.10724

Related papers

Honest Approximations to Realistic Fault Models and Their Applications to Efficient Simulation of Quantum Error Correction

Daniel Puzzuoli

Understanding the performance of realistic noisy encoded circuits is an important task for the development of large-scale practical quantum computers. Specifically, the development of proposals for quantum computation must be well informed by both the qualities of the low-level physical system of choice, and the properties of the high-level quantum error correction and fault-tolerance schemes. Gaining insight into how a particular computation will play out on a physical system is in general a difficult problem, as the classical simulation of arbitrary noisy quantum circuits is inefficient. Nevertheless, important classes of noisy circuits can be simulated efficiently. Such simulations have led to numerical estimates of threshold errors rates and resource estimates in topological codes subject to efficiently simulable error models. \n \nThis thesis describes and analyzes a method that my collaborators and I have introduced for leveraging efficient simulation techniques to understand the performance of large quantum processors that are subject to errors lying outside of the efficient simulation algorithm's applicability. The idea is to approximate an arbitrary gate error with an error from the efficiently simulable set in a way that ``honestly'' represents the original error's ability to preserve or distort quantum information. After introducing and analyzing the individual gate approximation method, its utility as a means for estimating circuit performance is studied. In particular, the method is tested within the use-case for which it was originally conceived; understanding the performance of a hypothetical physical implementation of a quantum error-correction protocol. It is found that the method performs exactly as desired in all cases. That is, the circuits composed of the approximated error models honestly represent the circuits composed of the errors derived from the physical models.

•Apr 25, 2014•3 citations

Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?

Man‐Hong Yung, Xun Gao

Although the emergence of a fully-functional quantum computer may still be far away from today, in the near future, it is possible to have medium-size, special-purpose, quantum devices that can perform computational tasks not efficiently simulable with any classical computer. This status is known as quantum supremacy (or quantum advantage), where one of the promising approaches is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic quantum circuits has been argued to require an exponential time for classical devices. A major question is whether quantum supremacy can be maintained under noise without error correction, as the implementation of fault-tolerance would cost lots of extra qubits and quantum gates. Here we show that, for a family of chaotic quantum circuits subject to Pauli errors, there exists an non-exponential classical algorithm capable of simulating the noisy chaotic quantum circuits with bounded errors. This result represents a serious challenge to a previous result in the literature suggesting the failure of classical devices in simulating noisy chaotic circuits with about 48 qubits and depth 25. Moreover, even though our model does not cover all types of experimental errors, from a practical point view, our result describes a well-defined setting where quantum supremacy can be tested against the challenges of classical rivals, in the context of chaotic quantum circuits.

arXiv:1706.08913•Jun 27, 2017•8 citations

Toward the first quantum simulation with quantum speedup

Andrew M. Childs, Dmitri Maslov, Yunseong Nam +2 more

With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

arXiv:1711.10980•Proceedings of the National Academy of Sciences•Sep 6, 2018•551 citations

Realistic simulation of quantum computation using unitary and measurement channels

A. A. Mouedenne, Nader Khammassi, Koen Bertels +1 more

The implementation and practicality of quantum algorithms hinge largely on the quality of operations within a quantum processor. Therefore, including realistic error models in quantum computing simulation platforms is crucial for testing these algorithms. Existing classical simulation techniques of quantum information processing devices exhibit a tradeoff between scalability (the number of qubits that can be simulated) and accuracy (how close the simulation is to the target error model). In this paper, we introduce a simulation approach that relies on approximating the density matrix evolution with a stochastic sum of unitary and measurement channels within a pure-state simulation environment. This model shows an improvement of at least one order of magnitude in terms of accuracy compared to the best known stochastic approaches while allowing us to simulate a larger number of qubits compared to the exact density matrix simulation. Furthermore, we used this approach to realistically simulate Grover's algorithm and the surface code 17 using a gate set tomography characterization of quantum operations as a noise model.

arXiv:2005.06337•Physical Review A•Nov 9, 2020•9 citations

Ensemble-Based Quantum Signal Processing for Error Mitigation

Suying Liu, Yulong Dong, Dong An +1 more

Despite rapid advances in quantum hardware, noise remains a central obstacle to deploying quantum algorithms on near-term devices. In particular, random coherent errors that accumulate during circuit execution constitute a dominant and fundamentally challenging noise source. We introduce a noise-resilient framework for Quantum Signal Processing (QSP) that mitigates such coherent errors without increasing circuit depth or ancillary qubit requirements. Our approach uses ensembles of noisy QSP circuits combined with measurement-level averaging to suppress random phase errors in Z rotations. Building on this framework, we develop robust QSP algorithms for implementing polynomial functions of Hermitian matrices and for estimating observables, with applications to Hamiltonian simulation, quantum linear systems, and ground-state preparation. We analyze the trade-off between approximation error and hardware noise, which is essential for practical implementation under the stringent depth and coherence constraints of current quantum hardware. Our results establish a practical pathway for integrating error mitigation seamlessly into algorithmic design, advancing the development of robust quantum computing, and enabling the discovery of scientific applications with near- and mid-term quantum devices.

quant-pharXiv:2601.20073•Jan 29, 2026•0 citations

Noise Threshold of Quantum Supremacy

Keisuke Fujii

Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage against over the best classical algorithms by using less universal quantum devices, is an important near-term milestone for quantum information processing. Here we develop a threshold theorem for quantum supremacy with noisy quantum circuits in the pre-threshold region, where quantum error correction does not work directly. We show that, even in such a region, we can virtually simulate quantum error correction by postselection. This allows us to show that the output sampled from the noisy quantum circuits (without postselection) cannot be simulated efficiently by classical computers based on a stable complexity theoretical conjecture, i.e., non-collapse of the polynomial hierarchy. By applying this to fault-tolerant quantum computation with the surface codes, we obtain the threshold value $2.84\%$ for quantum supremacy, which is much higher than the standard threshold $0.75\%$ for universal fault-tolerant quantum computation with the same circuit-level noise model. Moreover, contrast to the standard noise threshold, the origin of quantum supremacy in noisy quantum circuits is quite clear; the threshold is determined purely by the threshold of magic state distillation, which is essential to gain a quantum advantage.

arXiv:1610.03632•Oct 12, 2016•16 citations
Experimentally realizable quantum computers are rapidly approaching the threshold of quantum supremacy. Quantum Hamiltonian simulation promises to be one of the first practical applications for which such a device could demonstrate an advantage over all classical systems. However, these early devices will inevitably remain both noisy and small, precluding the use of quantum error correction. We use high-performance classical tools to construct, optimize, and simulate quantum circuits subject to realistic error models in order to empirically determine the "simulation capacity" of near-term simulation experiments implemented via quantum signal processing (QSP), describing the relationship between simulation time, system size, and resolution of QSP circuits which are optimally configured to balance algorithmic precision and external noise. From simulation capacity models, we estimate maximum tolerable error rate for meaningful simulation experiments on a near-term quantum computer. By exploiting symmetry inherent to the QSP circuit, we further demonstrate that its capacity for quantum simulation can be increased by at least two orders of magnitude if errors are systematic and unitary. We find that a device with ε2=10−5ε^2=10^{-5}ε2=10−5 systematic amplitude errors could meaningfully simulate systems up to n≈16n\approx16n≈16 with an expected failure rate below 10%10\%10%, whereas the largest system a device with a stochastic error rate of pε=10−5p_ε=10^{-5}pε​=10−5 could meaningfully simulate with the same rate of failure is between n=3n=3n=3 and n=5n=5n=5 (depending on the stochastic channel). Extrapolating from empirical results, we estimate that one would typically need a stochastic error rate below pε=10−8p_ε=10^{-8}pε​=10−8 to perform a meaningful n=50n=50n=50 simulation experiment with a failure rate below 10%10\%10%, while the same experiment could tolerate systematic unitary errors with strength ε2≈10−6ε^2\approx10^{-6}ε2≈10−6.
Understanding the performance of realistic noisy encoded circuits is an important task for the development of large-scale practical quantum computers. Specifically, the development of proposals for quantum computation must be well informed by both the qualities of the low-level physical system of choice, and the properties of the high-level quantum error correction and fault-tolerance schemes. Gaining insight into how a particular computation will play out on a physical system is in general a difficult problem, as the classical simulation of arbitrary noisy quantum circuits is inefficient. Nevertheless, important classes of noisy circuits can be simulated efficiently. Such simulations have led to numerical estimates of threshold errors rates and resource estimates in topological codes subject to efficiently simulable error models. \n \nThis thesis describes and analyzes a method that my collaborators and I have introduced for leveraging efficient simulation techniques to understand the performance of large quantum processors that are subject to errors lying outside of the efficient simulation algorithm's applicability. The idea is to approximate an arbitrary gate error with an error from the efficiently simulable set in a way that ``honestly'' represents the original error's ability to preserve or distort quantum information. After introducing and analyzing the individual gate approximation method, its utility as a means for estimating circuit performance is studied. In particular, the method is tested within the use-case for which it was originally conceived; understanding the performance of a hypothetical physical implementation of a quantum error-correction protocol. It is found that the method performs exactly as desired in all cases. That is, the circuits composed of the approximated error models honestly represent the circuits composed of the errors derived from the physical models.
Although the emergence of a fully-functional quantum computer may still be far away from today, in the near future, it is possible to have medium-size, special-purpose, quantum devices that can perform computational tasks not efficiently simulable with any classical computer. This status is known as quantum supremacy (or quantum advantage), where one of the promising approaches is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic quantum circuits has been argued to require an exponential time for classical devices. A major question is whether quantum supremacy can be maintained under noise without error correction, as the implementation of fault-tolerance would cost lots of extra qubits and quantum gates. Here we show that, for a family of chaotic quantum circuits subject to Pauli errors, there exists an non-exponential classical algorithm capable of simulating the noisy chaotic quantum circuits with bounded errors. This result represents a serious challenge to a previous result in the literature suggesting the failure of classical devices in simulating noisy chaotic circuits with about 48 qubits and depth 25. Moreover, even though our model does not cover all types of experimental errors, from a practical point view, our result describes a well-defined setting where quantum supremacy can be tested against the challenges of classical rivals, in the context of chaotic quantum circuits.
With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.
The implementation and practicality of quantum algorithms hinge largely on the quality of operations within a quantum processor. Therefore, including realistic error models in quantum computing simulation platforms is crucial for testing these algorithms. Existing classical simulation techniques of quantum information processing devices exhibit a tradeoff between scalability (the number of qubits that can be simulated) and accuracy (how close the simulation is to the target error model). In this paper, we introduce a simulation approach that relies on approximating the density matrix evolution with a stochastic sum of unitary and measurement channels within a pure-state simulation environment. This model shows an improvement of at least one order of magnitude in terms of accuracy compared to the best known stochastic approaches while allowing us to simulate a larger number of qubits compared to the exact density matrix simulation. Furthermore, we used this approach to realistically simulate Grover's algorithm and the surface code 17 using a gate set tomography characterization of quantum operations as a noise model.
Despite rapid advances in quantum hardware, noise remains a central obstacle to deploying quantum algorithms on near-term devices. In particular, random coherent errors that accumulate during circuit execution constitute a dominant and fundamentally challenging noise source. We introduce a noise-resilient framework for Quantum Signal Processing (QSP) that mitigates such coherent errors without increasing circuit depth or ancillary qubit requirements. Our approach uses ensembles of noisy QSP circuits combined with measurement-level averaging to suppress random phase errors in Z rotations. Building on this framework, we develop robust QSP algorithms for implementing polynomial functions of Hermitian matrices and for estimating observables, with applications to Hamiltonian simulation, quantum linear systems, and ground-state preparation. We analyze the trade-off between approximation error and hardware noise, which is essential for practical implementation under the stringent depth and coherence constraints of current quantum hardware. Our results establish a practical pathway for integrating error mitigation seamlessly into algorithmic design, advancing the development of robust quantum computing, and enabling the discovery of scientific applications with near- and mid-term quantum devices.
Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage against over the best classical algorithms by using less universal quantum devices, is an important near-term milestone for quantum information processing. Here we develop a threshold theorem for quantum supremacy with noisy quantum circuits in the pre-threshold region, where quantum error correction does not work directly. We show that, even in such a region, we can virtually simulate quantum error correction by postselection. This allows us to show that the output sampled from the noisy quantum circuits (without postselection) cannot be simulated efficiently by classical computers based on a stable complexity theoretical conjecture, i.e., non-collapse of the polynomial hierarchy. By applying this to fault-tolerant quantum computation with the surface codes, we obtain the threshold value 2.84%2.84\%2.84% for quantum supremacy, which is much higher than the standard threshold 0.75%0.75\%0.75% for universal fault-tolerant quantum computation with the same circuit-level noise model. Moreover, contrast to the standard noise threshold, the origin of quantum supremacy in noisy quantum circuits is quite clear; the threshold is determined purely by the threshold of magic state distillation, which is essential to gain a quantum advantage.