Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems

• URL: http://arxiv.org/abs/2604.11449v1
• Date: Mon, 13 Apr 2026 13:28:49 GMT
• Title: Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems
• Abstract summary: We study how the penalty coefficient in the penalty method affects sampling fairness.<n>More than 70% of instances exhibit monotonically increasing sampling fairness as the penalty coefficient increases.<n>These results show that increasing the penalty coefficient improves sampling fairness, though at the cost of ground-state probability.
• Score: 0.7519872646378835
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability [0.7734726150561088]
  sequential sampling rules that adaptively bias sampling probabilities in order to achieve faster convergence of the empirical distribution to a desired target law.<n>Self-balancing sampler is simple to implement, arises naturally among a class of Markovian samplers.<n>Results support a practical framework for reducing repeated selections and long gaps in coverage without making future selections overly predictable.
  arXiv  Detail & Related papers  (2026-07-23T01:10:42Z)
• Stratified Sampling for Quasi-Probability Decompositions [0.0]
  Quasi-probability decompositions (QPDs) have proven essential in many quantum algorithms and protocols.<n>We develop a broad framework for accounting for and reducing this variance.<n> Numerical simulations of typical QPDs demonstrate constant-factor reductions in overall variance.
  arXiv  Detail & Related papers  (2026-02-11T17:46:40Z)
• Importance-Weighted Non-IID Sampling for Flow Matching Models [5.995277983968318]
  We propose an importance-weighted non-IID sampling framework that jointly draws multiple samples to cover diverse, salient regions of a flow's distribution.<n>To balance diversity and quality, we introduce a score-based regularization for the diversity mechanism.<n>Our method produces diverse, high-quality samples and accurate estimates of both importance weights and expectations.
  arXiv  Detail & Related papers  (2025-11-21T22:05:56Z)
• Chance-constrained Flow Matching for High-Fidelity Constraint-aware Generation [46.932479632530764]
  Chance-constrained Flow Matching integrates optimization into the sampling process, enabling effective enforcement of hard constraints.<n>Experiments show that CCFM outperforms current state-of-the-art constrained generative models in modeling complex physical systems.
  arXiv  Detail & Related papers  (2025-09-29T17:56:52Z)
• Sample space filling analysis for boson sampling validation [0.0]
  We show that due to the intrinsic nature of the boson sampling wave function, its filling behavior can be computationally efficiently distinguished from classically simulated cases. We propose a new validation protocol based on the sample space filling analysis and test it for problems of up to $20$ photons injected into a $400$-mode interferometer.
  arXiv  Detail & Related papers  (2024-11-21T12:39:37Z)
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA [1.0878040851638]
  We numerically examine the fair sampling properties transverse field mixer QAOA, and Grover Mixer QAOA.<n>We show that some problem instances clearly saturate the Shannon entropy of $0$ with a maximally biased distribution.<n>Other problem instances never deviate from a maximum Shannon entropy (uniform) at any $p$ step.
  arXiv  Detail & Related papers  (2024-11-08T02:54:28Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling [156.7248383178991]
  Collaborative Metric Learning (CML) paradigm has aroused wide interest in the area of recommendation systems (RS) We find that negative sampling would lead to a biased estimation of the generalization error. Motivated by this, we propose an efficient alternative without negative sampling for CML named textitSampling-Free Collaborative Metric Learning (SFCML)
  arXiv  Detail & Related papers  (2022-06-23T08:50:22Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Variational Refinement for Importance Sampling Using the Forward Kullback-Leibler Divergence [77.06203118175335]
  Variational Inference (VI) is a popular alternative to exact sampling in Bayesian inference. Importance sampling (IS) is often used to fine-tune and de-bias the estimates of approximate Bayesian inference procedures. We propose a novel combination of optimization and sampling techniques for approximate Bayesian inference.
  arXiv  Detail & Related papers  (2021-06-30T11:00:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.