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

• URL: http://arxiv.org/abs/2303.01183v1
• Date: Thu, 2 Mar 2023 11:52:39 GMT
• Title: Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Authors: Alexander Mandl, Johanna Barzen, Marvin Bechtold, Frank Leymann, Karoline Wild
• Abstract summary: The amplitude amplification algorithm can be applied to unstructured search for satisfying variable assignments. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices. We introduce amplitude amplification-inspired variants of QAOA to improve the success probability for 3SAT.
• Score: 55.78588835407174
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields [0.0]
  We introduce a new iterative quantum algorithm, called Iterative Symphonic Tunneling for Satisfiability problems (IST-SAT) IST-SAT solves quantum spin glass optimization problems using high-frequency oscillating transverse fields.
  arXiv  Detail & Related papers  (2024-08-13T02:09:30Z)
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering [6.86850788361785]
  This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling. 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 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.
  arXiv  Detail & Related papers  (2024-02-04T19:01:27Z)
• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  We apply variational quantum algorithm QAOA to a variant of satisfiability problem (SAT): Not-All-Equal SAT. We show that while the runtime of both solvers scales exponentially with the problem size, the scaling for QAOA is smaller for large enough circuit depths.
  arXiv  Detail & Related papers  (2024-01-05T15:11:24Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems. The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
  arXiv  Detail & Related papers  (2023-06-07T12:19:22Z)
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm [4.03537866744963]
  We show that the adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-3-SAT problems. Our work paves the way for realizing quantum advantages for optimization problems on NISQ devices.
  arXiv  Detail & Related papers  (2022-10-06T11:25:26Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• A Quantum-Inspired Classical Solver for Boolean k-Satisfiability Problems [0.0]
  We describe an algorithmic approach to the k-satisfiability (k-SAT) problem that is inspired by the amplification amplification algorithm. We then discuss meaningfully leveraging this setting in a classical digital or analog computing setting to identify the strengths and limitations of AmplifySAT.
  arXiv  Detail & Related papers  (2021-09-21T16:10:52Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.