The Fair in Unfair Quantum Ground-State Sampling

Shunta Ide, Shu Tanaka

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.

Jonas Maziero

Niek J. Bouman, Serge Fehr

Naoki Maruyama, Masayuki Ohzeki

In applications where multiple optimal solutions are needed, transverse-field quantum annealing (QA) is known to sample degenerate ground states in a strongly biased manner. Despite extensive empirical observations, it remains unclear which features of degenerate ground states are preferentially sampled and why by QA. Here we analyze the final states using degenerate perturbation theory to characterize the preference among them. In this analysis, the adjacency matrix of the graph composed by the ground states naturally emerges, and we can predict the eigenvector centralities (one of the node centralities) are related to the probabilities of these states. We verify this prediction on toy models where degeneracy is lifted at first and second order, and we show that second-order weights encode local barrier information, relating sampling fairness to the flatness of the local energy landscape. Finally, this perspective suggests two practical routes toward fair sampling -- promoting connectivity of the graph and reducing heterogeneity of centralities -- and we illustrate consistency with higher-order drivers and minor-embedding transformations.

Vaibhaw Kumar, Casey Tomlin, C. Nehrkorn +2 more

Sampling all ground states of a Hamiltonian with equal probability is a desired feature of a sampling algorithm, but recent studies indicate that common variants of transverse field quantum annealing sample the ground state subspace unfairly. In this note, we present perturbation theory arguments suggesting that this deficiency can be corrected by employing reverse annealing-inspired paths. We confirm that this conclusion holds in simulations of previously studied small instances with degeneracy, as well as larger instances on quantum annealing hardware.

Patrick M. Hayden, Debbie Leung, Peter W. Shor +1 more