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 (14)

• Mathematical Foundation of Quantum Annealing
• 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
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Fair Sampling by Simulated Annealing on Quantum Annealer
• Model Counting in Product Configuration
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Fair sampling of ground-state configurations of binary optimization problems
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering

Cited by in corpus (1)

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