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

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.

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.