IEEE High Performance Extreme Computing Conference

Interrogating the performance of quantum annealing for the solution of steady-state subsurface flow

Jessie M. Henderson, Daniel O’Malley, Hari Viswanathan

Published Sep 20, 2021• 3 citations

Abstract

In the 1990s, the principles of quantum mechanics were leveraged to describe how discrete combinatorial optimization problems could be solved using a method called quantum annealing. D-Wave Systems, Inc. has since implemented commercial embodiments. We focus on the use of that hardware to solve discrete hydrologic inverse problems, which can become computationally intense at even moderate sizes. In particular, we interrogate whether contemporary quantum annealers with more qubits, lower noise, and reverse annealing features can improve performance. We find modest improvements in speed and accuracy are possible; however, those benefits are currently constrained to a regime of very rapid, approximate solutions on small meshes. As quantum annealers continue to improve, we expect further encroachment on the performance of classical numerical solvers.

DOI: 10.1109/hpec49654.2021.9622819

Related papers

An approach to quantum-computational hydrologic inverse analysis

Daniel O’Malley

Making predictions about flow and transport in an aquifer requires knowledge of the heterogeneous properties of the aquifer such as permeability. Computational methods for inverse analysis are commonly used to infer these properties from quantities that are more readily observable such as hydraulic head. We present a method for computational inverse analysis that utilizes a type of quantum computer called a quantum annealer. While quantum computing is in an early stage compared to classical computing, we demonstrate that it is sufficiently developed that it can be used to solve certain subsurface flow problems. We utilize a D-Wave 2X quantum annealer to solve 1D and 2D hydrologic inverse problems that, while small by modern standards, are similar in size and sometimes larger than hydrologic inverse problems that were solved with early classical computers. Our results and the rapid progress being made with quantum computing hardware indicate that the era of quantum-computational hydrology may not be too far in the future.

AGUFMDec 1, 20180 citations

An approach to quantum-computational hydrologic inverse analysis

Daniel O’Malley

Scientific ReportsApr 26, 201841 citations

On the emerging potential of quantum annealing hardware for combinatorial optimization

Byron Tasseff, Tameem Albash, Zachary Morrell +4 more

Abstract Over the past decade, the usefulness of quantum annealing hardware for combinatorial optimization has been the subject of much debate. Thus far, experimental benchmarking studies have indicated that quantum annealing hardware does not provide an irrefutable performance gain over state-of-the-art optimization methods. However, as this hardware continues to evolve, each new iteration brings improved performance and warrants further benchmarking. To that end, this work conducts an optimization performance assessment of D-Wave Systems’ Advantage Performance Update computer, which can natively solve sparse unconstrained quadratic optimization problems with over 5,000 binary decision variables and 40,000 quadratic terms. We demonstrate that classes of contrived problems exist where this quantum annealer can provide run time benefits over a collection of established classical solution methods that represent the current state-of-the-art for benchmarking quantum annealing hardware. Although this work does not present strong evidence of an irrefutable performance benefit for this emerging optimization technology, it does exhibit encouraging progress, signaling the potential impacts on practical optimization tasks in the future.

Journal of HeuristicsAug 2, 202442 citations

Extending the computational reach of Quantum Annealing using Reverse Annealing

Lucas Joshua Menger, Thomas Lippert, Manpreet Singh Jattana

Quantum annealing is a promising heuristic for combinatorial optimization, but on current hardware its performance degrades for larger and more complex problems due to noise and small energy gaps. Reverse annealing has been proposed as a refinement strategy, yet it remains unclear when it provides systematic advantages over standard forward annealing or simply increasing annealing time. We find that combining forward and reverse annealing consistently improves solution quality and efficiency across multiple problem classes. The benefits of reverse annealing increase with problem complexity and are strongest in regimes where forward annealing is increasingly limited. Moreover, reverse annealing yields larger efficiency gains than simply extending forward annealing times. We establish these results through a systematic experimental study on a D-Wave Advantage system, benchmarking reverse annealing across Max-Cut, Number Partitioning, and sparse clustering problems while varying reverse distance, pause duration, and annealing time. We identify a narrow optimal regime for reverse annealing parameters linked to the location of freeze-out points and energy-level crossings in the annealing schedule. These findings demonstrate that reverse annealing is most valuable for large, high-complexity optimization problems and is likely to gain importance as quantum annealing hardware scales toward more realistic applications.

quant-pharXiv:2607.02146EPJ Quantum TechnologyJul 3, 20260 citations

On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization

Byron Tasseff, Tameem Albash, Zachary Morrell +4 more

Over the past decade, the usefulness of quantum annealing hardware for combinatorial optimization has been the subject of much debate. Thus far, experimental benchmarking studies have indicated that quantum annealing hardware does not provide an irrefutable performance gain over state-of-the-art optimization methods. However, as this hardware continues to evolve, each new iteration brings improved performance and warrants further benchmarking. To that end, this work conducts an optimization performance assessment of D-Wave Systems' most recent Advantage Performance Update computer, which can natively solve sparse unconstrained quadratic optimization problems with over 5,000 binary decision variables and 40,000 quadratic terms. We demonstrate that classes of contrived problems exist where this quantum annealer can provide run time benefits over a collection of established classical solution methods that represent the current state-of-the-art for benchmarking quantum annealing hardware. Although this work does not present strong evidence of an irrefutable performance benefit for this emerging optimization technology, it does exhibit encouraging progress, signaling the potential impacts on practical optimization tasks in the future.

arXiv:2210.04291Oct 9, 202217 citations

Early steps toward practical subsurface computations with quantum computing

Catherine McGeoch, Henri Calandra, France Amandeep +5 more

Quantum computing exploits quantum mechanics to perform certain computations more efficiently than classical computers. Current quantum computers have performed carefully tailored computational tasks that would be difficult or impossible for even the fastest supercomputers in the world. This “quantum supremacy” result demonstrates that quantum computing is more powerful than classical computing in some computational regimes. At present, it is unknown if any computational problems related to the Earth's subsurface fall within these regimes. Here, we describe an approach to performing seismic inverse analysis that combines a type of quantum computer called a quantum annealer with classical computing. This approach improves upon past work on applying quantum computing to the subsurface (via subsurface hydrology) in two ways. First, the seismic inverse problem enables better performance from the quantum annealer because of the Earth's relatively narrow distribution of P-wave velocities compared to the broad distribution of hydraulic conductivities. Second, we develop an iterative approach to quantum-computational inverse analysis, which works with a realistic set of observations. By contrast, the previous method used an inverse method that depended on an impractically dense set of observations. In combination, these two advances significantly narrow the gap a quantum-computational advantage for a practical subsurface geoscience problem. Closing the gap completely requires more work, but has the potential to dramatically accelerate inverse analyses for subsurface geoscience.

Aug 17, 20230 citations