Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems
Shunta Ide, Shu Tanaka
Abstract
Quantum annealing (QA) is a promising approach for solving combinatorial optimization problems; however, it is known to exhibit unfair sampling, in which degenerate ground states are not sampled with equal probability even for sufficiently long annealing times. Fair sampling is important in applications such as solution diversity assessment and combinatorial counting, yet the mechanism of unfair sampling remains poorly understood, particularly in constrained combinatorial optimization problems. In this work, we investigate unfair sampling of QA in weighted graph bipartitioning problems (GBP), a representative constrained optimization problem. We study how the penalty coefficient in the penalty method affects sampling fairness. Through numerical simulations and experiments on the D-Wave Advantage2 system, we show that increasing the penalty coefficient reduces unfair sampling in a representative single instance, and that this qualitative behavior is also observed on actual hardware. A scaling analysis over randomly generated instances with up to 12 spins reveals that, while this trend does not hold universally, more than 70% of instances exhibit monotonically increasing sampling fairness as the penalty coefficient increases, even at the largest system size studied. These results show that increasing the penalty coefficient improves sampling fairness, though at the cost of ground-state probability under practical annealing conditions, and call for a deeper theoretical understanding of unfair sampling in constrained optimization problems.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper investigates how the penalty coefficient in constrained combinatorial optimization problems affects the sampling fairness of quantum annealing (QA). Specifically, the authors study weighted graph bipartitioning problems (GBP) and demonstrate that increasing the penalty coefficient tends to reduce unfair sampling — the well-known phenomenon where degenerate ground states are not sampled with equal probability. The main finding is that in ~70-75% of randomly generated instances (up to N=12 spins), increasing the penalty coefficient monotonically improves sampling fairness, as measured by Shannon entropy of the normalized ground-state probability distribution.
The novelty lies in connecting the penalty method — a standard tool for handling constraints in QA — to the unfair sampling phenomenon, which had previously been studied primarily in unconstrained or geometrically frustrated systems. This is a conceptually interesting observation that the penalty coefficient serves a dual role: enforcing feasibility and influencing sampling fairness.
Methodological Rigor
The methodology combines numerical simulation (solving the time-dependent Schrödinger equation via QuTiP) with experiments on D-Wave Advantage2 hardware. However, several limitations undermine the rigor:
1. System size: The scaling analysis is limited to N ≤ 12 spins, which is extremely small. At these sizes, the behavior could be dominated by finite-size effects, and it is impossible to draw reliable conclusions about scalability. The saturation of the monotonic increase rate around 70-75% is observed over only a few data points (N=8, 10, 12), making the claim of saturation speculative.
2. Instance generation: Only 100 instances per system size were studied, all restricted to exactly 2-fold degeneracy (4-fold with spin-flip symmetry). This is a narrow slice of the problem landscape. The authors acknowledge that larger degeneracies are left for future work, but this significantly limits the generality of the conclusions.
3. D-Wave experiments: The hardware results are presented for a single instance (plus 10 baseline instances), making it difficult to assess reproducibility or statistical significance of the hardware trends. The entropy variation on D-Wave (Fig. 3b) is extremely small (~0.005 range), raising questions about whether the observed trends are meaningful given hardware noise.
4. Parameterization choice: The reparameterization in Eq. (8) using λ ∈ [0,1] is non-standard and changes the overall energy scale, which could conflate effects of the penalty coefficient with effects of energy rescaling on the annealing dynamics. The authors acknowledge this but do not adequately disentangle these effects.
5. No theoretical explanation: The paper is primarily empirical and offers no mechanistic explanation for why increasing the penalty coefficient improves fairness. The suggestion that degenerate perturbation theory might explain the phenomenon is mentioned only as future work.
Potential Impact
The practical impact is limited for several reasons:
The conceptual insight that penalty coefficients influence sampling fairness is potentially useful for the quantum optimization community, particularly those working on applications requiring solution diversity (e.g., SAT filtering, counting problems). However, without theoretical understanding or practical guidelines, the actionable value is modest.
Timeliness & Relevance
The paper addresses a real concern in the quantum annealing community. Unfair sampling has been recognized as a significant limitation for applications beyond pure optimization, including combinatorial counting and diversity-aware optimization. The connection to constrained optimization through the penalty method is timely, as most practical problems involve constraints. However, the field is increasingly moving toward larger-scale studies and fault-tolerant quantum computing, making small-scale empirical observations on current hardware less impactful.
Strengths
1. Clear problem formulation: The paper clearly defines sampling fairness using Shannon entropy and systematically varies the penalty coefficient.
2. Hardware validation: Including D-Wave experiments, despite limitations, provides some empirical grounding.
3. Honest reporting: The authors transparently report that the trend does not hold universally and acknowledge the trade-off with ground-state probability.
4. Well-defined experimental protocol: The use of parallel annealing, spin reversal transformation, and auto-scaling normalization demonstrates careful experimental design.
Limitations
1. Very small system sizes (N ≤ 12) severely limit the significance of scaling claims.
2. No theoretical framework to explain the observed phenomena.
3. Limited degeneracy (only 4-fold) restricts generality.
4. Narrow problem class: Only GBP is studied; extension to other constrained problems is entirely speculative.
5. The D-Wave results show marginal effects (entropy variations of ~0.005) that may not be distinguishable from noise or embedding artifacts.
6. Missing comparison to other approaches for improving sampling fairness (e.g., higher-order drivers, modified annealing schedules).
7. Conference paper format with limited depth — reads more as a preliminary observation than a complete study.
Overall Assessment
This paper presents an interesting preliminary observation connecting penalty coefficients to sampling fairness in quantum annealing for constrained problems. The core idea is sound and the question is relevant, but the study remains at a very early stage. The extremely small system sizes, lack of theoretical explanation, narrow problem scope, and marginal hardware effects significantly limit the impact. The paper would benefit substantially from larger-scale analysis (perhaps using tensor network methods), theoretical grounding via perturbation theory, and extension to other problem types. As it stands, it represents an incremental contribution that identifies a phenomenon but does not adequately characterize or explain it.
Generated Apr 19, 2026
Comparison History (34)
Paper 2 likely has higher impact due to timeliness and real-world relevance: unfair sampling is a practical limitation for current quantum annealers, and the work combines theory, simulations, and on-hardware experiments (D-Wave Advantage2), making results immediately actionable for QA users. It addresses a broadly important issue (solution diversity/counting) across optimization, quantum computing, and applications. Paper 1 is technically novel for quantum thermodynamics/batteries and offers analytic insight, but the application space is less mature and more specialized, with impact contingent on future quantum battery implementations.
Paper 2 addresses a more broadly impactful problem (TSP) with a practical preprocessing method applicable to both classical and quantum optimization, offering immediate scalability improvements. Its contributions are more actionable and relevant across operations research and quantum computing communities. Paper 1, while scientifically interesting in characterizing unfair sampling in quantum annealing, addresses a narrower phenomenon (sampling fairness) with limited system sizes (up to 12 spins) and acknowledges the trend doesn't hold universally, limiting its broader applicability and impact.
Paper 2 is more novel and broadly impactful: it proposes a general architectural concept (quantum actuators) for globally controlled quantum computation, potentially affecting multiple platforms and intersecting quantum architecture, compilation, and even quantum thermodynamics (via the battery interpretation). Its potential real-world applications—reducing local-control overhead while enabling long-range entangling gates—map directly onto a central bottleneck in scalable quantum computing. Paper 1 is timely and methodologically grounded (hardware + simulations) but is narrower (QA sampling in a specific constrained problem) and limited in scale (≤12 spins), likely constraining broader impact.
Paper 2 has higher estimated impact due to stronger real-world applicability and timeliness: it directly addresses a known limitation of quantum annealers (unfair sampling) with implications for optimization, counting, and solution diversity. It combines simulations with experiments on state-of-the-art D-Wave hardware, improving methodological credibility and relevance to industry and quantum computing practitioners. While Paper 1 is novel and rigorous for nonequilibrium dissipative quantum many-body dynamics, its impact is more specialized within condensed matter/theory. Paper 2’s findings can influence QA benchmarking, encoding practices, and near-term hardware use across domains.
Paper 2 likely has higher impact due to stronger real-world relevance and timeliness: it addresses unfair sampling in quantum annealing on a commercial platform (D-Wave Advantage2), a key obstacle for practical QA use in optimization, counting, and diversity tasks. It combines simulation with hardware experiments and explores a controllable mitigation knob (penalty coefficient), making the findings actionable. While Paper 1 is novel and useful for generative quantum ML encoding, its scope is narrower (mainly 1D distributions and QCBMs) and more methodological, with less immediate cross-domain applicability than QA fairness issues.
Paper 2 has higher impact potential due to its direct relevance to near-term quantum computing hardware and applications in combinatorial optimization. It combines simulations with experiments on a state-of-the-art D-Wave system, addressing a practical limitation (unfair sampling) that affects solution diversity and counting. The work offers actionable guidance (penalty-coefficient tradeoffs) and is timely for constrained QA use cases, with potential influence across quantum algorithms, benchmarking, and hardware-operation practices. Paper 1 is more theoretical/resource-theory focused with narrower immediate applicability.
Paper 2 addresses a well-defined, practically important problem (unfair sampling in quantum annealing) with rigorous methodology combining numerical simulations and real hardware experiments on D-Wave Advantage2. It provides actionable insights about penalty coefficients and sampling fairness with systematic scaling analysis. Paper 1 is more speculative, proposing to merge various quantum/classical tools for formic acid analysis but presents preliminary work on a simple non-catalytic process. Paper 2's findings are more immediately applicable to the quantum computing optimization community and offer clearer, reproducible contributions.
Paper 2 has higher potential impact: it advances a central, long-standing theoretical problem by giving new conditions and explicit non-degradable/non-PPT families where one-way distillable entanglement is single-letter, with links to channel capacity additivity. The contributions are broadly relevant across quantum information theory (entanglement theory, entropy inequalities, quantum Shannon theory) and likely to be reusable. Paper 1 is timely and practical for QA benchmarking, but its scope is narrower, results are partly instance-dependent and limited to small sizes, and impact is more incremental/empirical.
Paper 2 proposes a novel quantum simulation scheme for Motzkin spin chains using Rydberg atoms, bridging mathematical physics (topological phases, AdS/CFT) with experimental quantum simulation. It addresses a fundamentally hard problem (non-area-law entangled states) and opens new experimental avenues in programmable quantum simulators. Paper 1 provides useful but incremental insights into unfair sampling in quantum annealing for a specific problem class, with limited system sizes (12 spins) and results that don't universally hold. Paper 2 has broader cross-disciplinary impact spanning condensed matter, quantum information, and high-energy physics.
Paper 1 introduces a significant methodological generalization of the TEMPO method for open quantum systems, extending it to handle non-commuting coupling operators with general Gaussian bosonic baths. This addresses a fundamental limitation in quantum dynamics simulations with broad applicability across quantum optics, condensed matter, and quantum information. Paper 2 studies unfair sampling in quantum annealing for a specific problem class with modest system sizes (up to 12 spins), providing empirical observations without deep theoretical explanation. Paper 1's methodological contribution has greater breadth of impact and enables new classes of simulations previously inaccessible.
Paper 1 introduces a novel quantum-inspired algorithm (ADAPT-VMPE) with theoretical guarantees, polynomial complexity, and demonstrates scalability up to 100 qubits on a clinically relevant molecular system. It addresses a fundamental challenge in quantum chemistry—ground state approximation—with direct real-world applications (cancer treatment photosensitizer). Paper 2 provides useful empirical insights into unfair sampling in quantum annealing but is limited to small system sizes (12 spins), lacks strong theoretical explanations, and addresses a narrower problem. Paper 1's methodological innovation, scalability, and practical relevance give it significantly broader impact potential.
Paper 1 establishes rigorous information-theoretic scaling laws connecting quantum state complexity to neural network capacity, providing fundamental theoretical results (proven bounds, analytical rank formulas) with broad implications across quantum computing, machine learning, and many-body physics. It addresses a foundational question about representability of quantum states by neural networks. Paper 2 makes a useful empirical contribution studying unfair sampling in quantum annealing for a specific problem class, but its scope is narrower, results are largely empirical with limited system sizes (up to 12 spins), and findings are not universal across instances, limiting broader impact.
Paper 2 offers broader, more foundational impact: it provides exact characterisation of initial-state memory in finite random brickwork circuits, identifies a sharp threshold (environment smaller/larger than half), demonstrates emergent universality, and predicts a dissipation-driven phase transition. These results are timely for quantum information, thermalization/scrambling, noisy intermediate-scale devices, and open-system dynamics, and are less platform-specific than Paper 1. Paper 1 is valuable experimentally (D-Wave) but its scope is narrower (one problem class, small-size scaling, heuristic penalty tuning with tradeoffs), limiting cross-field impact.
Paper 2 addresses a fundamental and poorly understood phenomenon (unfair sampling) in quantum annealing with both theoretical and experimental validation on real D-Wave hardware. It provides novel insights into how penalty coefficients affect sampling fairness in constrained optimization, opening new research directions. Paper 1, while practically useful, is primarily an engineering contribution—a transpilation pipeline between two existing frameworks—with limited novelty beyond software integration. Paper 2 has broader scientific implications for quantum computing theory, combinatorial optimization, and the understanding of quantum annealing dynamics.
Paper 2 introduces novel theoretical concepts at the intersection of quantum information and nonlocality, demonstrating a stronger form of 'nonlocality without entanglement' and establishing new separations between marking and discrimination tasks for unitary operations. These foundational results have broader implications across quantum information theory, quantum communication, and resource theory. Paper 1, while addressing a practical issue in quantum annealing, is more incremental—studying penalty coefficients' effects on sampling fairness in a specific problem class with limited system sizes (up to 12 spins), offering empirical observations without deep theoretical resolution.
Paper 2 addresses a practical and widely relevant problem in quantum computing—unfair sampling in quantum annealing—with both theoretical analysis and experimental validation on real D-Wave hardware. It has broader impact across quantum computing, optimization, and combinatorial counting communities. Paper 1, while theoretically interesting in strong-field QED, presents a more niche contribution about structured Volkov wavepackets with arbitrary velocity, whose experimental verification and practical applications are less immediately apparent. Paper 2's timeliness in the rapidly growing quantum computing field and its actionable insights for practitioners give it higher potential impact.
Paper 2 has higher potential impact due to greater novelty and breadth: it proposes a new quantum algorithmic route to simulating full Navier–Stokes (including dissipation, pressure, vorticity) via a Hamilton–Jacobi reformulation and tensor-network Carleman embedding, with demonstrated emulation and error/convergence analysis. If scalable, applications span computational fluid dynamics, engineering, climate, and turbulence—high-impact domains and timely for quantum algorithms. Paper 1 is solid and experimentally grounded but more incremental and narrow (sampling fairness tuning in QA for a specific constrained problem, small-size scaling), limiting cross-field reach.
Paper 2 has higher potential impact due to its clearer novelty and relevance to a well-known limitation of quantum annealing—unfair sampling—in a constrained, practically important optimization setting. It combines simulations with experiments on state-of-the-art D-Wave Advantage2 hardware, improving methodological rigor and real-world applicability. The findings (penalty coefficient trade-offs) are actionable for practitioners and connect to broader themes in optimization, sampling, and probabilistic computing. Paper 1 is useful but is largely an empirical robustness study on a small classical benchmark (Titanic) via simulation, with more limited generalizability and cross-field influence.
Paper 2 likely has higher scientific impact because it addresses a timely, high-leverage bottleneck—scalable wafer-scale manufacturing workflows for superconducting quantum chips—linking quantum device design to foundry-executable manufacturing data. Its contributions (end-to-end Q-EDA architecture, quantum-specific DRC rules, process stack model, and benchmarking of existing tools) are broadly applicable across academia and industry and can accelerate large-scale hardware development. Paper 1 advances understanding of unfair sampling in quantum annealing, but its scope (small-size scaling up to 12 spins, instance-dependent trends) suggests more limited near-term generality and cross-field uptake.
Paper 1 likely has higher impact: it addresses a broadly relevant stability bottleneck in quantum Krylov subspace methods, a key early fault-tolerant algorithm family, and offers general, spectrum-agnostic reliability diagnostics (imaginary/unitary filters) applicable across many Hamiltonian problems. The work reframes a common concern (ill-conditioning) by identifying sampling noise as the dominant limiter in realistic regimes, which is timely and actionable for near-term experiments and error-mitigation/regularization research. Paper 2 is valuable and includes hardware evidence, but is more application- and platform-specific with limited scaling, reducing breadth and generality.