Technical Summary: Constant Runtime Error Mitigation via Restricted Evolution

Problem Statement

Near-term quantum hardware is inherently noisy, limiting the reliability of measurement outcomes for physical observables. While Quantum Error Mitigation (QEM) techniques like Probabilistic Error Cancellation (PEC) and Zero-Noise Extrapolation (ZNE) have been proposed to improve result fidelity, they suffer from a critical scalability bottleneck: exponential sampling overhead relative to noise levels and circuit depth. Universal performance limits suggest that achieving resolvable statistics with these methods requires a super-polynomial or exponential number of samples, rendering them impractical for deep circuits or high-noise regimes. The community requires error mitigation strategies that offer a trade-off between computational overhead and statistical precision, specifically those that avoid exponential scaling to enable practical quantum utility in the near-term and early fault-tolerant eras.

Methodology: Restricted Evolution

The authors propose Error Mitigation by Restricted Evolution (EMRE), a protocol that approximates ideal quantum circuits with implementable noisy operations to achieve constant runtime sampling overhead.

Core Mechanism

1. Generalized Quasi-Probability Decomposition (GQPD):
   Instead of decomposing a unitary gate $U_i$ into a linear combination of implementable gates with both positive and negative coefficients (as in standard PEC), EMRE seeks a decomposition of the form:
   $$U_i = s_i B_i - (s_i - 1)N_i$$
   Where:

   • $B_i$ is an implementable (noisy) operation (or convex combination thereof).
   • $N_i$ is a quantum channel.
   • $s_i \geq 1$ is a scaling factor.
   • The term $(s_i - 1)$ represents the generalized robustness, a resource-theoretic measure quantifying the distance between the ideal operation and the set of implementable operations.

2. Restricted Evolution:
   The protocol approximates the ideal circuit $U$ by replacing each layer $U_i$ with the implementable operation $B_i$, scaled by the product of all $s_i$ factors ($s = \prod s_i$). The evolution is "restricted" to the implementable circuit $B$.
   $$U \approx sB$$
   This approximation introduces a bias in the expectation value estimate but eliminates the need to sample from negative probability distributions, which is the source of exponential overhead in PEC.

3. Bias Estimation and Correction:
   The estimated expectation value $E$ is derived from the noisy measurement of $B$, scaled by $s$. The bias $b$ is analytically bounded and depends on the generalized robustness. The authors provide a flowchart (Fig. 2) to determine the optimal estimate and bias bound based on the relationship between the scaling factor $s$, the estimation error $\epsilon$, and the measured value.

Hybrid EMRE (HEMRE)

To address scenarios where the bias from pure EMRE becomes too large (e.g., in high-noise regimes), the authors introduce Hybrid EMRE (HEMRE).

• Strategy: HEMRE allows the user to specify a maximum tolerable bias ($\Delta_{fixed}$).
• Implementation: The algorithm selectively applies the restricted evolution (approximating gates to their closest implementable versions) to a subset of gates, while retaining the full quasi-probabilistic decomposition (PEC-style) for others.
• Optimization: An algorithm (Algorithm 1) is provided to maximize the number of gates approximated while ensuring the product of their generalized robustnesses satisfies the user's bias constraint. This creates a continuous family of protocols bridging EMRE (constant overhead, non-zero bias) and PEC (zero bias, exponential overhead).

Key Contributions

1. Constant Sampling Overhead: The paper formally proves that EMRE can estimate expectation values with constant sampling complexity, independent of circuit depth, provided the bias is accepted. This contrasts sharply with the exponential scaling of PEC.
2. Analytical Bounds on Bias: The authors establish an analytical relationship between the bias and the generalized robustness. They derive exact expressions and bounds for the generalized robustness under specific noise models:
   • Depolarizing Noise: An exact result is derived for $d$-dimensional depolarizing noise, showing that mitigation can be achieved via simple post-processing (multiplication by a constant factor) without finding complex decompositions.
   • Dephasing Noise: Exact results are provided for single-qubit dephasing noise.
   • Probabilistic Noise: Upper bounds are established for single-qubit probabilistic error channels.
3. Hybrid Protocol (HEMRE): The introduction of HEMRE offers a tunable parameter (bias) to trade off between sample complexity and error reduction, allowing users to optimize for their specific hardware constraints (e.g., limited QPU hours).
4. Optimal Decomposition via Resource Theory: The methodology leverages the generalized robustness measure from dynamical resource theories to find the closest implementable circuit to the ideal one, providing a rigorous mathematical foundation for the approximation.

Numerical Results

The authors validated their proposals using numerical simulations on a SWAP-test circuit (7 qubits, 140 gates) designed to distinguish between a $|GHZ\rangle$ state and a $|0\rangle^{\otimes n}$ state.

• Comparison: They compared EMRE, HEMRE, and PEC against a baseline of no error mitigation.
• Low Noise Regime: For low noise probabilities (gate fidelities $\approx 99.7\%$), EMRE using the optimal generalized QPD outperformed PEC with the same number of samples, yielding a bias approximately 40% lower than PEC.
• High Noise Regime: As noise increased, the bias of pure EMRE grew. However, HEMRE maintained a lower bias than PEC while utilizing the same sampling budget.
• Scalability: Simulations on larger circuits (up to 51 qubits) and different noise models (inhomogeneous Pauli noise) confirmed the scalability of the approach.
• Efficiency: In cases where exact analytical results for generalized robustness were available (e.g., depolarizing noise), EMRE required only simple post-processing (multiplication by a factor), incurring zero extra computational time for decomposition.

Significance and Claims

The paper claims that EMRE and HEMRE provide a practical pathway for error mitigation in the Near-Term (NISQ) and Early Fault-Tolerant eras.

• Practicality: By removing the exponential sampling overhead, these protocols make it feasible to run quantum simulations on current and near-future hardware where PEC is computationally prohibitive.
• Flexibility: The ability to tune the bias via HEMRE allows researchers to balance computational cost (sampling overhead) against result accuracy, catering to specific application requirements.
• Resource Efficiency: The derivation of exact analytical bounds for common noise models implies that for certain hardware configurations, error mitigation can be performed with minimal classical post-processing, eliminating the need for expensive pre-computation of optimal decompositions.
• Future Outlook: The authors suggest that these protocols are particularly relevant as the field moves toward early fault-tolerant computing, where combining error correction with efficient error mitigation will be essential. They identify the integration with learning-based methods to find optimal decompositions and the synergy with error correction as promising avenues for future research.