Simulated annealing (SA) has been considered as a good tool for searchand optimization problems which represent the abstraction of obtaining thecrystalline structure through a physical process. This algorithm works sequentiallythat the current state will produce only one next state. That will make the search tobe slower and the important drawback is that the search may fall in local minimumwhich represent the best solution in only part of the solution space. In this workwe present the transformation of Simulated Annealing algorithm into quantumversion which will be called Quantum Simulated Annealing (QSA). Thisalgorithm will overcome the drawbacks of slowness and local minimum falling byproduce as much as possible of the neighbor states and work on in parallel byexploiting the massive parallelism feature in quantum computation. The resultsshow that QSA can find the optimal path in smaller number of iterations than thesequential simulated annealing algorithm and the time complexity of QSA isbetter than any other parallel simulated annealing algorithm.
Simulated annealing (SA) has been considered as a good tool for searchand optimization problems which represent the abstraction of obtaining thecrystalline structure through a physical process. This algorithm works sequentiallythat the current state will produce only one next state. That will make the search tobe slower and the important drawback is that the search may fall in local minimumwhich represent the best solution in only part of the solution space. In this workwe present the transformation of Simulated Annealing algorithm into quantumversion which will be called Quantum Simulated Annealing (QSA). Thisalgorithm will overcome the drawbacks of slowness and local minimum falling byproduce as much as possible of the neighbor states and work on in parallel byexploiting the massive parallelism feature in quantum computation. The resultsshow that QSA can find the optimal path in smaller number of iterations than thesequential simulated annealing algorithm and the time complexity of QSA isbetter than any other parallel simulated annealing algorithm.
Simulated annealing (SA) is a widely used metaheuristic algorithm for solving optimization problems. However, its performance is often limited by the slow exploration of the search space. This paper explores the potential of accelerating simulated annealing using quantum computing. We propose a framework where the search space of SA is mapped to the quantum state space, leveraging quantum superposition and interference to expedite the search for the global optimum. The core claim is that quantum computation can significantly speed up the search process within simulated annealing. The mechanism relies on utilizing quantum algorithms to explore the solution space far more efficiently than classical methods. This work introduces a novel approach to optimization, demonstrating the potential of harnessing quantum mechanical phenomena to enhance the performance of classical optimization algorithms. The theoretical framework and conceptual design are presented, outlining a possible architecture for a quantum-accelerated simulated annealing system. The potential speedup is analyzed, and future research directions are discussed.
Quantum annealing (QA) algorithm is a new quantum optimization algorithm based on the classical simulated annealing (SA) algorithm. Unlike classical SA algorithm, which uses the thermal waves to search for the optimal solution, the QA algorithm uses the quantum tunneling effect to allow a quantum to penetrate a potential barrier with a higher energy than itself. Therefore, the algorithm can get rid of the local extreme values and is more likely to approach the global optimal with higher probability. In the literature, the QA algorithm has shown perfect optimization effects on combinatorial optimization problems. In this paper, the basic concepts and application fields of QA algorithm, which is the core principle of D-Wave quantum computer, are systematically reviewed. The applications of QA algorithm in cryptography, traveling salesman problem, graph coloring problem, and traffic path are discussed in detail. In addition, the direction of future research for QA algorithm is explored.
Combinatorial optimization problems are frequently classified as NP-hard, which means that the time needed to find the optimal solution generally increases exponentially with the problem size. However, the existing research gap highlights the necessity to develop combinatorial optimization methods capable of scaling to large problems while maintaining low solution latency. In this paper, we introduce stochastic simulated quantum annealing (SSQA) for fast solution of combinatorial optimization problems. SSQA is designed based on stochastic computing, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. It can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities. The time to solution of SSQA is 11.5 times and 423 times smaller than that of the conventional stochastic simulated annealing method and traditional SA, respectively, when solving a 2,025-node combinatorial optimization problem.
Quantum annealing is a generic algorithm using quantum-mechanical fluctuations to search for the solution of an optimization problem. The present paper first reviews the fundamentals of quantum annealing and then reports on preliminary results for an alternative method. The review part includes the relationship of quantum annealing with classical simulated annealing. We next propose a novel quantum algorithm which might be available for hard optimization problems by using a classical-quantum mapping as well as the Jarzynski equality introduced in nonequilibrium statistical physics.
This paper investigates the application of quantum annealing for solving complex combinatorial optimization problems. The core claim is that quantum annealing leverages its global search capabilities to efficiently address such problems. The proposed mechanism involves formulating the combinatorial optimization problem as a quantum annealing problem and utilizing the simulated annealing process within quantum annealing to conduct a search for the optimal solution. This research explores the potential of quantum annealing in practical applications, acknowledging that its application in combinatorial optimization is still in its exploratory phase. The algorithm is designed to minimize the energy of a system described by a Hamiltonian, which evolves over time according to the time-dependent Schrödinger equation. The core of the algorithm lies in mapping the problem's constraints and objective function into this Hamiltonian. The search process is governed by quantum fluctuations, represented by the operator H^, which encourages transitions to lower energy states, effectively navigating the solution space. The effectiveness of the algorithm is evaluated based on the quality of the solution found and the computational resources required. This work provides a foundational exploration of quantum annealing's potential within the field of combinatorial optimization.
In the field of combinatorial optimization (CO), quantum computing is increasingly recognized for its potential to provide groundbreaking solutions. However, embedding the problems into quantum circuits presents significant challenges due to the complexities of scaling to large dimensions and the constraints in qubit count and circuit depth.In this paper, we introduce a quantum neural simulated annealing (QNSA) framework, combining both simulated annealing (SA) in the classical domain and quantum neural networks (QNNs) in the quantum domain to address the computational challenges for large-scale problems. By employing an SA algorithm, we can explore the vast combination space of optimization problems. In addition, by incorporating QNNs with proposed adaptive embedding and observable, our approach extends beyond the standalone capabilities of quantum computing, leveraging the unique strengths of both quantum and classical computing paradigms. Our experimental results show that the QNSA framework significantly outperforms traditional classical computing methods, showcasing its potential for efficient problem-solving in complex scenarios.