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:2610.15210

Signal-to-noise problems in fault-tolerant quantum computation

Hyunwoo Oh

quant-phhep-latnucl-thSubmitted Oct 10, 2026• Announced Oct 13, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum computation offers a promising alternative to classical Monte Carlo methods by naturally avoiding sign problems through unitary evolution. A common misconception follows from this: because quantum simulation sidesteps the sign problem, it is often assumed to be an essentially perfect substitute for classical sampling. This is false---quantum measurements are intrinsically stochastic, and estimating observables often requires a number of samples that grows exponentially with system size, time separation, or inverse temperature, exactly as in the classical signal-to-noise problem. In this work, we analyze the origin and structure of signal-to-noise problems in quantum computation, drawing parallels with classical Monte Carlo, and demonstrate that such noise persists even in sign-problem-free regimes. We discuss strategies to mitigate it, in particular a quantum generalization of Stein control variates construction, in which unbiased estimators are built from operator commutators $[X,A]$ and their discrete diagonal counterparts, and validate the approach with exactly solvable numerical examples that quantify the achievable variance reduction. Our results underscore that variance reduction, not merely sign-problem avoidance, is required to make quantum algorithms practically viable for many-body physics.

AI Summary

The paper asks whether avoiding classical sign problems also removes statistical bottlenecks in fault-tolerant quantum simulation. It distinguishes sign-problem avoidance from measurement signal-to-noise: repeated projective measurements require $N\sim 1/(\epsilon^2\mathrm{SNR}^2)$ shots for relative precision $\epsilon$. For an assumed exponentially decaying correlator $|C(t)|\sim e^{-\gamma t}$ measured with order-one variance, this gives $N\sim e^{2\gamma t}/\epsilon^2$. Amplitude estimation can improve precision scaling but does not generally eliminate exponential costs for exponentially small signals. The proposed variance-reduction framework replaces $O$ by $O-f$, using operators with known zero expectation. For stationary states, $f=[X,A]$ has zero mean whenever $[X,\rho]=0$; taking $X$ anti-Hermitian and $A$ Hermitian makes $f$ measurable as a Hermitian observable. A nondegenerate generator spans the off-diagonal sector, while a discrete construction using thermal population ratios covers the diagonal zero-mean sector. For a linear ansatz, variance minimization becomes a positive-semidefinite quadratic problem with formal solution $\theta^*=M^{-1}v$. Analytic examples include transverse-noise cancellation in a qubit and zero-variance kinetic-energy estimation for harmonic-oscillator energy eigenstates. Exact finite-shot simulations report variance reductions of factors $9.0$ and $9.2$ in one- and two-qubit thermal models, respectively, retaining $1/\sqrt{N}$ error scaling. Validation is restricted to exactly solvable small systems. For larger systems, estimating the optimization matrix requires $O(k^2)$ expectation values for $k$ ansatz directions; circuit-based variational optimization is suggested but left for future work.

Likely largely AI-generatedOverclaimsSmall numerics onlyUnclear noveltyPossible error

Error found: The Schwinger-model example assumes an exponential correlator envelope without establishing a regime where it applies or removing the potentially nonzero disconnected contribution. The asserted equality between path-integral sampling variance and quantum operator variance is false in general because their second-moment estimators need not coincide. The single-qubit projective-variance demonstration does not justify the claim that its reduction requires only classical post-processing of existing measurement data. The combined control-variate construction spans Hermitian operators with zero thermal expectation, not the ordinary traceless Hermitian operators claimed in the text.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
7 pages, 1 figure

Related papers

Quantum-classical crossover in fault-tolerant quantum dynamics simulation

Jinzhao Sun, Bozhen Zhou, Jue Xu +28 more

While quantum computers promise to solve classically intractable problems, identifying the point at which fault-tolerant quantum computation outperforms the best classical algorithms for practical applications remains an outstanding challenge. Here we establish a concrete quantum-classical crossover for quantum many-body dynamics under realistic hardware conditions. We introduce a scalable fault-tolerant framework that combines coherent observable estimation with a space-time-efficient implementation of non-Clifford rotations, suppressing the residual logical errors that limit existing partially fault-tolerant approaches. A benchmark against state-of-the-art tensor-network and variational Monte Carlo algorithms reveals a concrete crossover for mixed-field Ising dynamics at modest system sizes. For a physical error rate of $p=10^{-3}$, fault-tolerant simulation requires approximately 2 hours and $3.7 \times 10^5$ physical qubits for a 100-site 1D system, whereas tensor network approaches would require about 100 years. For 2D models, where rapid entanglement growth limits the classical evolution time, we project quantum runtimes within minutes. A physical error rate of $p=10^{-4}$ leads to at least an order of magnitude reduction in qubit count ($3.1 \times 10^4$ physical qubits) and runtime (minutes for 1D and seconds for 2D). The reduction in quantum runtime arises from our improved rotation-state injection and co-design of quantum error correction and observable-estimation protocols, which jointly suppress logical-error accumulation and reduce sampling overhead. Our results establish a scalable route towards practical quantum advantage and identify quantitative engineering targets for future fault-tolerant architectures.

quant-pharXiv:2607.16116•Jul 20, 2026•4 citations

Quantum computing quantum Monte Carlo algorithm

Yukun Zhang, Yifei Huang, Jinzhao Sun +2 more

Quantum computing and quantum Monte Carlo (QMC) are respectively the state-of-the-art quantum and classical computing methods for understanding many-body quantum systems. Here, we propose a hybrid quantum-classical algorithm that integrates these two methods, inheriting their distinct features in efficient representation and manipulation of quantum states and overcoming their limitations. We first introduce non-stoquasticity indicators (NSIs) and their upper bounds, which measure the sign problem, the most notable limitation of QMC. We show that our algorithm could greatly mitigate the sign problem, which decreases NSIs with the assistance of quantum computing. Meanwhile, the use of quantum Monte Carlo also increases the expressivity of shallow quantum circuits, allowing more accurate computation that is conventionally achievable only with much deeper circuits. We numerically test and verify the method for the N$_2$ molecule (12 qubits) and the Hubbard model (16 qubits). Our work paves the way to solving practical problems with intermediate-scale and early-fault tolerant quantum computers, with potential applications in chemistry, condensed matter physics, materials, high energy physics, etc.

arXiv:2206.10431•Physical Review A•Jul 21, 2025•33 citations

Accelerated Quantum Monte Carlo with Mitigated Error on Noisy Quantum Computer

Yongdan Yang, Bing-Nan Lu, Ying Li

Quantum Monte Carlo and quantum simulation are both important tools for understanding quantum many-body systems.As a classical algorithm, quantum Monte Carlo suffers from the sign problem, preventing its application to most fermion systems and real-time dynamics.In this paper, we introduce a novel nonvariational algorithm using quantum simulation as a subroutine to accelerate quantum Monte Carlo by easing the sign problem.The quantum subroutine can be implemented with shallow circuits and, by incorporating error mitigation, can reduce the Monte Carlo variance by several orders of magnitude even when the circuit noise is significant.As such, the proposed quantum algorithm is applicable to near-term noisy quantum hardware.

arXiv:2106.09880•PRX Quantum•Dec 29, 2021•32 citations

Sign-problem free quantum stochastic series expansion algorithm on a quantum computer

Kok Chuan Tan, Dhiman Bhowmick, Pinaki Sengupta

Abstract A quantum implementation of the Stochastic Series Expansion (SSE) Monte Carlo method is proposed, and is shown to offer significant advantages over classical implementations of SSE. In particular, for problems where classical SSE encounters the sign problem, the cost of implementing a Monte Carlo iteration scales only linearly with system size in quantum SSE, while it may scale exponentially with system size in classical SSE. In cases where classical SSE can be efficiently implemented, quantum SSE still offers an advantage by allowing for more general observables to be measured.

arXiv:2010.00949•npj Quantum Information•Apr 26, 2022•16 citations

Hybrid Quantum-Classical Methods for Noisy Intermediate Scaling Quantum Machines

Diksha Dhawan

The accurate and efficient simulation of many body systems has been a long-standing challenge for quantum chemists and physicists. At the heart of this challenge lies the correlation between quantum particles, which is crucial in understanding various physical phenomena, but is numerically hard to calculate. Over the decades, there has been remarkable progress in simplifying this problem aided by mathematical and chemical approximations and the availability of powerful computers. However, an exact solution to the problem still remains intractable as it requires exponential re- sources with respect to the system size. Recent advances in the field of quantum computing have shown promise in Feynman’s idea of simulating quantum mechanics on quantum computers. It has been proposed that an ideal fault-tolerant quantum computer can reduce the scaling of these sim- ulations from exponential to polynomial. However, initial quantum algorithms have shown that there is a large gap between the capabilities of current hardware and the resources required for simulating quantum systems of interest. The work of this thesis focuses on reducing this gap by introducing two novel algorithms for quantum xiv chemistry simulations, which are suitable for near-term hardware. First, we intro- duce a hybrid algorithm to decrease the total number of operations required for the quantum simulations. We use a classical computer to generate an effective Hamilto- nian containing O(n2) terms compared to the O(n4) terms of the full Hamiltonian, where n is the number of orbitals. This sparse Hamiltonian can then be used with a high-level method to recover the ground state energies. We demonstrate that this sparsification of the Hamiltonian reduces the number of quantum operations required for the simulation by an order of magnitude, thus making it accessible for the near- term Hardware. Our second algorithm aims to make the calculation of dynamic correlation functions (Green’s functions) more feasible on these quantum machines. This algorithm is designed with the motive of avoiding the use of time-evolution and reduced use of two-qubit gates. We demonstrate that we can reproduce the Green’s function within reasonable error limits using this approach. We have also discussed the use of re-sampling techniques for proper error-propagation of the stochastic data obtained from the quantum machines. The general structure of this thesis is as follows. We begin by motivating this work in Chapter 1. Chapters 2 and 3 provide a general introduction of quantum computing and Green’s function based methods, respectively. In chapter 4, the development of effective Hamiltonian is discussed in detail. Chapter 5 demonstrates the use of these effective Hamiltonians on the quantum machine for time evolution. In chapter 6, we have discussed the algorithm to calculate Green’s functions on a quantum machine. This is followed by conclusions and future directions in Chapters 7 and 8, respectively.

•Jan 1, 2022•0 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
Quantum computation offers a promising alternative to classical Monte Carlo methods by naturally avoiding sign problems through unitary evolution. A common misconception follows from this: because quantum simulation sidesteps the sign problem, it is often assumed to be an essentially perfect substitute for classical sampling. This is false---quantum measurements are intrinsically stochastic, and estimating observables often requires a number of samples that grows exponentially with system size, time separation, or inverse temperature, exactly as in the classical signal-to-noise problem. In this work, we analyze the origin and structure of signal-to-noise problems in quantum computation, drawing parallels with classical Monte Carlo, and demonstrate that such noise persists even in sign-problem-free regimes. We discuss strategies to mitigate it, in particular a quantum generalization of Stein control variates construction, in which unbiased estimators are built from operator commutators [X,A][X,A][X,A] and their discrete diagonal counterparts, and validate the approach with exactly solvable numerical examples that quantify the achievable variance reduction. Our results underscore that variance reduction, not merely sign-problem avoidance, is required to make quantum algorithms practically viable for many-body physics.
The paper asks whether avoiding classical sign problems also removes statistical bottlenecks in fault-tolerant quantum simulation. It distinguishes sign-problem avoidance from measurement signal-to-noise: repeated projective measurements require N∼1/(ϵ2SNR2)N\sim 1/(\epsilon^2\mathrm{SNR}^2)N∼1/(ϵ2SNR2) shots for relative precision ϵ\epsilonϵ. For an assumed exponentially decaying correlator ∣C(t)∣∼e−γt|C(t)|\sim e^{-\gamma t}∣C(t)∣∼e−γt measured with order-one variance, this gives N∼e2γt/ϵ2N\sim e^{2\gamma t}/\epsilon^2N∼e2γt/ϵ2. Amplitude estimation can improve precision scaling but does not generally eliminate exponential costs for exponentially small signals.
The proposed variance-reduction framework replaces OOO by O−fO-fO−f, using operators with known zero expectation. For stationary states, f=[X,A]f=[X,A]f=[X,A] has zero mean whenever [X,ρ]=0[X,\rho]=0[X,ρ]=0; taking XXX anti-Hermitian and AAA Hermitian makes fff measurable as a Hermitian observable. A nondegenerate generator spans the off-diagonal sector, while a discrete construction using thermal population ratios covers the diagonal zero-mean sector. For a linear ansatz, variance minimization becomes a positive-semidefinite quadratic problem with formal solution θ∗=M−1v\theta^*=M^{-1}vθ∗=M−1v.
Analytic examples include transverse-noise cancellation in a qubit and zero-variance kinetic-energy estimation for harmonic-oscillator energy eigenstates. Exact finite-shot simulations report variance reductions of factors 9.09.09.0 and 9.29.29.2 in one- and two-qubit thermal models, respectively, retaining 1/N1/\sqrt{N}1/N​ error scaling. Validation is restricted to exactly solvable small systems. For larger systems, estimating the optimization matrix requires O(k2)O(k^2)O(k2) expectation values for kkk ansatz directions; circuit-based variational optimization is suggested but left for future work.
While quantum computers promise to solve classically intractable problems, identifying the point at which fault-tolerant quantum computation outperforms the best classical algorithms for practical applications remains an outstanding challenge. Here we establish a concrete quantum-classical crossover for quantum many-body dynamics under realistic hardware conditions. We introduce a scalable fault-tolerant framework that combines coherent observable estimation with a space-time-efficient implementation of non-Clifford rotations, suppressing the residual logical errors that limit existing partially fault-tolerant approaches. A benchmark against state-of-the-art tensor-network and variational Monte Carlo algorithms reveals a concrete crossover for mixed-field Ising dynamics at modest system sizes. For a physical error rate of p=10−3p=10^{-3}p=10−3, fault-tolerant simulation requires approximately 2 hours and 3.7×1053.7 \times 10^53.7×105 physical qubits for a 100-site 1D system, whereas tensor network approaches would require about 100 years. For 2D models, where rapid entanglement growth limits the classical evolution time, we project quantum runtimes within minutes. A physical error rate of p=10−4p=10^{-4}p=10−4 leads to at least an order of magnitude reduction in qubit count (3.1×1043.1 \times 10^43.1×104 physical qubits) and runtime (minutes for 1D and seconds for 2D). The reduction in quantum runtime arises from our improved rotation-state injection and co-design of quantum error correction and observable-estimation protocols, which jointly suppress logical-error accumulation and reduce sampling overhead. Our results establish a scalable route towards practical quantum advantage and identify quantitative engineering targets for future fault-tolerant architectures.
Quantum computing and quantum Monte Carlo (QMC) are respectively the state-of-the-art quantum and classical computing methods for understanding many-body quantum systems. Here, we propose a hybrid quantum-classical algorithm that integrates these two methods, inheriting their distinct features in efficient representation and manipulation of quantum states and overcoming their limitations. We first introduce non-stoquasticity indicators (NSIs) and their upper bounds, which measure the sign problem, the most notable limitation of QMC. We show that our algorithm could greatly mitigate the sign problem, which decreases NSIs with the assistance of quantum computing. Meanwhile, the use of quantum Monte Carlo also increases the expressivity of shallow quantum circuits, allowing more accurate computation that is conventionally achievable only with much deeper circuits. We numerically test and verify the method for the N2_22​ molecule (12 qubits) and the Hubbard model (16 qubits). Our work paves the way to solving practical problems with intermediate-scale and early-fault tolerant quantum computers, with potential applications in chemistry, condensed matter physics, materials, high energy physics, etc.
Quantum Monte Carlo and quantum simulation are both important tools for understanding quantum many-body systems.As a classical algorithm, quantum Monte Carlo suffers from the sign problem, preventing its application to most fermion systems and real-time dynamics.In this paper, we introduce a novel nonvariational algorithm using quantum simulation as a subroutine to accelerate quantum Monte Carlo by easing the sign problem.The quantum subroutine can be implemented with shallow circuits and, by incorporating error mitigation, can reduce the Monte Carlo variance by several orders of magnitude even when the circuit noise is significant.As such, the proposed quantum algorithm is applicable to near-term noisy quantum hardware.
Abstract A quantum implementation of the Stochastic Series Expansion (SSE) Monte Carlo method is proposed, and is shown to offer significant advantages over classical implementations of SSE. In particular, for problems where classical SSE encounters the sign problem, the cost of implementing a Monte Carlo iteration scales only linearly with system size in quantum SSE, while it may scale exponentially with system size in classical SSE. In cases where classical SSE can be efficiently implemented, quantum SSE still offers an advantage by allowing for more general observables to be measured.
The accurate and efficient simulation of many body systems has been a long-standing challenge for quantum chemists and physicists. At the heart of this challenge lies the correlation between quantum particles, which is crucial in understanding various physical phenomena, but is numerically hard to calculate. Over the decades, there has been remarkable progress in simplifying this problem aided by mathematical and chemical approximations and the availability of powerful computers. However, an exact solution to the problem still remains intractable as it requires exponential re- sources with respect to the system size. Recent advances in the field of quantum computing have shown promise in Feynman’s idea of simulating quantum mechanics on quantum computers. It has been proposed that an ideal fault-tolerant quantum computer can reduce the scaling of these sim- ulations from exponential to polynomial. However, initial quantum algorithms have shown that there is a large gap between the capabilities of current hardware and the resources required for simulating quantum systems of interest. The work of this thesis focuses on reducing this gap by introducing two novel algorithms for quantum xiv chemistry simulations, which are suitable for near-term hardware. First, we intro- duce a hybrid algorithm to decrease the total number of operations required for the quantum simulations. We use a classical computer to generate an effective Hamilto- nian containing O(n2) terms compared to the O(n4) terms of the full Hamiltonian, where n is the number of orbitals. This sparse Hamiltonian can then be used with a high-level method to recover the ground state energies. We demonstrate that this sparsification of the Hamiltonian reduces the number of quantum operations required for the simulation by an order of magnitude, thus making it accessible for the near- term Hardware. Our second algorithm aims to make the calculation of dynamic correlation functions (Green’s functions) more feasible on these quantum machines. This algorithm is designed with the motive of avoiding the use of time-evolution and reduced use of two-qubit gates. We demonstrate that we can reproduce the Green’s function within reasonable error limits using this approach. We have also discussed the use of re-sampling techniques for proper error-propagation of the stochastic data obtained from the quantum machines. The general structure of this thesis is as follows. We begin by motivating this work in Chapter 1. Chapters 2 and 3 provide a general introduction of quantum computing and Green’s function based methods, respectively. In chapter 4, the development of effective Hamiltonian is discussed in detail. Chapter 5 demonstrates the use of these effective Hamiltonians on the quantum machine for time evolution. In chapter 6, we have discussed the algorithm to calculate Green’s functions on a quantum machine. This is followed by conclusions and future directions in Chapters 7 and 8, respectively.
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.