Quantum Approximate Optimisation for Not-All-Equal SAT

• URL: http://arxiv.org/abs/2401.02852v1
• Date: Fri, 5 Jan 2024 15:11:24 GMT
• Title: Quantum Approximate Optimisation for Not-All-Equal SAT
• Authors: Andrew El-Kadi, Roberto Bondesan
• Abstract summary: 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.
• Score: 9.427635404752936
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Establishing quantum advantage for variational quantum algorithms is an important direction in quantum computing. In this work, we apply the Quantum Approximate Optimisation Algorithm (QAOA) -- a popular variational quantum algorithm for general combinatorial optimisation problems -- to a variant of the satisfiability problem (SAT): Not-All-Equal SAT (NAE-SAT). We focus on regimes where the problems are known to have solutions with low probability and introduce a novel classical solver that outperforms existing solvers. Extensively benchmarking QAOA against this, we show that while the runtime of both solvers scales exponentially with the problem size, the scaling exponent for QAOA is smaller for large enough circuit depths. This implies a polynomial quantum speedup for solving NAE-SAT.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
  Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization. We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
  arXiv  Detail & Related papers  (2024-07-08T22:02:39Z)
• Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer [0.0]
  Block ENcoding Quantum (BEQO) is a hybrid quantum solver that uses block encoding to represent the cost function. Our findings confirm that BENQO performs significantly better than QAOA and competes with VQE across a variety of performance metrics.
  arXiv  Detail & Related papers  (2024-04-22T10:10:29Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  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.
  arXiv  Detail & Related papers  (2023-03-02T11:52:39Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits [15.279642278652654]
  We present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
  arXiv  Detail & Related papers  (2021-12-21T12:41:31Z)
• Quantum mean value approximator for hard integer value problems [19.4417702222583]
  We show that an optimization can be improved substantially by using an approximation rather than the exact expectation. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of general integer-value problems.
  arXiv  Detail & Related papers  (2021-05-27T13:03:52Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer [0.0]
  The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves optimization problems. We develop an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA.
  arXiv  Detail & Related papers  (2020-05-20T18:00:01Z)

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.