Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing-the heuristic employed in current commercially available quantum annealing machines-has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.
Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing-the heuristic employed in current commercially available quantum annealing machines-has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.
We study the performance of the D-Wave 2X quantum annealing machine on systems with well-controlled ground-state degeneracy. While obtaining the ground state of a spin-glass benchmark instance represents a difficult task, the gold standard for any optimization algorithm or machine is to sample all solutions that minimize the Hamiltonian with more or less equal probability. Our results show that while naive transverse-field quantum annealing on the D-Wave 2X device can find the ground-state energy of the problems, it is not well suited in identifying all degenerate ground-state configurations associated with a particular instance. Even worse, some states are exponentially suppressed, in agreement with previous studies on toy model problems [New J. Phys. 11, 073021 (2009)NJOPFM1367-263010.1088/1367-2630/11/7/073021]. These results suggest that more complex driving Hamiltonians are needed in future quantum annealing machines to ensure a fair sampling of the ground-state manifold.
We present and apply a general-purpose, multistart algorithm for improving the performance of low-energy samplers used for solving optimization problems. The algorithm iteratively fixes the value of a large portion of the variables to values that have a high probability of being optimal. The resulting problems are smaller and less connected, and samplers tend to give better low-energy samples for these problems. The algorithm is trivially parallelizable since each start in the multistart algorithm is independent, and could be applied to any heuristic solver that can be run multiple times to give a sample. We present results for several classes of hard problems solved using simulated annealing, path-integral quantum Monte Carlo, parallel tempering with isoenergetic cluster moves, and a quantum annealer, and show that the success metrics and the scaling are improved substantially. When combined with this algorithm, the quantum annealer's scaling was substantially improved for native Chimera graph problems. In addition, with this algorithm the scaling of the time to solution of the quantum annealer is comparable to the Hamze-de Freitas-Selby algorithm on the weak-strong cluster problems introduced by Boixo et al. Parallel tempering with isoenergetic cluster moves was able to consistently solve three-dimensional spin glass problems with 8000 variables when combined with our method, whereas without our method it could not solve any.
The quantum alternating operator ansatz, a generalization of the quantum approximate optimization algorithm (QAOA), is a quantum algorithm used for approximately solving combinatorial optimization problems. QAOA typically uses the transverse field mixer as the driving Hamiltonian. One of the interesting properties of the transverse field driving Hamiltonian is that it results in nonuniform sampling of degenerate ground states of optimization problems. In this study, we numerically examine the fair sampling properties of the transverse field mixer QAOA, and Grover mixer QAOA (GM-QAOA), which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to a large enough p such that the mean expectation value converges to an optimal approximation ratio of 1. This comparison is performed with high-quality heuristically computed, but not necessarily optimal, QAOA angles, which give strictly monotonically improving solution quality as p increases. These angles are computed using the Julia based numerical simulation software JuliQAOA. Fair sampling of degenerate ground states is quantified using the Shannon entropy of the ground-state amplitudes distribution. The fair sampling properties are reported on several quantum signature Hamiltonians from previous quantum annealing fair sampling studies. Small random fully connected spin glasses are shown, which exhibit exponential suppression of some degenerate ground states with transverse field mixer QAOA. The transverse field mixer QAOA simulations show that some problem instances clearly saturate the Shannon entropy of 0 with a maximally biased distribution that occurs when the learning converges to an approximation ratio of 1 while other problem instances never deviate from a maximum Shannon entropy (uniform distribution) at any p step.
We study the fair sampling properties of hybrid quantum-classical Markov chain Monte Carlo (MCMC) algorithms for combinatorial optimization problems with degenerate ground states. While quantum optimization heuristics such as quantum annealing and the quantum approximate optimization algorithm (QAOA) are known to induce biased sampling, hybrid quantum-classical MCMC incorporates quantum dynamics only as a proposal transition and enforces detailed balance through classical acceptance steps. Using small Ising models, we show that MCMC post-processing corrects the sampling bias of quantum dynamics and restores near-uniform sampling over degenerate ground states. We then apply the method to random k-SAT problems near the satisfiability threshold. For random 2-SAT, a hybrid MCMC combining QAOA-assisted neural proposals with single spin-flip updates achieves fairness comparable to that of PT-ICM. For random 3-SAT, where such classical methods are no longer applicable, the hybrid MCMC still attains approximately uniform sampling. We also examine solution counting and find that the required number of transitions is comparable to that of WalkSAT. These results indicate that hybrid quantum-classical MCMC provides a viable framework for fair sampling and solution enumeration.
A wide variety of optimization techniques, both exact and heuristic, tend to be biased samplers. This means that when attempting to find multiple uncorrelated solutions of a degenerate Boolean optimization problem a subset of the solution space tends to be favored while, in the worst case, some solutions can never be accessed by the algorithm used. Here we present a simple postprocessing technique that improves sampling for any optimization approach, either quantum or classical. More precisely, starting from a pool of a few optimal configurations, the algorithm generates potentially new solutions via rejection-free cluster updates at zero temperature. Although the method is not ergodic and there is no guarantee that all the solutions can be found, fair sampling is typically improved. We illustrate the effectiveness of our method by improving the exponentially biased data produced by the D-Wave 2X quantum annealer [S. Mandrà et al., Phys. Rev. Lett. 118, 070502 (2017)PRLTAO0031-900710.1103/PhysRevLett.118.070502], as well as data from three-dimensional Ising spin glasses. As part of the study, we also show that sampling is improved when suboptimal states are included and discuss sampling at a finite fixed temperature.
Recently, it was demonstrated both theoretically and experimentally on the D-Wave quantum annealer that transverse-field quantum annealing does not find all ground states with equal probability. In particular, it was proposed that more complex driver Hamiltonians beyond transverse fields might mitigate this shortcoming. Here, we investigate the mechanisms of (un)fair sampling in quantum annealing. While higher-order terms can improve the sampling for selected small problems, we present multiple counterexamples where driver Hamiltonians that go beyond transverse fields do not remove the sampling bias. Using perturbation theory we explain why this is the case. In addition, we present large-scale quantum Monte Carlo simulations for spin glasses with known degeneracy in two space dimensions and demonstrate that the fair-sampling performance of quadratic driver terms is comparable to standard transverse-field drivers. Our results suggest that quantum annealing machines are not well suited for sampling applications, unless postprocessing techniques to improve the sampling are applied.