This paper introduces the Rerandomization technique of simulated stochastic quantum annealing (SSQA), which enables the solution of large-scale combinatorial optimization problems. Rerandomization is a technique that explores a wider solution space by resetting the spin states, and it shows excellent performance for large-scale problems when executed at the optimal timing. The optimal timing can be predicted using mathematical equations. The adoption of the predicted rerandomization timing is demonstrated to significantly improve the accuracy from 42% (without rerandomization) to 100% in the graph isomorphism problem, a common large-scale combinatorial optimization problem with a size of 2,500 bits. Furthermore, the proposed method shows to solve problems of four times the size at the same speed as traditional SA.
This paper introduces the Rerandomization technique of simulated stochastic quantum annealing (SSQA), which enables the solution of large-scale combinatorial optimization problems. Rerandomization is a technique that explores a wider solution space by resetting the spin states, and it shows excellent performance for large-scale problems when executed at the optimal timing. The optimal timing can be predicted using mathematical equations. The adoption of the predicted rerandomization timing is demonstrated to significantly improve the accuracy from 42% (without rerandomization) to 100% in the graph isomorphism problem, a common large-scale combinatorial optimization problem with a size of 2,500 bits. Furthermore, the proposed method shows to solve problems of four times the size at the same speed as traditional SA.
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 (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.
This paper investigates the application of quantum annealing for the combinatorial optimization challenges inherent in large-scale simulations. We demonstrate that classical algorithms frequently encounter significant computational bottlenecks when tackling complex problems such as molecular dynamics simulations, materials design, and financial modeling. Quantum annealing, leveraging quantum tunneling, offers a potential paradigm shift by providing a mechanism for directly mapping these optimization problems onto quantum hardware and exploring the solution space with enhanced efficiency. This work presents a theoretical framework outlining the approach and discusses the core principles underlying its implementation. The focus is on the potential to accelerate computationally intensive simulations, addressing a critical limitation in current simulation methodologies. We explore the challenges and opportunities associated with this emerging technology, emphasizing its role in overcoming the limitations of classical optimization techniques. The primary goal is to provide a foundational understanding of how quantum annealing can be strategically applied to significantly improve the speed and accuracy of large-scale simulations.
Abstract Two classes of quantum-annealing-inspired-algorithms (QAIA), namely different variants of simulated coherent Ising machine and simulated bifurcation, have been proposed for efficiently solving combinatorial optimization problems recently. In order to certify the superiority of these algorithms, standardized comparisons among them and against other physics-based algorithms are necessary. In this work, for Max-Cut problems up to 20,000 nodes, we benchmark QAIA against quantum annealing and other physics-based algorithms. We found that ballistic simulated bifurcation excelled for chimera and small-scale graphs, achieving nearly a 50-fold reduction in time-to-solution compared to quantum annealing. For large-scale graphs, discrete simulated bifurcation achieves the lowest time-to-target and outperforms D-Wave Advantage system when tasked with finding the maximum cut value in pegasus graphs. Our results suggest that QAIA represents a promising means for solving combinatorial optimization problems in practice, and can act as a natural baseline for competing quantum algorithms.
It is well-known that quantum annealing (QA) is an excellent algorithm for solving combinatorial optimization problems (COPs). However, its hardware implementation poses challenges, requiring quantum devices. Therefore, a quantum Monte Carlo (QMC) method-based annealing approach called Simulated Quantum Annealing (SQA), which aims to emulate quantum annealing using classical computers, has been proposed. In the demo-night session, we will demonstrate a SQA based on stochastic computing (SC) on a standard FPGA board, called “PYNQ”. The use of SC-based data representation, along with the realization of SC-based spin-gate circuits, makes it possible to drastically reduce hardware costs compared to QA. This enhances the suitability for extending large-scale COPs.
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.