Advanced unembedding techniques for quantum annealers

• URL: http://arxiv.org/abs/2009.05028v3
• Date: Wed, 28 Dec 2022 00:56:30 GMT
• Title: Advanced unembedding techniques for quantum annealers
• Authors: Elijah Pelofske, Georg Hahn, Hristo Djidjev
• Abstract summary: We present tailored unembedding techniques for four important NP-hard problems. Our techniques are simple and yet make use of structural properties of the problem being solved.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The D-Wave quantum annealers make it possible to obtain high quality solutions of NP-hard problems by mapping a problem in a QUBO (quadratic unconstrained binary optimization) or Ising form to the physical qubit connectivity structure on the D-Wave chip. However, the latter is restricted in that only a fraction of all pairwise couplers between physical qubits exists. Modeling the connectivity structure of a given problem instance thus necessitates the computation of a minor embedding of the variables in the problem specification onto the logical qubits, which consist of several physical qubits "chained" together to act as a logical one. After annealing, it is however not guaranteed that all chained qubits get the same value (-1 or +1 for an Ising model, and 0 or 1 for a QUBO), and several approaches exist to assign a final value to each logical qubit (a process called "unembedding"). In this work, we present tailored unembedding techniques for four important NP-hard problems: the Maximum Clique, Maximum Cut, Minimum Vertex Cover, and Graph Partitioning problems. Our techniques are simple and yet make use of structural properties of the problem being solved. Using Erd\H{o}s-R\'enyi random graphs as inputs, we compare our unembedding techniques to three popular ones (majority vote, random weighting, and minimize energy). We demonstrate that our proposed algorithms outperform the currently available ones in that they yield solutions of better quality, while being computationally equally efficient.

Related papers

• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All [0.0]
  Solving problems that do not directly map the chip topology remains challenging for quantum computers. The creation of logical qubits as sets of interconnected physical qubits overcomes limitations imposed by the sparsity of the chip. We show that densely connected logical qubits require a lower chain strength to maintain the ferromagnetic coupling.
  arXiv  Detail & Related papers  (2024-04-08T12:24:03Z)
• Logical qubit implementation for quantum annealing: augmented Lagrangian approach [0.0]
  Solving optimization problems on quantum annealers usually requires each variable of the problem to be represented by a connected set of qubits. We propose an optimization-based approach for producing suitable logical qubits representations that results in smaller chain weights.
  arXiv  Detail & Related papers  (2023-01-29T08:45:36Z)
• 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)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• 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)
• Solving Larger Optimization Problems Using Parallel Quantum Annealing [0.0]
  We show that a hybrid approach combining parallel quantum annealing with graph decomposition allows one to solve larger optimization problem accurately. We apply the approach on the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.
  arXiv  Detail & Related papers  (2022-05-24T15:56:15Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Parallel Quantum Annealing [0.0]
  Quantum annealers of D-Wave Systems, Inc., offer an efficient way to compute high quality solutions of NP-hard problems. We propose a novel method, called parallel quantum annealing, to make better use of available qubits. We demonstrate that our method may give dramatic speed-ups in terms of Time-to-Solution (TTS) for solving instances of the Maximum Clique problem.
  arXiv  Detail & Related papers  (2021-11-11T00:10:44Z)
• 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)
• Decomposition algorithms for solving NP-hard problems on a quantum annealer [0.0]
  NP-hard problems have applications in computational chemistry, biochemistry and computer network security. Adaabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems.
  arXiv  Detail & Related papers  (2020-09-10T15:59:06Z)

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.