Quantum Annealing Algorithms: State of the Art

Alfonso de la Fuente Ruiz

Brief description on the state of the art of some local optimization methods: Quantum annealing Quantum annealing (also known as alloy, crystallization or tempering) is analogous to simulated annealing but in substitution of thermal activation by quantum tunneling. The class of algorithmic methods for quantum annealing (dubbed: 'QA'), sometimes referred by the italian school as Quantum Stochastic Optimization ('QSO'), is a promising metaheuristic tool for solving local search problems in multivariable optimization contexts.

E. Arvidsson

Arnab Das, Bikas K. Chakrabarti

Hugo Da Silva Araujo, Xinyi Wang, Mohammadreza Ahmadi Mousavi +1 more

Quantum computing offers the potential to address complex computational challenges, particularly in areas such as simulation and optimisation. Despite this promise, current gate-based quantum devices remain limited in scale and reliability, constraining their practical use. In this context, quantum annealing (QA) emerges as a viable and currently accessible alternative for solving optimisation problems, as it employs adiabatic quantum evolution to efficiently explore large and complex search spaces. This makes it a natural candidate for search-based software testing in the Cyber-Physical Systems (CPS) domain, which demands effective test cases due to their complexity and combination of continuous and discrete domains. This work explores the use of quantum annealing to enhance test case generation for CPS through a mutation-based approach. We employ quantum annealing to identify areas on test cases that can be improved and apply mutations to those areas. We encode test case mutation as a binary optimisation problem, and use quantum annealing to identify and target critical regions of the test cases for improvement. Our approach mechanises this process into an algorithm that uses D-Wave’s quantum annealer to find the solution. As a main contribution, we offer insights into how quantum annealing can advance testing methodologies by empirically evaluating the correlation between problem size, hardware limitations, and the effectiveness of the results. Moreover, we compare the proposed method against state-of-the-art classical optimisation algorithms, targeting efficiency (time to generate test cases) and effectiveness (fault detection rates). Our results indicate that quantum annealing may enable faster test case generation (when problem decomposition, sampling and scheduling strategies are applied) while achieving comparable fault detection performance to state-of-the-art alternatives.

Helmut G. Katzgraber, Firas Hamze, Zhu, Zheng +2 more

There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a "`quantum advantage" over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.

Shu Tanaka