Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA

Abstract

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 non-uniform sampling of degenerate ground states of optimization problems. In this study we numerically examine the fair sampling properties transverse field mixer QAOA, and Grover Mixer QAOA (GM-QAOA) which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to 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 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.

References in corpus (30)

• Quantum Annealing in the Transverse Ising Model
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Mathematical Foundation of Quantum Annealing
• Experimental signature of programmable quantum annealing
• $XY$-mixers: analytical and numerical results for QAOA
• Decoherence in adiabatic quantum computation
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Reexamining classical and quantum models for the D-Wave One processor
• Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Uncertain fate of fair sampling in quantum annealing
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Programmable Quantum Annealers as Noisy Gibbs Samplers
• Fair Sampling by Simulated Annealing on Quantum Annealer
• Model Counting in Product Configuration
• Advantages of Unfair Quantum Ground-State Sampling
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
• Fair sampling of ground-state configurations of binary optimization problems
• Fair Sampling Error Analysis on NISQ Devices
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Comment on "Evidence for nontrivial ground-state structure of 3d +/- J spin glasses"
• Feeding the multitude: A polynomial-time algorithm to improve sampling
• Sampling diverse near-optimal solutions via algorithmic quantum annealing
• Dynamics of open quantum systems by interpolation of von Neumann and classical master equations, and its application to quantum annealing

Cited by in corpus (1)

• Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems