Abstract Quantum annealing promises to solve complex combinatorial optimization problems faster than current transistor-based computer technologies. Although to date only one commercially-available quantum annealer is procurable, one can already start to map out the application scope of these novel optimization machines. These mid-scale programmable analog special-purpose devices could, potentially, revolutionize optimization. However, their disruptive application domain remains to be found. While the commercial analog quantum optimization machine by D-Wave Systems Inc. already exceeds 1000 qubits, here it is argued that maybe smaller devices with better quality qubits, higher connectivity, and more tunability might be better suited to answer if quantum annealing will ever truly outperform specialized silicon technology combined with efficient heuristics for optimization and sampling applications.
Abstract Quantum annealing promises to solve complex combinatorial optimization problems faster than current transistor-based computer technologies. Although to date only one commercially-available quantum annealer is procurable, one can already start to map out the application scope of these novel optimization machines. These mid-scale programmable analog special-purpose devices could, potentially, revolutionize optimization. However, their disruptive application domain remains to be found. While the commercial analog quantum optimization machine by D-Wave Systems Inc. already exceeds 1000 qubits, here it is argued that maybe smaller devices with better quality qubits, higher connectivity, and more tunability might be better suited to answer if quantum annealing will ever truly outperform specialized silicon technology combined with efficient heuristics for optimization and sampling applications.
This paper investigates the possibility of using an analog quantum computer as commercialized by D-Wave to solve large QUBO problems by means of a single invocation of the quantum annealer. Indeed this machine solves a spin glass problem with programmable coefficients but subject to quite strong topology restrictions on the set of non-zero coefficients. Rather than mapping problem variables onto multiple qbits, an approach which requires many invocations of the annealer to solve small size problems, it is tempting to investigate the existence of sparse relaxations compliant with the qbits interconnection topology of the machine, hence solvable in one invocation of the annealing oracle, but still providing good-quality solutions to the original problem. This paper provides an experimental setup which aims to determine whether or not such convenient relaxations do exist or, rather, are easy to find. Our experiments suggest that it is not the case and, therefore, that solving even moderate size arbitrary problems with a single call to a quantum annealer is not possible at least within the constraints of the so-called Chimera topology. We conclude the paper with a number of perspectives that this results imply on the design of heuristics taking profit of a quantum annealing oracle to solve large scale problems.
Quantum computing has emerged as a promising computational paradigm with the potential to solve problems that are intractable for classical computers. This paper provides an overview of the current state of quantum computing, including its historical development, hardware advancements, applications, and challenges. Special attention is given to combinatorial optimization, which is considered one of the most promising application domains. The limitations of current quantum systems and future research directions are also discussed. This paper presents a comparative study between a conventional D-Wave-based simulated annealing approach and a proposed hybrid optimization model for solving largescale combinatorial optimization problems. The study focuses on benchmark problems, including AES, TSP gr24, and a real-world load balancing problem, all formulated as QUBO models. The D-Wave approach employs the dwave-neal simulated annealing engine with various parameter settings, while the proposed model introduces a decomposition-based framework combined with adaptive parameter control and iterative refinement. The experimental results demonstrate that the proposed model consistently outperforms the conventional approach in terms of solution quality, achieving significantly lower energy values across all problem instances. In particular, for the TSP gr24 problem, the proposed model achieves near-optimal solutions with substantially reduced computation time. For large-scale problems such as AES and load balancing, the proposed model maintains scalability and robustness, whereas the conventional approach suffers from increased computational cost and performance degradation. Although the proposed method introduces additional computational steps, its hybrid structure effectively mitigates limitations related to local minima, parameter sensitivity, and scalability. These findings indicate that integrating classical optimization techniques with quantum-inspired methods is essential for practical applications. The proposed model provides a promising framework for solving complex real-world optimization problems and highlights the importance of hybrid approaches in advancing quantum annealing technologies.
The quantum annealing technique is such a paradigm that is next generation that can be used in solving optimization problem across different scientific domains like finance and material science and is capable of breaking through past obstacles to generate solutions for problems waiting to be solved. The purpose of this paper is the detailed depiction of the application of the quantum annealing in the optimization that includes the principles, applications, methodologies and outcomes and future trends all of them. Through a multidisciplinary approach, we examine the use of quantum annealing, as the method that exploits the specific features of the quantum annealing through the quantum mechanics, to explore the multitude of solution spaces faster and better than the classical methods, leading to the superior solution quality and the faster computing times. Next, we give examples for its implementation in Portfolio optimization, Machine learning, chemical optimization, Traffic management and so on depicting its role in delivering tangible benefits such as higher financial returns, precision improvement, and time savings contrast to the classical methods. Therefore, we also emphasize the current impediments, such as the scaling down the size and the ethical aspect, through which we give the way forward for the subsequent scientific researches and studies. In this abstract, we aim to depict the helix-like nature of quantum annealing in the revolution of optimization, bringing in innovations, and thus, shaping the future in which it is the quantum computing technologies that hold the central stage in addressing the complex interconnecting real-world issues.
Quantum annealing (QA) is a heuristic quantum optimization algorithm that can be used to solve combinatorial optimization problems. In recent years, advances in quantum technologies have enabled the development of small- and intermediate-scale quantum processors that implement the QA algorithm for programmable use. Specifically, QA processors produced by D-Wave systems have been studied and tested extensively in both research and industrial settings across different disciplines. In this paper we provide a literature review of the theoretical motivations for QA as a heuristic quantum optimization algorithm, the software and hardware that is required to use such quantum processors, and the state-of-the-art applications and proofs-of-concepts that have been demonstrated using them. The goal of our review is to provide a centralized and condensed source regarding applications of QA technology. We identify the advantages, limitations, and potential of QA for both researchers and practitioners from various fields.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a "`quantum advantage" over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.