Comparative study of the performance of quantum annealing and simulated annealing

Stéphane Louise

In this paper, we aim to compare Vector Annealing (VA), a quantum-inspired metaheuristic introduced by NEC, with other metaheuristics. For this comparison, we utilize Quantum Annealing (QA), as implemented by D-Wave, and the conventional Simulated Annealing (SA) as a reference point for the capabilities of classical hardware with classical algorithms. The applications used for performance evaluation are two important benchmark programs designed to assess quantum hardware. This comparison is relevant because, for benchmarking purposes, it is valuable to have reference points between classical and quantum computing. It is widely thought that quantum computers will take some time to reach the level of relevance currently held by classical computing. This research, focusing on the Q-Score benchmark and Maximum Cardinality Matching (MCM) problems -both part of the MetriQs/BACQ benchmarking initiative- demonstrates this point. Through this work, we also trace the evolution from VA 2.0 to VA 3.0. While VA 2.0 already showed a significant advantage over both QA and SA in constrained problems, VA 3.0 introduces substantial optimizations and overcomes previous limitations in unconstrained problems. This advancement highlights the potential of VA 3.0. Furthermore, this work paves the way for the comprehensive testing of VA within the context of the MetriQs/BACQ quantum benchmark, an application-oriented French benchmarking initiative for quantum computers.

秀稔 西森, Hidetoshi Nishimori

Hidetoshi Nishimori

Daryl P. Nazareth, J Spaans

Optimization methods are critical to radiation therapy. A new technology, quantum annealing (QA), employs novel hardware and software techniques to address various discrete optimization problems in many fields. We report on the first application of quantum annealing to the process of beamlet intensity optimization for IMRT. We apply recently-developed hardware which natively exploits quantum mechanical effects for improved optimization. The new algorithm, called QA, is most similar to simulated annealing, but relies on natural processes to directly minimize a system's free energy. A simple quantum system is slowly evolved into a classical system representing the objective function. If the evolution is sufficiently slow, there are probabilistic guarantees that a global minimum will be located. To apply QA to IMRT-type optimization, two prostate cases were considered. A reduced number of beamlets were employed, due to the current QA hardware limitations. The beamlet dose matrices were computed using CERR and an objective function was defined based on typical clinical constraints, including dose-volume objectives, which result in a complex non-convex search space. The objective function was discretized and the QA method was compared to two standard optimization methods, simulated annealing and Tabu search, run on a conventional computing cluster. Based on several runs, the average final objective function value achieved by the QA was 16.9 for the first patient, compared with 10.0 for Tabu and 6.7 for the simulated annealing (SA) method. For the second patient, the values were 70.7 for the QA, 120.0 for Tabu and 22.9 for the SA. The QA algorithm required 27-38% of the time required by the other two methods. In this first application of hardware-enabled QA to IMRT optimization, its performance is comparable to Tabu search, but less effective than the SA in terms of final objective function values. However, its speed was 3-4 times faster than the other two methods. This initial experiment suggests that more research into QA-based heuristics may offer significant speedup over conventional clinical optimization methods, as quantum annealing hardware scales to larger sizes.

Ameya Bhave, Ajinkya Borle

Quantum annealing is an emerging metaheuristic used for solving combinatorial optimisation problems. However, hardware based physical quantum annealers are primarily limited to a single vendor. As an alternative, we can discretise the quantum annealing process (discretised quantum annealing or DiQA) and use it on gate-model quantum computers. In this work, we first benchmark DiQA against simulated annealing for a similar number of steps. We then propose and evaluate a hybrid quantumclassical heuristic: Quantum Accelerated Simulated Annealing (QASA), where the traditional classical annealing procedure can be sped up with the use of (relatively) low depth DiQA circuits. This is done by (i) running a partial annealing scheme with a fraction of the depth of the complete circuit (ii) sampling the results from the circuit and fitting a Gibbs distribution on it and (iii) Using the inverse temperature of the Gibbs distribution and the best sample to initialise simulated annealing (SA). Our simulation results show QASA performing comparably to SA but for a reduced amount of steps.With the promising results of our work, we hope to generate interest for potential future work in the area of fixed-parameter quantum optimisation.

Matthias Troyer