Optimizing the optimizer: decomposition techniques for quantum annealing

doi:10.1007/s42484-021-00039-9

Return

Optimizing the optimizer: decomposition techniques for quantum annealing

2021-03-26

PRE

DOI：10.1007/s42484-021-00039-9

Original

Original request for help

Save

Abstract

En 中文

Although quantum computing hardware has evolved significantly in recent years, spurred by increasing industrial and government interest, the size limitation of current generation quantum computers remains an obstacle when applying these devices to relevant, real-world problems. In order to effectively exploit the potential benefits of quantum computing, heterogeneous approaches that combine both classical and quantum computing techniques are needed. In this work, we explore multiple heterogeneous algorithms for solving a variety of industry-relevant benchmark problems in order to understand how best to leverage quantum computers given current constraints. Our results indicate the following: (1) that solver performance is highly dependent on the structure (size and edge density) of the problem graph; (2) that reusing a single fixed problem embedding, as opposed to dynamically searching for problem embeddings, is key to avoiding computational bottlenecks; (3) that solutions of better quality are produced by algorithms that iteratively propagate the influence that solving an individual sub-problem has to the remainder of the larger problem; and (4) that the Qbsolv algorithm (which implements the aforementioned techniques) is, at this time, the state-of-the-art in producing quality solutions, in a timely fashion, to a variety of theoretical and real-world problems too large to directly embed onto a quantum annealing device.

Keywords:

Optimization

Quantum

Quantum computing

Quantum annealing

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.