Combinatorial optimization is a mathematical basis for solving many practical tasks. Quantum annealing offers an efficient hardware platform, specialized for solving such problems. The aim of this work is to reduce the scalability complexities faced in solving large size optimization problems. We propose an algorithm of splitting high dimensional problems into subproblems and solve each problem, including interaction energy between them individually. Furthermore, we calculate the combined energy of the system by using the optimal spin configuration obtained from the solution of subproblems and compare this energy with energy obtained from conventional full system approach. Our splitting approach performs better in both time and computational resources. We verify the proposed approach by comparing numerical simulations obtained by solving random Ising Hamiltonians of different dimensions. This splitting method is crucial for finding optimal solutions especially for large optimization problem in less computational time and memory.
Combinatorial optimization is a mathematical basis for solving many practical tasks. Quantum annealing offers an efficient hardware platform, specialized for solving such problems. The aim of this work is to reduce the scalability complexities faced in solving large size optimization problems. We propose an algorithm of splitting high dimensional problems into subproblems and solve each problem, including interaction energy between them individually. Furthermore, we calculate the combined energy of the system by using the optimal spin configuration obtained from the solution of subproblems and compare this energy with energy obtained from conventional full system approach. Our splitting approach performs better in both time and computational resources. We verify the proposed approach by comparing numerical simulations obtained by solving random Ising Hamiltonians of different dimensions. This splitting method is crucial for finding optimal solutions especially for large optimization problem in less computational time and memory.
The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.
This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem.\nIn order to realize a smart society, optimization of people and thingssuch as transportation networks, power networks, human resource allocationand routes is indispensable. Many of these problems are called combinatorial optimization problems and are known as very important problems in modern society. However, it is known that the combinatorial optimization problem is NP-hard and it is difficult to efficiently solve it with a conventional Neumann computer.\nIn recent years, the miniaturization of the process of manufacturing computer chips is approaching the physical limit. Therefore, especially in the solution by the full search, the improvement in speed due to the calculation speed of the computer cannot be expected. From such a background, dedicated hardware capable of solving a combination optimization problem at high speed and with low power consumption has been attracting attention.\nThe annealing processor is a general-purpose combination optimization solver that utilizes the property that the ground state of the optimization problem expressed by using the Ising model and the optimal solution of the combination optimization problem match. The Ising model is a ferromagnetic model in statistical physics expressed by spins having an upward and downward state, spin-spin interactions occurring between the spins, and an external magnetic field acting on each spin. The Ising model can express a combinatorial optimization problem by expressing a control target and a cost using these parameters. The annealing processor updates the spin state while slowly lowering the temperature parameters based on simulated annealing,which is an optimization method learned from natural phenomena generally called annealing. Eventually, the spin will reach the ground state with a high probability and obtain the optimal solution.\nAnnealing processors are classified into two types, the nearest neighbor type and the fully connected type, depending on the shape of the Ising model simulated on the hardware. In the nearest neighbor type, the coupling between spins is limited to only between adjacent spins, and in the full coupling type, coupling exists between arbitrary spins. The nearest neighbor type realizes high parallel processing by reducing the data spin required by simulated annealing by reducing the proximity spin. In addition, since data transfer is limited to adjacent spins, the scalability is high. However, since the spin-to-spin interaction is sparse, there is a problem that the class of combinatorial optimization problems that can be dealt with is limited, or that the problem requires deformation processing to match the Ising model of hardware. The fully connected type can solve any class of problems as long as the number of spins permits, however it requires connections between arbitrary spins.Therefore, scalability is low. Because there there is a dependency on all spins,the number of spins that can be updated at one time is always limited to only one regardless of the total number of spins. Therefore, it takes time to converge to the ground state.\nIn this research, we propose a method of increasing the number of spins for this annealing processor by using (1) a spatially-expanded time-division processing mechanism architecture based on a loosely-coupled type, (2) An algorithm for applying a fully coupled Ising network to a more complex Ising network using the nearest neighbor Ising network and an annealing method that can be updated in parallel, (3)We conducted a study on the architecture of a fully coupled annealing processor for parallel updating annealing.\nAs described above, the research described in this paper contributes to the improvement of the efficiency of the annealing processor for solving the large-scale combinatorial optimization problem from both the fundamental algorithm and the hardware architecture. I hope that this research will solve the combinatorial optimization problem that is expected to increase in demand in the future and contribute to the development of human society.
Annealing machines such as quantum annealing machines and semiconductor-based annealing machines have been attracting attention as an efficient computing alternative for solving combinatorial optimization problems. They solve original combinatorial optimization problems by transforming them into a data structure called an Ising model. At that time, the bit-widths of the coefficients of the Ising model have to be kept within the range that an annealing machine can deal with. However, by reducing the Ising-model bit-widths, its minimum energy state, or ground state, may become different from that of the original one, and hence the targeted combinatorial optimization problem cannot be well solved. This paper proposes an effective method for reducing Ising model's bit-widths. The proposed method is composed of two processes: First, given an Ising model with large coefficient bit-widths, the shift method is applied to reduce its bit-widths roughly. Second, the spin-adding method is applied to further reduce its bit-widths to those that annealing machines can deal with. Without adding too many extra spins, we efficiently reduce the coefficient bit-widths of the original Ising model. Furthermore, the ground state before and after reducing the coefficient bit-widths is not much changed in most of the practical cases. Experimental evaluations demonstrate the effectiveness of the proposed method, compared to existing methods.
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 annealing is a promising algorithm for solving combinatorial optimization problems. However, various hardware restrictions significantly impede its efficient performance. Size-reduction methods provide an effective approach to addressing large-scale problems but often introduce additional difficulties. A notable hardware restriction is that quantum annealing can handle only a limited number of decision variables, compared to the size of the problem. Moreover, when employing size-reduction methods, the interactions and local magnetic fields in the Ising model — used to represent the combinatorial optimization problem — can become excessively large, making them difficult to implement on hardware. Although prior studies suggest that energy rescaling impacts the performance of quantum annealing, its interplay with size-reduction methods remains unexplored. This study examines the relationship between fixing spins, a promising size-reduction method, and the effects of energy rescaling. Numerical simulations and experiments conducted on a quantum annealer demonstrate that the fixing spins method enhances quantum annealing performance while preserving the spin-chain embedding for a homogeneous, fully connected ferromagnetic Ising model.
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.