In the noisy intermediate-scale quantum (NISQ) era, annealing-based computing is emerging as a new type of high-performance computing (HPC) technology for solving computationally intractable combinatorial optimization problems (COPs). Inspired by thermal annealing in metallurgy, the cost function of a COP is encoded in an energy function (Hamiltonian), with its lowest energy state being searched using an annealer and finally transformed to the global or global approximate optimal solution to a target problem. We address the key technology underlying annealing-based methods along with an experimental study with a commercial digital annealer (DA). We hope to shed light on how industries could benefit from this emerging computing technology to explore the challenges and opportunities in the quantum computing age.
In the noisy intermediate-scale quantum (NISQ) era, annealing-based computing is emerging as a new type of high-performance computing (HPC) technology for solving computationally intractable combinatorial optimization problems (COPs). Inspired by thermal annealing in metallurgy, the cost function of a COP is encoded in an energy function (Hamiltonian), with its lowest energy state being searched using an annealer and finally transformed to the global or global approximate optimal solution to a target problem. We address the key technology underlying annealing-based methods along with an experimental study with a commercial digital annealer (DA). We hope to shed light on how industries could benefit from this emerging computing technology to explore the challenges and opportunities in the quantum computing age.
A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing (SA) and QA method from each study.
Quantum computing is an important developing technology with the potential to revolutionise the landscape of scientific and business problems that can be practically addressed. The widespread excitement derives from the potential for a fault tolerant quantum computer to solve previously intractable problems. Such a machine is not expected to be available until 2030 at least. Thus we are currently in the so-called NISQ era where more heuristic quantum approaches are being applied to early versions of quantum hardware. In this paper we seek to provide a more accessible explanation of many of the more technical aspects of quantum computing in the current NISQ era exploring the 2 main hybrid classical-quantum algorithms, QAOA and VQE, as well as quantum annealing. We apply these methods, to an example of combinatorial optimisation in the form of a facilities location problem. Methods explored include the applications of different types of mixer (X, XY and a novel 3XY mixer) within QAOA as well as the effects of many settings for important meta parameters, which are often not focused on in research papers. Similarly, we explore alternative parameter settings in the context of quantum annealing. Our research confirms the broad consensus that quantum gate hardware will need to be much more capable than is available currently in terms of scale and fidelity to be able to address such problems at a commercially valuable level. Quantum annealing is closer to offering quantum advantage but will also need to achieve a significant step up in scale and connectivity to address optimisation problems where classical solutions are sub-optimal.
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.
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.
In 2017, John Preskill defined Noisy Intermediate Scale Quantum (NISQ) computers as an intermediate step on the road to large scale error corrected fault-tolerant quantum computers (FTQC). The NISQ regime corresponds to noisy qubit quantum computers with the potential to solve actual problems of some commercial value faster than conventional supercomputers, or consuming less energy. Over five years on, it is a good time to review the situation. While rapid progress is being made with quantum hardware and algorithms, and many recent experimental demonstrations, no one has yet successfully implemented a use case matching the original definition of the NISQ regime. This paper investigates the space, fidelity and time resources of various NISQ algorithms and highlights several contradictions between NISQ requirements and actual as well as future quantum hardware capabilities. It then covers various techniques which could help like qubit fidelities improvements, various breeds of quantum error mitigation methods, analog/digital hybridization, using specific qubit types like multimode photons as well as quantum annealers and analog quantum computers (aka quantum simulators or programmable Hamiltonian simulators) which seem closer to delivering useful applications although they have their own mid to longer-term scalability challenges. Given all the constraints of these various solutions, it seems possible to expect some practical use cases for NISQ systems, but with a very narrow window before various scaling issues show up. Turning to the future, a scenario can be envisioned where NISQ will not necessarily be an intermediate step on the road to FTQC. Instead, the two may develop along different paths, due to their different requirements. This leaves open a key question on the trade-offs that may be necessary to make between qubit scale and qubit fidelities in future quantum computers designs.
Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000Qquantum hardware demonstrate that the optimal solutions for several instances can be attained.