Source-linked AI summary
Reliable Sample-Level Quantum Error Mitigation via Dominance-Aware Clustering
Mohsen Ghodrati, Kausthubh Chandramouli, Dror Baron
TL;DR
Quantum error mitigation commonly targets expectation values, although optimization algorithms often need high-quality bitstrings from finite samples. This paper studies center recovery in noisy multi-source distributions, develops dominance-aware refinement for majority-vote recovery, and evaluates it on synthetic and MaxCut-QAOA data. DA refinement favors precision, while DA-enhanced k-modes improves overall center recovery without additional circuit executions.
Problem
Sample-level QEM must recover task-relevant bitstrings from finite measured distributions, whereas most QEM methods target expectation values.
Method
The paper uses dominance conditions, responsibility thresholding, and a local dominance screen to refine clustering and support majority-vote center recovery.
Results
At n = 100, Adaptive or Lightning DA give the highest recall for both tested center geometries.
Takeaways & Limitations
DA refinement favors precision and requires no additional quantum-circuit executions.
Abstract
from arXiv · showhide
Many quantum algorithms for classically difficult optimization tasks must return high-quality bitstrings from finitely many circuit executions, whereas most quantum error-mitigation methods target expectation values. We study sample-level recovery when measured probability mass is distributed around multiple latent bitstrings, called centers. Each component of the measured probability mass is called a source and we assume that each center is associated with one source. We identify dominance-at every coordinate, more than half of a retained region's probability mass comes from one source and agrees with its center-as a sufficient condition under which majority voting recovers that center with exponentially decreasing error probability. We show that nearest-center assignment, as used in clustering algorithms such as the $k$-modes algorithm, can fail to produce dominated regions even when the true centers are known. This failure motivates responsibility thresholding and a local dominance screen, whose combination we call dominance-aware (DA) refinement. Synthetic and simulated MaxCut-QAOA experiments show that DA refinement favors precision, while $k$-modes with DA refinement improves overall center recovery. All procedures are classical post-processing and require no additional quantum-circuit executions.
I. INTRODUCTION
Sample-level QEM targets task-relevant bitstrings rather than expectation values, but finite-shot noise makes unobserved-center recovery difficult. The paper introduces dominance-aware refinement after showing that nearest-center assignment can undermine majority-vote recovery.
- Sample-level QEM seeks task-relevant bitstrings from finite measured distributions, whereas most QEM methods improve expectation values.In QAOA, the measured bitstrings themselves are the objects of interest.
- Directly observing a center requires exponentially many shots in bitstring length, while qubit-wise majority voting requires logarithmically many shots for fixed confidence.This contrast motivates majority-vote-based recovery under finite-shot budgets.
- Q-Cluster’s nearest-center Hamming assignment can produce nondominated clusters even when candidate centers are correct.Its geometric assignment ignores unequal mixture weights.
- EM-QEM accounts for unequal mixture weights but can produce initialization-dependent local solutions through its nonconvex likelihood optimization.Both methods can recover unobserved centers, but their analyses lack a finite-sample condition for exact recovery from mixed-source clusters.
- The paper identifies dominance as a sufficient condition for majority-vote recovery and combines responsibility thresholding with a local dominance screen in DA refinement.DA refinement is instantiated in k-modes, alongside Adaptive DA k-modes as an end-to-end method.
II. MODEL AND MLE FORMULATION
The paper models measured quantum outputs as a global-plus-local mixture whose local sources generate noisy versions of task-relevant centers. Sample-level QEM is then formulated as joint maximum-likelihood estimation of centers, source weights, and source-specific bit-flip rates.
- Measured outputs are modeled as a probabilistic mixture over K distinct task-relevant bitstrings called centers.The model includes a uniform background component and local components centered on the task-relevant bitstrings.
- Each local source generates a noisy version of its associated center, with independent coordinate bit flips at rates below 1/2.The uniform term represents effective global depolarizing background probability.
- The measured data consist of S independent shots, each assigned a latent source label whose probability equals that source’s mixture weight.Source 0 is uniform background, while sources k ≥ 1 are centered on their associated centers.
- For fixed K, joint maximum likelihood estimates centers, source weights, and source-specific bit-flip rates.The feasible parameter set constrains the optimization variables.
- A restricted two-center discrete search reduces to NP-hard hypercube 2-segmentation, motivating a dominance-aware approximate method.The hardness statement does not apply to every individual parameter update.
III. DOMINANCE AND FINITE-SHOT RECOVERY
Dominance provides a sufficient condition for coordinatewise majority voting to recover latent centers with finite samples, while nearest-center assignment can violate that condition. Responsibility thresholding and local screening address this failure.
- A region is dominated by source k when source k contributes more than half of the retained mass agreeing with center c_k at every coordinate.
- QMV recovers a dominated center with failure probability bounded by an exponentially decreasing function of assigned shots and the dominance margin.The bound follows from Hoeffding’s inequality and a union bound; the condition is sufficient rather than necessary because other sources may also agree with c_k.
- Nearest-center assignment can produce a non-dominated cluster even when the candidate centers are exactly correct.With centers (000, 001, 111), weights (0.95, 0.04, 0.01), and bit-flip rate 0.1, region {110, 111} is assigned to 111 although most shots are 110.
- Under equal source weights, no background, bounded bit-flip rates, and sufficient center separation, nearest-center regions become dominated and QMV recovery applies.For fixed β, d_min > (2β^2)^-1 log(K/β) is sufficient, so Q-Cluster can succeed when centers are sufficiently separated.
IV. DOMINANCE-AWARE REFINEMENT
DA refinement uses fitted source responsibilities to retain likely source-consistent shots, recompute candidate centers by QMV, and screen them with a local dominance score. Applied within k-modes variants, it favors precision but requires candidate coverage for recall.
- Responsibility thresholding forms source-specific regions from fitted source probabilities, while a local agreement score screens whether those regions support reliable QMV recovery.At the population level, a positive score together with thresholding implies the QMV bound; empirically, the score is used as a screen.
- DA refinement updates candidate centers by QMV, accepts only centers with positive fitted empirical dominance scores, and can increase responsibility thresholds when screening fails.The workflow also merges repeated centers and refits mixture parameters after recomputing responsibility regions.
- DA refinement is instantiated in k-modes because k-modes shares the iterative assign-and-update structure of Q-Cluster and EM-QEM.
- DA refinement favors precision but cannot recover a center whose recovery basin contains no initialized candidate.Adaptive DA k-modes addresses this recall limitation by pruning overcomplete fits and proposing diverse candidates from concentrated, poorly explained probability mass.
- Lightning DA k-modes preserves candidate proposal and DA-refinement structure while reducing parameter updates per fit, and all processing remains classical.
V. SYNTHETIC AND QAOA EVALUATION
Across synthetic and QAOA evaluations, Adaptive DA generally achieves the strongest recovery, while high-dimensional results depend on center geometry and candidate-proposal strategy.
- At n = 10, Adaptive DA has the highest marginal F C
- 1 and remains within 0.02 of EM-QEM on the factorial design; Lightning DA also reaches F C
- With six QAOA candidate checks, Adaptive DA has the highest average recall, 0.65.
- High-dimensional benchmark: For clustered centers, Lightning and Adaptive DA reach recall 0.80 and 0.79, compared with 0.18 for EM-QEM and 0.01 for Q-Cluster.
- High-dimensional benchmark: For uniform centers, Adaptive DA reaches recall 0.89, compared with 0.85 for EM-QEM, 0.32 for Lightning DA, and 0.00 for Q-Cluster.
- High-dimensional benchmark: Lightning DA is effective when local clustered structure supplies candidates in one round, whereas repeated Adaptive DA proposals are important for dispersed centers.
VI. SCOPE AND CONCLUSION
Reliable center recovery requires retained clusters to support majority voting, not merely to group nearby shots. DA refinement addresses this through responsibility thresholding and local dominance screening without additional circuit executions.
- DA refinement combines responsibility-thresholded regions with a local dominance screen to reject unsupported QMV updates.
- DA refinement requires no additional quantum-circuit executions and provides logarithmic verification complexity for QMV-based recovery.
- At n = 100, Adaptive or Lightning DA give the highest recall for both tested center geometries.