Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering

Abstract

The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT problems (All-SAT). G-QAOA is less resource-intensive and more adaptable for 3-SAT and Max-SAT than Grover's algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles.

References in corpus (47)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Quantum Amplitude Amplification and Estimation
• Quantum computation with ions in thermal motion
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Training variational quantum algorithms is NP-hard
• A Race Track Trapped-Ion Quantum Processor
• Warm-starting quantum optimization
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Hyper-optimized tensor network contraction
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Basic circuit compilation techniques for an ion-trap quantum machine
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Concentration in Quantum Approximate Optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Assessing requirements to scale to practical quantum advantage
• Challenges of variational quantum optimization with measurement shot noise
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• MLIC: A MaxSAT-Based framework for learning interpretable classification rules
• Principled Network Reliability Approximation: A Counting-Based Approach
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• Fair Sampling Error Analysis on NISQ Devices
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Quantum Alternating Operator Ansatz (QAOA) beyond low depth with gradually changing unitaries
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms
• Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz
• Ising Model Partition Function Computation as a Weighted Counting Problem

Cited by in corpus (5)

• Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems
• Counting with the quantum alternating operator ansatz
• Using deep learning to construct stochastic local search SAT solvers with performance bounds