Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT

Abstract

The Boolean satisfiability problem (SAT), in particular 3SAT with its bounded clause size, is a well-studied problem since a wide range of decision problems can be reduced to it. Due to its high complexity, examining potentials of quantum algorithms for solving 3SAT more efficiently is an important topic. Since 3SAT can be formulated as unstructured search for satisfying variable assignments, the amplitude amplification algorithm can be applied. However, the high circuit complexity of amplitude amplification hinders its use on near-term quantum systems. On the other hand, the Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices in the near future due to its simple quantum ansatz. However, although QAOA generally exhibits a high approximation ratio, there are 3SAT problem instances where its success probability decreases using current implementations. To address this problem, in this paper we introduce amplitude amplification-inspired variants of QAOA to improve the success probability for 3SAT. For this, (i) three amplitude amplification-inspired QAOA variants are introduced and implemented, (ii) the variants are experimental compared with a standard QAOA implementation, and (iii) the impact on the success probability and ansatz complexity is analyzed. The experiment results show that an improvement in the success probability can be achieved with only a moderate increase in circuit complexity.

References in corpus (23)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Elementary gates for quantum computation
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• Tight bounds on quantum searching
• A Quantum Algorithm for Finding the Minimum
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• $XY$-mixers: analytical and numerical results for QAOA
• Reachability Deficits in Quantum Approximate Optimization
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• MAXCUT QAOA performance guarantees for p >1
• Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
• Applying quantum algorithms to constraint satisfaction problems
• A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
• Variationally Learning Grover's Quantum Search Algorithm
• Ground State Spin Logic
• Quantum Computational Phase Transition in Combinatorial Problems
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
• Efficient quantum circuit synthesis for SAT-oracle with limited ancillary qubit

Cited by in corpus (2)

• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations