Parallel Quantum Annealing
arXiv:2111.05995 · doi:10.1038/s41598-022-08394-8
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.
arXiv comment13 pages. v4: format improvements
References in corpus (14)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- A practical heuristic for finding graph minors
- Massively Parallel Probabilistic Computing with Sparse Ising Machines
- Quantum annealing correction for random Ising problems
- Benchmarking a quantum annealing processor with the time-to-target metric
- Solving large Maximum Clique problems on a quantum annealer
- Decomposition algorithms for solving NP-hard problems on a quantum annealer
- Quantum Annealing Algorithms for Boolean Tensor Networks
- Extending the D-Wave with support for Higher Precision Coefficients
Cited by in corpus (11)
- Quantum Annealing: An Overview
- Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
- Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era
- Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
- Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- Quantum Annealing Algorithms for Boolean Tensor Networks
- Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
- 4-clique Network Minor Embedding for Quantum Annealers
- Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
- Mapping State Transition Susceptibility in Quantum Annealing
- Leveraging Quantum Annealer to identify an Event-topology at High Energy Colliders