pith. sign in

arxiv: 2604.11449 · v1 · submitted 2026-04-13 · 🪐 quant-ph

Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems

Shunta Ide , Shu Tanaka This is my paper

Pith reviewed 2026-05-10 16:28 UTC · model grok-4.3

classification 🪐 quant-ph
keywords samplingunfairpenaltyproblemsannealingcoefficientoptimizationcombinatorial
0
0 comments X

The pith

Increasing the penalty coefficient reduces unfair sampling in quantum annealing for most graph bipartitioning instances

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper investigates how the penalty coefficient affects unfair sampling in quantum annealing applied to weighted graph bipartitioning problems. It finds that raising this coefficient makes sampling of degenerate ground states fairer in a single instance, confirmed on hardware. Across many random instances up to 12 spins, more than 70 percent show this monotonic improvement in fairness with larger penalties. This comes at the cost of reduced ground-state probability, highlighting the need for better understanding of sampling bias in constrained problems.

Core claim

Quantum annealing shows unfair sampling where degenerate ground states are not equally likely even for long annealing times. In weighted graph bipartitioning, the penalty coefficient in the penalty method controls the strength of the constraint term in the Hamiltonian. Increasing this coefficient leads to improved sampling fairness in over 70% of instances studied, as measured by how equally the solutions are sampled, although the probability of reaching the ground state decreases under practical conditions.

What carries the argument

The penalty coefficient that scales the constraint term in the Ising Hamiltonian formulation of the weighted graph bipartitioning problem

Load-bearing premise

The annealing schedules and random instance generation method used are representative for generalizing the 70% trend beyond 12 spins

What would settle it

A study on instances with significantly more spins or alternative annealing schedules showing that a majority do not exhibit increasing fairness with penalty would falsify the generalizability of the trend

Figures

Figures reproduced from arXiv: 2604.11449 by Shunta Ide, Shu Tanaka.

Figure 1
Figure 1. Figure 1: Panel (a) shows the annealing-time dependence of the [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The unfair sampling of the GBP instance shown in [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The unfair sampling of the GBP instances on the D [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The entropy of the ground-state probability distribution [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper studies unfair sampling in quantum annealing for weighted graph bipartitioning (GBP) problems. Using numerical simulations and D-Wave Advantage2 experiments, it shows that increasing the penalty coefficient reduces unfair sampling for a representative instance. A scaling analysis on randomly generated instances up to N=12 finds that more than 70% exhibit monotonically increasing sampling fairness with penalty strength (though not universally), at the cost of lower ground-state probability under practical annealing times.

Significance. If the empirical trend holds, the work provides actionable guidance for penalty tuning to improve fairness in constrained QA problems, relevant for applications needing solution diversity or counting. Strengths include direct measurement of fairness from sampled bitstrings, combined classical/hardware validation, and focus on a representative constrained problem; these are genuine contributions even at small sizes.

major comments (3)
  1. [Abstract and scaling analysis] Abstract and scaling analysis: the central claim that 'more than 70% of instances exhibit monotonically increasing sampling fairness' is reported without the total number of instances, any statistical uncertainty (standard error, bootstrap, or hypothesis test), or breakdown of the fraction versus N. This directly undermines assessment of the 70% figure's robustness given the N≤12 regime.
  2. [Scaling analysis] Scaling analysis: no data or plot shows how the fraction of instances obeying the monotonic trend evolves with N, nor is there a finite-size scaling collapse or extrapolation. The observed percentage is therefore confined to the studied regime and cannot yet support claims of generic behavior.
  3. [Numerical simulations and D-Wave runs] Numerical simulations and D-Wave runs: the fairness metric and ground-state probabilities lack reported error bars or statistical tests, and the instance-generation procedure plus annealing schedules are described at insufficient detail to judge representativeness or enable reproduction.
minor comments (2)
  1. Clarify the precise definition of the 'sampling fairness' metric (e.g., how degeneracy is identified and probabilities normalized) in the main text or a dedicated methods subsection.
  2. Figure captions should explicitly state the number of samples, annealing time, and penalty values used for each panel to improve readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We have carefully considered each major comment and will revise the manuscript to address the concerns raised, particularly by providing additional details, statistical measures, and clarifications on the scaling analysis.

read point-by-point responses

  1. Referee: [Abstract and scaling analysis] Abstract and scaling analysis: the central claim that 'more than 70% of instances exhibit monotonically increasing sampling fairness' is reported without the total number of instances, any statistical uncertainty (standard error, bootstrap, or hypothesis test), or breakdown of the fraction versus N. This directly undermines assessment of the 70% figure's robustness given the N≤12 regime.

    Authors: We agree with the referee that including the total number of instances, statistical uncertainties, and a breakdown by N would strengthen the presentation. In the revised version, we will report the exact number of instances sampled in the scaling analysis, include appropriate error estimates or statistical tests for the 70% figure, and provide a table or figure showing the percentage of instances with the monotonic trend for each N up to 12. This will allow readers to better evaluate the robustness within the studied regime. revision: yes

  2. Referee: [Scaling analysis] Scaling analysis: no data or plot shows how the fraction of instances obeying the monotonic trend evolves with N, nor is there a finite-size scaling collapse or extrapolation. The observed percentage is therefore confined to the studied regime and cannot yet support claims of generic behavior.

    Authors: We note that our analysis was focused on the behavior up to N=12, which is relevant for current quantum annealing hardware. We will add a plot depicting the evolution of the fraction of instances showing monotonically increasing fairness with increasing N. However, performing a finite-size scaling collapse or extrapolation would require a theoretical model for the scaling of unfair sampling, which is beyond the scope of this empirical study. We will explicitly state the limitations of extrapolating to larger N in the revised manuscript. revision: partial

  3. Referee: [Numerical simulations and D-Wave runs] Numerical simulations and D-Wave runs: the fairness metric and ground-state probabilities lack reported error bars or statistical tests, and the instance-generation procedure plus annealing schedules are described at insufficient detail to judge representativeness or enable reproduction.

    Authors: We appreciate this feedback on the presentation of our numerical and experimental results. In the revised manuscript, we will include error bars on all relevant plots for the fairness metric and ground-state probabilities, derived from multiple independent runs or statistical resampling. Additionally, we will provide more comprehensive details on the random instance generation procedure, including the specific parameters for generating weighted graphs, and the exact annealing schedules and parameters used in both the numerical simulations and the D-Wave Advantage2 experiments to ensure reproducibility. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical measurements of fairness from direct sampling

full rationale

The paper reports numerical simulations and D-Wave experiments that measure sampling fairness directly from the empirical distribution of obtained bit strings in weighted graph bipartitioning instances. The central observation (>70% of instances up to N=12 show monotonically increasing fairness with penalty strength) is obtained by counting the monotonicity property over randomly generated instances; no parameters are fitted to a subset and then re-predicted, no equations are derived that reduce to their own inputs by construction, and no self-citation chain is invoked to justify a uniqueness theorem or ansatz that carries the main claim. The work is therefore self-contained as an observational study whose results stand or fall on the reported simulation and hardware data rather than on any internal definitional loop.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard Ising formulation of GBP plus the penalty method; no new entities are introduced and the only tunable quantity is the penalty coefficient itself, which is varied rather than fitted to the fairness metric.

free parameters (1)
  • penalty coefficient
    Varied across a range to observe its effect on fairness; not fitted to any target fairness value.
axioms (1)
  • domain assumption The problem can be encoded as a quadratic unconstrained binary optimization (QUBO) via the penalty method.
    Standard for constrained combinatorial optimization on quantum annealers; invoked when the GBP is mapped to the Ising Hamiltonian.

pith-pipeline@v0.9.0 · 5516 in / 1356 out tokens · 46014 ms · 2026-05-10T16:28:21.899248+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Quantum annealing in the transverse Ising model,

    T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,”Phys. Rev. E, vol. 58, no. 5, p. 5355, 1998

    work page 1998

  2. [2]

    Quantum annealing and computation: challenges and perspectives,

    B. K. Chakrabarti, H. Leschke, P. Ray, T. Shirai, and S. Tanaka, “Quantum annealing and computation: challenges and perspectives,” Philos. Trans. R. Soc. A: Math. Phys. Eng. Sci., vol. 381, no. 2241, p. 20210419, 12 2022

    work page 2022

  3. [3]

    A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem,

    E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, “A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem,”Science, vol. 292, no. 5516, pp. 472–475, 2001

    work page 2001

  4. [4]

    Random generation of combinatorial structures from a uniform distribution,

    M. R. Jerrum, L. G. Valiant, and V . V . Vazirani, “Random generation of combinatorial structures from a uniform distribution,”Theor. Comput. Sci., vol. 43, pp. 169–188, 1986

    work page 1986

  5. [5]

    Constructing SAT filters with a quantum annealer,

    A. Douglass, A. D. King, and J. Raymond, “Constructing SAT filters with a quantum annealer,” inInternational Conference on Theory and Applications of Satisfiability Testing. Springer, 2015, pp. 104–120

    work page 2015

  6. [6]

    Assessment of quantum annealing for the construction of satisfiability filters,

    M. Azinovi ´c, D. Herr, B. Heim, E. Brown, and M. Troyer, “Assessment of quantum annealing for the construction of satisfiability filters,”SciPost Physics, vol. 2, no. 2, p. 013, 2017

    work page 2017

  7. [7]

    Quantum annealing for problems with ground-state degeneracy,

    Y . Matsuda, H. Nishimori, and H. G. Katzgraber, “Quantum annealing for problems with ground-state degeneracy,” inJ. Phys. Conf. Ser., vol. 143, no. 1, 2009, p. 012003

    work page 2009

  8. [8]

    Ground-state statistics from annealing algorithms: quantum ver- sus classical approaches,

    ——, “Ground-state statistics from annealing algorithms: quantum ver- sus classical approaches,”New J. Phys., vol. 11, no. 7, p. 073021, 2009

    work page 2009

  9. [9]

    Exponentially biased ground- state sampling of quantum annealing machines with transverse-field driving hamiltonians,

    S. Mandra, Z. Zhu, and H. G. Katzgraber, “Exponentially biased ground- state sampling of quantum annealing machines with transverse-field driving hamiltonians,”Phys. Rev. Lett., vol. 118, no. 7, p. 070502, 2017

    work page 2017

  10. [10]

    Uncertain fate of fair sampling in quantum annealing,

    M. S. K ¨onz, G. Mazzola, A. J. Ochoa, H. G. Katzgraber, and M. Troyer, “Uncertain fate of fair sampling in quantum annealing,”Phys. Rev. A, vol. 100, no. 3, p. 030303, 2019

    work page 2019

  11. [11]

    Graph minor embedding can affect sampling degenerate ground states using quantum annealing,

    N. Maruyama, M. Ohzeki, and K. Tanaka, “Graph minor embedding can affect sampling degenerate ground states using quantum annealing,”J. Phys. Soc. Japan, vol. 95, no. 1, p. 013002, 2026

    work page 2026

  12. [12]

    Ising formulations of many NP problems,

    A. Lucas, “Ising formulations of many NP problems,”Front. Phys., vol. 2, p. 74887, 2014

    work page 2014

  13. [13]

    Tanaka, R

    S. Tanaka, R. Tamura, and B. K. Chakrabarti,Quantum spin glasses, annealing and computation. Cambridge University Press, 2017

    work page 2017

  14. [14]

    Formulating and solving routing problems on quantum computers,

    S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. Bernal Neira, and D. Greenberg, “Formulating and solving routing problems on quantum computers,”IEEE Transactions on Quantum Engineering, vol. 2, pp. 1–17, 2021

    work page 2021

  15. [15]

    Dynamic portfolio optimization with real datasets using quantum processors and quantum-inspired tensor networks,

    S. Mugel, C. Kuchkovsky, E. S ´anchez, S. Fern ´andez-Lorenzo, J. Luis- Hita, E. Lizaso, and R. Or ´us, “Dynamic portfolio optimization with real datasets using quantum processors and quantum-inspired tensor networks,”Physical Review Research, vol. 4, p. 013006, 2022

    work page 2022

  16. [16]

    Quantum bridge analytics I: a tutorial on formulating and using QUBO models,

    F. Glover, G. Kochenberger, and Y . Du, “Quantum bridge analytics I: a tutorial on formulating and using QUBO models,”4OR, vol. 17, no. 4, pp. 335–371, 2019

    work page 2019

  17. [17]

    Application of Ising machines and a software development for Ising machines,

    K. Tanahashi, S. Takayanagi, T. Motohashi, and S. Tanaka, “Application of Ising machines and a software development for Ising machines,”J. Phys. Soc. Japan, vol. 88, no. 6, p. 061010, 2019

    work page 2019

  18. [18]

    Extending sample persistence variable reduction for constrained combinatorial optimization problems,

    S. Ide, S. Kikuchi, and S. Tanaka, “Extending sample persistence variable reduction for constrained combinatorial optimization problems,” arXiv:2509.19280, 2025

    work page arXiv 2025

  19. [19]

    QuTiP 5: The quantum toolbox in Python,

    N. Lambert, E. Gigu `ere, P. Menczel, B. Li, P. Hopf, G. Su ´arez, M. Gali, J. Lishman, R. Gadhvi, R. Agarwal, A. Galicia, N. Shammah, P. Nation, J. R. Johansson, S. Ahmed, S. Cross, A. Pitchford, and F. Nori, “QuTiP 5: The quantum toolbox in Python,”Phys. Rep., vol. 1153, pp. 1–62, 2026

    work page 2026

  20. [20]

    QuTiP: An open-source Python framework for the dynamics of open quantum systems,

    J. Johansson, P. Nation, and F. Nori, “QuTiP: An open-source Python framework for the dynamics of open quantum systems,”Comput. Phys. Commun., vol. 183, no. 8, pp. 1760–1772, 2012

    work page 2012

  21. [21]

    QuTiP 2: A Python framework for the dynamics of open quantum systems,

    ——, “QuTiP 2: A Python framework for the dynamics of open quantum systems,”Comput. Phys. Commun., vol. 184, no. 4, pp. 1234–1240, 2013

    work page 2013

  22. [22]

    QPU solver parameters: auto-scale,

    D-Wave Systems, Inc., “QPU solver parameters: auto-scale,” https://docs.dwavequantum.com/en/latest/quantum research/solver parameters.html#auto-scale, accessed: 2026-03-27

    work page 2026