Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs

• URL: http://arxiv.org/abs/2302.14369v1
• Date: Tue, 28 Feb 2023 07:49:10 GMT
• Title: Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
• Authors: Seokho Jeong, Minhyuk Kim, Minki Hhan, and Jaewook Ahn
• Abstract summary: An experiment is presented to demonstrate the use of Rydberg atoms to solve (i.e., to program and obtain the solution of) the satisfiability (3-SAT) problem.
• Score: 1.2179548969182574
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Finding a quantum computing method to solve nondeterministic polynomial time (NP)-complete problems is currently of paramount importance in quantum information science. Here an experiment is presented to demonstrate the use of Rydberg atoms to solve (i.e., to program and obtain the solution of) the satisfiability (3-SAT) problem, which is the prototypical NP-complete problem allowing general programming of all NP problems. Boolean expressions of the 3-SAT problem are programmed with the blockade interactions of Rydberg atom graphs and their many-body ground states are experimentally obtained, to determine the satisfiabilities of the given 3-SAT problem instances quantum mechanically.

Related papers

• Atom Cavity Encoding for NP-Complete Problems [5.482856804346147]
  We present encoding schemes for numerous NP-complete problems, encompassing the majority of Karp's 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems.
  arXiv  Detail & Related papers  (2024-07-16T15:32:42Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
  We develop a parallel quantum SAT solver, which reduces the time complexity in each iteration from linear time O(m) to constant time O(1) by utilising extra entangled qubits. We have proved the correctness of our approaches and demonstrated them in simulations.
  arXiv  Detail & Related papers  (2023-08-07T06:52:06Z)
• 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)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• On Theoretical Complexity and Boolean Satisfiability [0.0]
  This thesis introduces some of the most central concepts in the Theory of Computing. We then explore some of its tractable as well as intractable variants such as Horn-SAT and 3-SAT. Finally, we establish reductions from 3-SAT to some of the famous NP-complete graph problems.
  arXiv  Detail & Related papers  (2021-12-22T10:13:34Z)
• Rydberg Quantum Wires for Maximum Independent Set Problems with Nonplanar and High-Degree Graphs [0.7046417074932257]
  We present experiments with Rydberg atoms to solve non-deterministic-time hard (NP-hard) problems. We introduce the Rydberg quantum wire scheme with auxiliary atoms to engineer long-ranged networks of qubit atoms. Three-dimensional (3D) Rydberg-atom arrays are constructed, overcoming the intrinsic limitations of two-dimensional arrays.
  arXiv  Detail & Related papers  (2021-09-08T09:37:18Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
  We devise three effective QAE-based learning protocols to address three classically computational hard learning problems. Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)

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.