Efficient re-sampling in quasi-probability decompositions

AI summary

Overview

Research area: Quantum computing — circuit knitting via quasi-probability decompositions (QPDs), fidelity estimation, and variational quantum algorithms (quantum natural gradient, variational time evolution, quantum kernels).

Technical level: Advanced. The paper works in the superoperator representation, assumes familiarity with Hadamard-test style overlap estimation, importance sampling, and the quantum geometric tensor.

Scope (one sentence): The paper introduces a sample-reweighting scheme that lets a single QPD sampling of a parameterized circuit be reused across nearby parameter settings, and applies it to fidelity estimation and to estimating the real part of the quantum geometric tensor via SPSA.

What This Paper Is About

Quasi-probability decompositions replace hard-to-execute (for example, non-local) operations with signed mixtures of easy-to-execute local operations, but the sampling overhead quantified by the factor γ generally grows exponentially with the number of decomposed gates. The authors ask whether, for a family of circuits that share the same variational structure and differ only in gate angles, samples drawn for one reference parameter setting can be recycled to estimate quantities at other parameter settings instead of building a fresh decomposition each time. They answer yes, via self-normalized importance sampling, and use this to estimate state fidelities and, through SPSA, the real part of the quantum geometric tensor.

Key Contributions

1. An angle-independent QPD of the controlled-R_Z gate. The authors decompose CR_Z(θ) into a sum of local channels whose form does not depend on θ (Eq. 8), with γ_{CR_Z}(θ) = 1 + |sin(θ/2)|(2 + |sin(θ/2)| + |cos(θ/2)|). They note this factor is larger than the known optimal γ_opt = 1 + 2|sin(θ/2)| for parameterized two-qubit gates, but the optimal construction leaves an explicit angle dependence in the local channels, u_i = u_i(θ), which would break the reweighting conditions.

2. A reweighting framework for QPDs across parameter settings. Given a reference QPD with coefficients a_i(θ) and a target with a_i(θ′), they reuse reference samples with weights w_i(θ′, θ) = |a_i(θ′)/a_i(θ)|, showing the estimator is unbiased whenever the target support satisfies ξ′ ⊆ ξ (Eq. 20–21), and deriving the variance (Eq. 22). A variance-inflation indicator χ(θ, θ′) = Σ_i |a_i(θ′)|²/(γ|a_i(θ)|) is introduced, with χ = 1 meaning the reweighted estimator matches the reference variance, χ > 1 an increase, and χ < 1 a reduction.

3. A self-normalized importance-sampling estimator for finite samples. Because the weights are random variables, the normalization Σ_i p̂_i w_i = 1 holds only in expectation; the authors normalize by the sum of reweighted empirical probabilities (Eq. 24), giving comparatively smaller variance while remaining asymptotically unbiased.

4. QGT estimation from a single reference sampling. Combining the compressed Hadamard test, the CR_Z QPD, and reweighting with SPSA, they estimate all 4K fidelity terms entering the QGT estimator from one reference QPD, chosen as the fidelity between |φ(θ)⟩ and |φ(θ + 2h·1)⟩, because displacements generated by Δ_1, Δ_2 lie in {−2, 0, 2}. This caps circuit executions at M, versus 4KN for compute–uncompute and 8KN for the uncut Hadamard test.

Main Findings

• RMSE scaling confirmed: For fidelity estimation on a 3-qubit layered ansatz with L = 2 layers, the RMSE of the fidelity estimator scales as O(γ/√M), consistent with the error analysis in the appendix (results averaged over 10 runs; fixed M = 5 × 10⁴ when varying h, and fixed h = 0.1 when varying M).
• γ alone is not a sufficient reweighting criterion: For the CR_Z QPD, the authors identify parameter points where the target γ < γ_r (reference γ) yet χ > 1, so the variance stays large. They report that parameter values within an ℓ∞-neighborhood of a given reference point can be reliably reweighted, and in the plotted example the perturbation domain [−θ_r, θ_r]² satisfies χ ≤ 1.
• Constant circuit-execution budget for cut-HT: The compressed Hadamard test with a single reference QPD requires at most M circuit executions, whereas compute–uncompute requires 4KN and the uncut Hadamard test 8KN for N shots and K SPSA iterations; the authors emphasize that for CU and HT the execution count grows linearly with K while for cut-HT it stays constant.
• Noiseless comparison favors compute–uncompute: On Qiskit's Aer Qasm simulator (shot-based, no device noise), for the chosen simulation parameters the CU method achieves the highest accuracy, while the cut Hadamard test performs comparably, particularly when K is small. The truncated text does not report the remaining noiseless comparison numbers.
• Noise robustness (abstract-level claim): The abstract states that with realistic hardware noise the method outperforms other standard estimation techniques; simulations use Qiskit 1.2 fake Manila and Toronto backends with M = 5 × 10⁵ QPD samples and h = 0.1. The body text with the detailed noisy-backend error values is not included in the provided content, so those specific numbers are not reported here.
• No ancilla, no extra depth: Unlike the Hadamard test, which needs an ancilla and controlled state-preparation unitaries, and compute–uncompute, which uses a deep U†V circuit, the QPD approach separates the ancilla from the state-preparation circuit and preserves the ansatz structure in width and depth counted in multi-qubit gates. The compressed Hadamard test also reduces controlled gates from 2d to d and halves the number of two-qubit gates relative to the standard Hadamard test.
• Error metric definition: Accuracy is measured by the relative Frobenius-norm error ε(ĝ, g) = ‖ĝ − g‖_F / ‖g‖_F, with all data points averaged over 10 runs.

Methodology in Plain English

The authors start from the observation that a hard gate can be written as a signed weighted sum of easy gates, and that estimating an expectation value then means running randomly chosen easy circuits and applying sign corrections, with cost inflated by γ. For the two-qubit controlled rotation, they deliberately choose a decomposition whose building blocks are fixed, angle-independent unitaries and mid-circuit projections, so that only the real-valued coefficients in front of the blocks change when the rotation angle changes.

Because the underlying circuit set is identical for different angles, a batch of sampled circuits from one reference angle can be re-weighted by the ratio of the old and new coefficients and reused. The authors work out when this is sound (the target must not use blocks that were not sampled), what the variance penalty is (summarized by χ), and how to stabilize the estimator for small sample counts with self-normalization. They then build a fidelity estimator that avoids ancilla-controlled state preparation by cutting the ancilla off the compressed Hadamard test and recombining results classically.

Finally, they plug this fidelity primitive into SPSA, which estimates the full geometric tensor from random ±1 perturbation directions rather than O(d²) separate finite differences. Since each SPSA iteration needs four fidelities at nearby parameters, they pick one reference fidelity far enough out in the ℓ∞ sense to cover all the perturbed states, sample it once, and recover every required fidelity by reweighting. Comparisons against compute–uncompute and the standard Hadamard test are made at equal total circuit-execution budgets, both without device noise and on fake hardware backends.

Why This Matters

Impact on research: The work reframes QPD sampling overhead as something that can be amortized over a family of parameter settings rather than paid per evaluation, and it supplies a concrete diagnostic (χ) for where amortization is safe. It also gives a fidelity-estimation route that avoids both ancillas and doubled-depth compute–uncompute circuits, which matters for variational algorithms where fidelity is a recurring subroutine.

Real-world applications (bullets):

• Variational quantum simulation of quantum systems, where fidelities between nearby time-evolved states are needed repeatedly.
• Quantum natural gradient and variational dynamics, which require the real part of the quantum geometric tensor.
• Quantum kernel methods, which rely on overlap estimation between parameterized states.
• Circuit knitting on fixed-connectivity hardware, where long-range interactions would otherwise require SWAP-induced depth and error.

Industry relevance: The authors are affiliated with EPFL and IBM Research Rüschlikon, and the numerics use Qiskit 1.2 with the fake Manila and Toronto backends, indicating direct relevance to superconducting-device workflows where connectivity constraints and noise limit executable circuit depth. Reducing measurement and execution counts per optimization step is a practical cost driver for variational workloads on near-term hardware.

Future Directions

• Extending reweighting beyond the CR_Z case: the angle-independent decomposition used here has a larger γ than the known optimal γ_opt = 1 + 2|sin(θ/2)|; finding decompositions that are both angle-independent and closer to optimal is an open design question.
• Characterizing safe reweighting regions more generally: the ℓ∞-neighborhood result and the χ ≤ 1 perturbation domain are established for this specific QPD; generalizing the χ-based criterion to other gates, deeper cut sets, and larger parameter displacements is a natural next step.
• Handling partial support overlap: when ξ′ ⊄ ξ the estimator is biased by the missing terms Σ_{i∈ξ′∖ξ} a_i′ u_i; strategies for correcting or bounding this bias remain to be developed.
• Larger-scale and hardware validation: the reported simulations use a 3-qubit, L = 2 ansatz; scaling behavior with qubit number, layer count, and number of cut gates on real devices is not established in the presented content.

Target Audience

Researchers and practitioners in quantum algorithm design and quantum error mitigation who already know circuit knitting, Hadamard-test overlap estimation, and variational algorithms, and who want to reduce sampling and execution overhead when evaluating fidelities or geometric tensors across many parameter settings. It is also relevant to quantum-software engineers implementing QPD-based workflows in Qiskit-style stacks, and less suited to readers without a quantum information background.

Authors’ abstract

Near-term quantum devices are limited by noise and hardware constraints, motivating algorithmic approaches that trade circuit complexity for increased sampling overhead. Quasi-probability decompositions (QPDs), for example, allow replacing non-local operations by multiple circuits with local operations, but the associated sampling overhead generally scales exponentially and limits their practicality. In this work, we introduce a reweighting strategy for QPDs for circuits with the same variational structure across parameter settings, reusing samples and thereby reducing the sampling overhead. We first demonstrate this approach by estimating fidelities between parameterized quantum states, a key primitive in variational time evolution and quantum kernel methods. Importantly, this setup allows controlling the exponential QPD sampling overhead while preserving the structure of the state-encoding ansatz. We then apply the method to estimate the real part of the quantum geometric tensor using the simultaneous perturbation stochastic approximation and find that, in the presence of realistic hardware noise, our method outperforms other standard estimation techniques. These results highlight the potential of reweighting strategies to extend the applicability of QPD-based methods in variational quantum algorithms.