We are interested in Quantum Annealing (QA), an algorithm inspired by quantum theory and Simulated Annealing (SA). It is based on quantum replicas, which explore an energy surface, and are less prone to be trapped in local minima. Moreover, kinetic energy helps replicas to find a global minimum. This method has proved its efficiency for several optimization problems. We start this study by presenting the application of QA to a new problem: the Multidimensional Knapsack Problem (MKP). We then present a new idea to speed up the quantum annealing process by detecting the resemblance between replicas. If many of the replicas exhibit the same properties, our assumption is that these properties will also be present with a high probability in a global solution. Consequently, the QA may restrict certain mutations in order to preserve those similarities. We call this algorithm Restrictive Quantum Annealing (RQA). We establish that RQA has better performances than QA and SA by carrying out an adequate analysis of the RQA performance, taking the Traveling Salesman Problem (TSP) and the above-mentioned MKP as references. We also advance guidelines indicating types of NP-hard problems for which our algorithm is particularly well adapted.
We are interested in Quantum Annealing (QA), an algorithm inspired by quantum theory and Simulated Annealing (SA). It is based on quantum replicas, which explore an energy surface, and are less prone to be trapped in local minima. Moreover, kinetic energy helps replicas to find a global minimum. This method has proved its efficiency for several optimization problems. We start this study by presenting the application of QA to a new problem: the Multidimensional Knapsack Problem (MKP). We then present a new idea to speed up the quantum annealing process by detecting the resemblance between replicas. If many of the replicas exhibit the same properties, our assumption is that these properties will also be present with a high probability in a global solution. Consequently, the QA may restrict certain mutations in order to preserve those similarities. We call this algorithm Restrictive Quantum Annealing (RQA). We establish that RQA has better performances than QA and SA by carrying out an adequate analysis of the RQA performance, taking the Traveling Salesman Problem (TSP) and the above-mentioned MKP as references. We also advance guidelines indicating types of NP-hard problems for which our algorithm is particularly well adapted.
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.
This paper explores the application of quantum annealing to solve combinatorial optimization problems. The core idea centers around mapping these problems onto a quantum annealing platform and utilizing the quantum effects to find optimal or near-optimal solutions. Specifically, we investigate the potential of improved parameter tuning and algorithmic modifications to enhance the effectiveness of quantum annealing for problems such as the Traveling Salesperson Problem (TSP) and the Knapsack Problem. While quantum annealing has shown promise, its practical performance remains limited, and this work aims to address this limitation through targeted algorithmic and parameter optimization. The central focus is on demonstrating a method for translating a classical combinatorial problem into a suitable form for quantum annealing, followed by a strategic approach to controlling the annealing process to guide the system toward a desired solution. The efficacy of this approach is evaluated conceptually, with a focus on outlining the necessary steps and considerations for successful implementation.
Simulated Annealing (SA) is often used to provide satisfactory solutions to solving combinatorial problems. However, the SA is limited by its tendency to get stuck in local minima, which often prevents the global optimal solution from being reached for large or very complex problems. To overcome this obstacle, we present a new method inspired by the properties of degenerate quantum systems, named Degenerate Quantum Simulated Annealing (SA-DQS). This innovative approach exploits the coexistence of several quantum states of the same energy; this multiplicity of states is advantageous because it allows to finding of several solutions with identical energies, thus increasing the chances of discovering and building a promising solution among them, and of getting out of the traps of local minima more efficiently. The traveling salesman problem (TSP) is used as an application benchmark to validate the effectiveness of SA-DQS. Compared to standard simulated annealing (SA-S), SA-DQS showed superior performance on multiple instances of TSP. On average, the solutions provided by SA-DQS are equal to or closer to the optimum known in TSPLIB, in addition, it also offers a shorter computation time compared to that of other heuristic methods.
Most of the modern day computations are considered as an NP-hard like solving a puzzle or traveling salesman problem. Over the decades, engineers are exploring for many approaches of solution, out of which Quantum Annealing has depicted the efficacy. In this paper, we do a review study of Quantum Annealing (i.e., an approach to find the global mini-mum of a particular function that can provide better heuristics for the NP-hard optimization problem) and discussed briefly about quantum computers. Not only that, we also showcase few applications of quantum annealing which include scheduling problem, lung cancer detection, coherence in quantum annealer, and clustering.
A primary challenge of computational science is solving NP-hard optimization problems since they are too complicated and cannot be effectively solved deterministically in large instances. Even though quantum computing can solve these problems with the help of its key properties quantum parallelism and tunneling, the modern hardware is yet not sufficiently developed. In this case, QICAs are considered as a new method in which the key aspects of quantum mechanics, such as superposition, entanglement, interference and tunneling are replicated in classical, non-quantum computers. It aims to attain rapid optimization of NP-hard problems through a hybrid approach that combines cartography-based exploration, variable state reduction with tensor networks as well as an inclusion of a variant-based approach inspired by QAOA. A number of standard problems are used to test the model, e.g., the Traveling Salesman Problem (TSP), the 0/1 Knapsack Problem and Max-Cut Problem. Genetic Algorithms, Simulated Annealing and Ant Colony Optimization trials all concur that QICA converges to superior solutions much faster and it can nonetheless handle bigger-sized problems. More precisely, the algorithm provides better approximation results as well as lesser computing power requirements, thus demonstrating the effectiveness of quantum-inspired methods in the case of classical systems. They establish the fact that QICAs have the potential to solve challenging optimization problems, particularly in the cases where quantum machines are absent or inaccessible. The way of solving the problem represented in the study is quite innovative and serves as a bridge between the theory of quantum and practical implementation in the optimization field.
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.