Parallel Quantum Annealing

• URL: http://arxiv.org/abs/2111.05995v4
• Date: Tue, 29 Nov 2022 02:57:04 GMT
• Title: Parallel Quantum Annealing
• Authors: Elijah Pelofske, Georg Hahn, Hristo N. Djidjev
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum annealers of D-Wave Systems, Inc., offer an efficient way to compute high quality solutions of NP-hard problems. This is done by mapping a problem onto the physical qubits of the quantum chip, from which a solution is obtained after quantum annealing. However, since the connectivity of the physical qubits on the chip is limited, a minor embedding of the problem structure onto the chip is required. In this process, and especially for smaller problems, many qubits will stay unused. We propose a novel method, called parallel quantum annealing, to make better use of available qubits, wherein either the same or several independent problems are solved in the same annealing cycle of a quantum annealer, assuming enough physical qubits are available to embed more than one problem. Although the individual solution quality may be slightly decreased when solving several problems in parallel (as opposed to solving each problem separately), 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 when compared to solving each problem sequentially on the quantum annealer. Additionally, we show that solving a single Maximum Clique problem using parallel quantum annealing reduces the TTS significantly.

Related papers

• Solving eigenvalue problems obtained by the finite element method on a quantum annealer using only a few qubits [0.0]
  One of the main obstacles for achieving a practical quantum advantage in quantum computing lies in the relatively small number of qubits currently available in quantum hardware. We show how to circumvent this problem in the context of eigenvalue problems obtained by the finite element method. As an example, we apply AQAE to eigenvalue problems that are relevant in a wide range of contexts, such as electromagnetism, acoustics and seismology.
  arXiv  Detail & Related papers  (2024-10-17T16:39:03Z)
• 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)
• Dynamic Programming on a Quantum Annealer: Solving the RBC Model [1.0681288493631977]
  We introduce a novel approach to solving dynamic programming problems, such as those in many economic models, on a quantum annealer. We achieve an order-of-magnitude speed-up in solving the real business cycle model over benchmarks in the literature.
  arXiv  Detail & Related papers  (2023-06-07T09:38:42Z)
• 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)
• Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits [0.0]
  We show that long term trends in solution quality exist on the D-Wave device, and that the unused qubits can be used to measure the current level of noise of the quantum system. In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time.
  arXiv  Detail & Related papers  (2022-09-12T23:06:51Z)
• 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)
• 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)
• 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)
• 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)
• Advanced unembedding techniques for quantum annealers [0.0]
  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.
  arXiv  Detail & Related papers  (2020-09-10T17:49:43Z)

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.