Ising machines are a promising approach to solve combinatorial optimization problems. They map these problems onto the Ising model and search for low-energy configurations. However, navigating the rugged energy landscapes of these systems remains difficult. To improve this navigation, classical adiabatic annealing has been proposed in the literature as a heuristic optimization method for classical Ising machines. Using this technique, the Hamiltonian of the Ising machine is gradually transformed from an easily solvable Hamiltonian to the target Hamiltonian. However, its purported effectiveness is primarily motivated by an analogy to quantum adiabatic annealing, and systematic benchmarking has remained limited.
In this work, we analyze the classical adiabatic annealing technique using continuation methods. Motivated by insights from this analysis, we propose an optimized annealing strategy we refer to as hybrid classical adiabatic annealing. We benchmark our proposed strategy using MaxCut instances with up to 800 spins and problems with external fields, for which it achieves a marginal improvement for a limited set of problems. We conclude that, although theoretically motivated and occasionally beneficial, the hybrid strategy does not offer a sufficient practical advantage over simpler, existing techniques.
Ising machines are a promising approach to solve combinatorial optimization problems. They map these problems onto the Ising model and search for low-energy configurations. However, navigating the rugged energy landscapes of these systems remains difficult. To improve this navigation, classical adiabatic annealing has been proposed in the literature as a heuristic optimization method for classical Ising machines. Using this technique, the Hamiltonian of the Ising machine is gradually transformed from an easily solvable Hamiltonian to the target Hamiltonian. However, its purported effectiveness is primarily motivated by an analogy to quantum adiabatic annealing, and systematic benchmarking has remained limited.
In this work, we analyze the classical adiabatic annealing technique using continuation methods. Motivated by insights from this analysis, we propose an optimized annealing strategy we refer to as hybrid classical adiabatic annealing. We benchmark our proposed strategy using MaxCut instances with up to 800 spins and problems with external fields, for which it achieves a marginal improvement for a limited set of problems. We conclude that, although theoretically motivated and occasionally beneficial, the hybrid strategy does not offer a sufficient practical advantage over simpler, existing techniques.
A combinatorial optimization problem is the problem of minimizing the energy function among many combinations of variables, which is often difficult to solve with conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. Among various methods for solving such problems using Ising machines, one prominent approach is the three-stage annealing method. The approach effectively solves a combinatorial optimization problem, utilizing an initial solution, but it performs the annealing process only once. Repeating the annealing process several times may enhance the solution more efficiently. In this paper, we propose a novel hybrid iterative annealing method that consists of an initial process using a classical computer, an annealing process using a quantum annealer, and a correction process/selection process using a classical computer. The proposed method repeats the annealing process and the correction process/selection process until the solution is sufficiently converged. In the experimental evaluations through the three types of typical combinatorial optimization problems, the proposed method shows improvements by up to 54.0% compared to the three-stage annealing method.
A combinatorial optimization problem is the problem of minimizing the energy function among many combinations of variables, which is often difficult to solve with conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. Among various methods for solving such problems using Ising machines, one prominent approach is the three-stage annealing method. The approach effectively solves a combinatorial optimization problem, utilizing an initial solution, but it performs the annealing process only once. Repeating the annealing process several times may enhance the solution more efficiently. In this paper, we propose a novel hybrid iterative annealing method that consists of an initial process using a classical computer, an annealing process using a quantum annealer, and a correction process/selection process using a classical computer. The proposed method repeats the annealing process and the correction process/selection process until the solution is sufficiently converged. In the experimental evaluations through the two types of typical combinatorial optimization problems, the proposed method shows improvements by up to 50.5% compared to the three-stage annealing method.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.
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.
Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.
Combinatorial optimization is a foundation of numerous scientific, industrial, and social decision-making questions, but its usefulness is mostly restricted by the exponential complexity of the problem of classical computability. The quantum annealing (QA) has become one of the leading analogue quantum systems to address such problems, whereby optimization problems are converted into physical energy structures and quantum fluctuations are utilized to perform systematic exploration. It provides a critical, synthesized, and comprehensive review of quantum annealing as applied to combinatorial optimization, including the theoretical basis, hardware designs, algorithm methods, issues of embedding and encoding, benchmarking procedures, applications, and integration with quantum algorithms based on gates and solvers on a classical computer. We build a comprehensive taxonomy between adiabatic dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to state-of-the-art flux-qubit annealers, new architectures, and hybrid quantum classical pipelines. We show that the overhead of embedding and encoding and the benchmarking approach taken are the most significant factors in determining scalability and performance, but not the raw number of qubits. Transportation, energy systems, robotics, finance, pharmacological discovery, and machine learning are just some examples of the domain-specific case studies that use QA with minimal empirical utility as a hybrid refinement engine and not an independent solver. Moreover, we introduce a stringent evaluation of the existing benchmarking culture, clarify the causal links between QA and QAOA as well as between VQE and structural predicaments, and reveal the institutional roots of the existing restrictions. We conclude by identifying a research roadmap in the future, focusing on the annealing hardness characterization, Stoquastic control manipulation, embedding rules automation, architecture design, and development of principled quantum advantage. It creates a benchmark reference to those in the field and research and deployment of scalable, reliable, and application-relevant quantum optimization