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.
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.
Quantum annealing is a computational paradigm in which optimisation problems are mapped onto the energy landscape of an interacting quantum system and explored through its dynamical evolution. By continuously transforming a simple initial Hamiltonian into one whose ground state encodes the solution, the system traverses a complex landscape via a combination of quantum fluctuations, tunnelling processes, and dissipative dynamics. Unlike gate-based quantum computing, quantum annealing is a specialised and near-term approach aimed primarily at discrete optimisation and sampling tasks. While it is not expected to provide polynomial-time solutions to NP-hard problems in the worst case, it offers a physically motivated heuristic for navigating rugged energy landscapes that arise across science and engineering. Modern quantum annealers realise programmable spin systems with thousands of qubits, placing them among the largest controllable quantum devices currently available. As a result, their significance extends beyond optimisation: they also function as experimental platforms for studying non-equilibrium many-body quantum dynamics in regimes that are difficult to access using classical simulation. In this review we present an accessible introduction to the principles of quantum annealing, describe the main hardware platforms and algorithmic techniques, and analyse how tunnelling, spectral gaps, and open-system effects shape computational performance. We survey applications ranging from optimisation and machine learning to quantum simulation and many-body physics, and discuss the central challenges in benchmarking, scaling, and control. These perspectives position quantum annealing as a distinctive framework at the interface of optimisation, stochastic sampling, and programmable quantum dynamics, with a role that is complementary to both classical algorithms and gate-based quantum computing.
Quantum annealers are specialized quantum computers for solving combinatorial optimization problems with special quantum computing characteristics, e.g., superposition and entanglement. Theoretically, quantum annealers can outperform classic computers. However, current quantum annealers are constrained by a limited number of qubits and cannot demonstrate quantum advantages. Nonetheless, research is needed to develop novel mechanisms to formulate combinatorial optimization problems for quantum annealing (QA). However, QA applications in software engineering remain unexplored. Thus, we propose BootQA , the very first effort at solving test case minimization (TCM) problems on classical software with QA. We provide a novel TCM formulation for QA and utilize bootstrap sampling to optimize the qubit usage. We also implemented our TCM formulation in three other optimization processes: simulated annealing (SA), QA without problem decomposition, and QA with an existing D-Wave problem decomposition strategy, and conducted an empirical evaluation with three real-world TCM datasets. Results show that BootQA outperforms QA without problem decomposition and QA with the existing decomposition strategy regarding effectiveness. Moreover, BootQA ’s effectiveness is similar to SA. Finally, BootQA has higher efficiency in terms of time when solving large TCM problems than the other three optimization processes.
Abstract Complete exploration of design spaces is often computationally prohibitive. Classical search methods offer a solution but are limited by challenges like local optima and an inability to traverse dislocated design spaces. Quantum computing (QC) offers a potential solution by leveraging quantum phenomena to achieve computational speed-ups. However, the practical capability of current QC platforms to deliver these advantages remains unclear. To investigate this, we apply and compare two quantum approaches – the Gate-Based Grover’s algorithm and quantum annealing (QA) – to a generic tile placement problem. We benchmark their performance on real quantum hardware (IBM and D-Wave, respectively) against a classical brute-force search. QA on D-Wave’s hardware successfully produced usable results, significantly outperforming a classical brute-force approach (0.137 s vs 14.8 s) at the largest scale tested. Conversely, Grover’s algorithm on IBM’s gate-based hardware was dominated by noise and failed to yield solutions. While successful, the QA results exhibited a hardware-induced bias, where equally optimal solutions were not returned with the same probability (coefficient of variation: 0.248–0.463). These findings suggest that for near-term engineering applications, QA shows more immediate promise than current gate-based systems. This study’s contribution is a direct comparison of two physically implemented quantum approaches, offering practical insights, reformulation examples and clear recommendations on the utilisation of QC in engineering design.
Abstract Quantum computers show potential for achieving computational advantage over classical computers, with many candidate applications in combinatorial optimisation. We present a focussed, application-level hardware case study of near-term quantum optimisation algorithms applied to a dense quadratic unconstrained binary optimisation (QUBO) materials science problem. To solve this problem, we implement two methods, the variational quantum eigensolver and quantum annealing (QA), on commercially-available gate-based and QA devices that are accessible via Quantum-Computing-as-a-Service (QCaaS) models. To analyse the performance of these algorithms on our chosen problem, we use a toolbox of relevant metrics and compare performance against three classical algorithms. We employ quantum methods to solve our fully-connected QUBO of up to 72 variables, and find that algorithm performance beyond this is restricted by device connectivity, noise and classical computation time overheads. The classical method—simulated annealing—demonstrates the best performance, exhibiting polynomial scaling on the tested problem sizes.
This paper investigates the application of the Quantum Annealing (QA) algorithm to solve complex optimization problems. The core claim is that simulating a complex optimization problem's local search process through the QA's annealing process can effectively locate global optimal solutions. The mechanism involves mapping the solution space of an optimization problem onto the annealing path of QA, controlling the annealing rate and path to guide the solution towards the optimal point. This research leverages QA's inherent ability to mimic physical annealing, aiming to enhance optimization efficiency and accuracy. We present a framework for formulating and applying QA to various complex problems, highlighting its potential advantages over traditional optimization methods. This work contributes to the growing field of quantum computing by demonstrating a practical approach to tackling challenging optimization tasks. The results suggest that QA can be a viable alternative for achieving superior performance in specific optimization scenarios.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.