Being immersed in the noisy intermediate-scale quantum (NISQ) era, current quantum annealers present limitations for solving optimization problems efficiently. To mitigate these limitations, D-Wave Systems developed a mechanism called reverse annealing, a specific type of quantum annealing designed to perform local refinement of good states found elsewhere. Despite the research activity around reverse annealing, no study has theorized about the possible benefits related to the transfer of knowledge under this paradigm. This work moves in that direction and is driven by experimentation focused on answering two key research questions: i) is reverse annealing a paradigm that can benefit from knowledge transfer between similar problems? and ii) can we infer the characteristics that an input solution should meet to help increase the probability of success? To properly guide the tests in this paper, the well-known knapsack problem has been chosen for benchmarking purposes, using a total of 34 instances composed of 14 and 16 items.
Being immersed in the noisy intermediate-scale quantum (NISQ) era, current quantum annealers present limitations for solving optimization problems efficiently. To mitigate these limitations, D-Wave Systems developed a mechanism called reverse annealing, a specific type of quantum annealing designed to perform local refinement of good states found elsewhere. Despite the research activity around reverse annealing, no study has theorized about the possible benefits related to the transfer of knowledge under this paradigm. This work moves in that direction and is driven by experimentation focused on answering two key research questions: i) is reverse annealing a paradigm that can benefit from knowledge transfer between similar problems? and ii) can we infer the characteristics that an input solution should meet to help increase the probability of success? To properly guide the tests in this paper, the well-known knapsack problem has been chosen for benchmarking purposes, using a total of 34 instances composed of 14 and 16 items.
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.
Advances in quantum annealing technology make it possible to obtain high quality approximate solutions of important NP-hard problems. With the newer generations of the D-Wave annealer, more advanced features are available which allow the user to have greater control of the anneal process. In this contribution, we study how such features can help in improving the quality of the solutions returned by the annealer. Specifically, we focus on two of these features: reverse annealing and h-gain. Reverse annealing (RA) was designed to allow refining a known solution by backward annealing from a classical state representing the solution to a mid-anneal point where a transverse field is present, followed by an ordinary forward anneal, which is hoped to improve on the previous solution. The h-gain (HG) feature stands for time-dependent gain in Hamiltonian linear (h) biases and was originally developed to help study freezeout times and phase transitions in spin glasses. Here we apply HG to bias the quantum state in the beginning of the annealing process towards the known solution as in the RA case, but using a different apparatus. We also investigate a hybrid reverse annealing/h-gain schedule, which has a backward phase resembling an RA step and whose forward phase uses the HG idea. To optimize the parameters of the schedules, we employ a Bayesian optimization framework. We test all techniques on a variety of input problems including the weighted Maximum Cut problem and the weighted Maximum Clique problem. Our results show that each technique may dominate the others depending on the input instance, and that the HG technique is a viable alternative to RA for some problems.
This thesis studies several aspects of the quantum annealing (QA) computing approach. Quantum annealers' primary objective is to solve hard computational optimization problems. Because these optimization problems are in the NP-Hard complexity class, they are of great interest in several fields. One of the leading open questions concerning quantum annealers asks whether they will outperform other classical methods for solving these problems; Some aspects of this question are addressed in this thesis. The first part of the thesis investigates whether quantum annealing provides improved performance for solving a particular family of NP problems, called the Quadratic Knapsack Problem (QKP), using the D-Wave Quantum Annealer. The performance metrics used to assess QKP solving are the solution quality and the total runtime, and are benchmarked against other classical solvers. \n \nFurthermore, we extend our research on quantum annealers to propose two use cases for such systems. One is for Blockchain technology, and the second is in the area of quantum chaos. For the first use case of QA, an application for Blockchain's Proof of Work (PoW) is proposed, based on having hard optimization problems as an alternative to PoW hashing challenge, and using quantum annealers as solvers. For the second use case of QA, we propose simulating quantum chaos on the D-Wave Quantum Annealer to study the transition between the deep quantum realm and the classical limit in a chaotic system, and obtain insights into the “quantumness" of quantum annealers.
Despite being considered as the next frontier in computation, Quantum Computing is still in an early stage of development. Indeed, current commercial quantum computers suffer from some critical restraints, such as noisy processes and a limited amount of qubits, among others, that affect the performance of quantum algorithms. Despite these limitations, researchers have devoted much effort to propose different frameworks for efficiently using these Noisy Intermediate-Scale Quantum (NISQ) devices. One of these procedures is D'WAVE Systems' quantum-annealer, which can be used to solve optimization problems by translating them into an energy minimization problem. In this context, this work is focused on providing useful insights and information into the behaviour of the quantum-annealer when addressing real-world combinatorial optimization problems. Our main motivation with this study is to open some quantum computing frontiers to non-expert stakeholders. To this end, we perform an extensive experimentation, in the form of a parameter sensitive analysis. This experimentation has been conducted using the Traveling Salesman Problem as benchmarking problem, and adopting two QUBOs: state-of-the-art and a heuristically generated. Our analysis has been performed on a single 7-noded instance, and it is based on more than 200 different parameter configurations, comprising more than 3700 unitary runs and 7 million of quantum reads. Thanks to this study, findings related to the energy distribution and most appropriate parameter settings have been obtained. Finally, an additional study has been performed, aiming to determine the efficiency of the heuristically built QUBO in further TSP instances.
Quantum annealing is a novel type of analog computation that aims to use quantum-mechanical fluctuations to search for optimal solutions for Ising problems. Quantum annealing in the transverse field Ising model, implemented on D-Wave devices, works by applying a time-dependent transverse field, which puts all qubits into a uniform state of superposition, and then applying a Hamiltonian over time, which describes a user-programed Ising problem. We present a method that utilizes two control features of D-Wave quantum annealers, namely reverse annealing and an h-gain schedule, to quantify the susceptibility, or the distance, between two classical states of an Ising problem. The starting state is encoded using reverse annealing, and the second state is encoded on the linear terms of a problem Hamiltonian. An h-gain schedule is specified, which incrementally increases the strength of the linear terms, thus allowing a quantification of the h-gain strength required to transition the anneal into a specific state at the final measurement. Because of the nature of quantum annealing, the state tends towards global minima, and therefore we restrict the second classical state to a minimum solution of the given Ising problem. This susceptibility mapping, when enumerated across all initial states, shows in detail the behavior of the quantum annealer during reverse annealing. The procedure is experimentally demonstrated on three small test Ising models which were embedded in parallel on the D-Wave Advantage_system4.1. Analysis of the state transition mapping shows detailed characteristics of the reverse annealing process, including intermediate state transition paths, which are visually represented as state transition networks.
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.