The potential of quantum annealing for rapid solution structure identification
- PDF / 1,058,497 Bytes
- 25 Pages / 439.642 x 666.49 pts Page_size
- 54 Downloads / 167 Views
The potential of quantum annealing for rapid solution structure identification Yuchen Pang1
· Carleton Coffrin2
· Andrey Y. Lokhov2
· Marc Vuffray2
Accepted: 15 October 2020 © The Author(s) 2020
Abstract The recent emergence of novel computational devices, such as quantum computers, coherent Ising machines, and digital annealers presents new opportunities for hardware-accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has the potential to quickly identify the structure of high-quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggests that quantum annealing’s performance on the proposed optimization tasks is distinct. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and suggests the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches. Keywords Discrete optimization · Ising model · Quadratic unconstrained binary optimization · Local search · Quantum annealing · Large neighborhood search · Integer programming · Belief propagation Carleton Coffrin
[email protected] Yuchen Pang [email protected] Andrey Y. Lokhov [email protected] Marc Vuffray [email protected] 1
Department of Computer Science, University of Illinois at Urbana-Champaign, Champaign, IL, 61801, USA
2
Advanced Network Science Initiative, Los Alamos National Laboratory, Los Alamos, NM, 87545, USA
Constraints
1 Introduction As the challenge of scaling traditional transistor-based Central Processing Unit (CPU) technology continues to increase, experimental physicists and high-tech companies have begun to explore radically different computational technologies, such as quantum computers [14, 41, 62], quantum annealers [43, 45] and coherent Ising machines [40, 47, 59]. The goal of all of these technologies is to leverage the dynamical evolution of a physical system to perform a computation that is challenging to emulate using traditional CPU technology, the most notable example being the simulation of quantum physics [29]. Despite their entirely disparate physical implementations, optimization of quadratic functions over binary variables (e.g., the Quadratic Unconstrained Binary Optimization (QUBO) and Ising models [13]) has emerged as a challenging computational task that a wide variety of novel hardware platforms can address. As these technologies mature, it may be possible for this specialized hardware to rapidly solve challenging co
Data Loading...
