Simulated annealing using quantum-inspired algorithms

Kedem, Eleanor

Simulated annealing using quantum-inspired algorithms

Thesis / Dissertation

2026

Publisher

University of Cape Town

Department

Department of Computer Science

Faculty

Faculty of Science

Abstract

Combinatorial optimisation is an area of research that has applications in nearly all areas of society. Such problems involve searching for an optimal solution in a finite range of potential candidates, with optimisation standardly being achieved through the approximation of the optimal solution. These problems are generally considered di”cult to solve. One optimisation method is simulated annealing, a metaheuristic that slowly modifies a single solution space until the local optimum is located. Recently, quantum annealing algorithms were implemented in hardware by companies such as D-Wave and NEC. These are based on quantum annealing algorithms, which evolve a multi quantum bit quantum state using an operator that evolves slowly enough over time, so as to allow the state to continuously remain in its lowest energy state, with its final lowest energy state representing the optimum. Quantum annealers have shown great promise and, in some instances, have demonstrated significant speed-ups for specific types of optimisation problems. However, despite their potential, quantum annealers are still restricted by current technology. Quantum-inspired annealing is a class of algorithms that simulate the dynamical evolution of physical systems on classical computers, drawing principles from quantum mechanics. This method could be implemented either via hardware or by using di!erent machine learning algorithms. According to the No Free Lunch Theorem, there is no universally optimal algorithm for all optimisation problems, and each algorithm performs well only within specific problem contexts. This work aimed to systematise and clarify the growing field of quantum-inspired annealing research. This study focused on benchmarking four optimisation algorithms: classical simulated annealing and three quantum-inspired annealing algorithms. These algorithms were tested on two distinct combinatorial optimisation problems: the Travelling Salesman Problem (TSP) and the Quadratic Unconstrained Binary Optimisation (QUBO) problem. The research aimed to assess each algorithm's performance in terms of accuracy, computational complexity, and resource e”ciency on five di!erent datasets. The results demonstrated that, while each algorithm has unique advantages, quantum-inspired algorithms performed competitively with classical simulated annealing, highlighting their potential for optimising complex systems on classical hardware.

Keywords

optimisation

algorithms

Reference:

Collections

Masters

Full item page