Algorithms for mitigating hardware restrictions in Ising machinesCombinatorial optimization problems is a category of problems which find the optimal combination of decision variables to minimize or maximize the objective function for given constraints.Ising machines, including quantum annealing machines and non-quantum type Ising machines, have attracted attention as accurate and efficient solvers for combinatorial optimization problems.However, the performance of Ising machines is limited because of hardware restrictions.This study proposes algorithms to overcome or mitigate these hardware restrictions and provide theoretical analysis of the algorithms.This thesis consists of five chapters.Chapter 1 introduces the research background and objectives.Chapter 2 presents basic knowledge, including methods to formulate combinatorial optimization problems in the Ising model, hardware restrictions, and internal algorithms such as Simulated Annealing (SA) and Quantum Annealing (QA), following the flow of solving combinatorial optimization problems with Ising machines.Chapter 3 describes a method to mitigate bit-width restriction.The study found a difference in the dynamical processes of the Ising model with SA before and after bit-width reduction.Thus, the SA parameters that align the dynamical processes of the reduced bit-width Ising model with the original Ising model, based on statistical mechanics analysis and these results.Chapter 4 describes a method to mitigate the problem size restrictions for quantum annealing machines.This study explains a hybrid optimization method that combines the larger problem size capability of non-quantum type Ising machines with the high-speed solution finding capability of quantum annealing machines.The performance of this hybrid method is evaluated using simulations with SA as the non-quantum type Ising machine and D-Wave Advantage as the quantum annealing machine.These simulations evaluate solution accuracy for problem sizes both feasible and infeasible for the quantum annealing machine, along with the parameter dependence of the hybrid method.In addition, simulations are performed with SA and QA using the master equation and the Schrödinger equation to evaluate the properties revealed by these simulations and the potential capabilities of the hybrid method.Chapter 5 describes the conclusions of this study and prospects.
Algorithms for mitigating hardware restrictions in Ising machinesCombinatorial optimization problems is a category of problems which find the optimal combination of decision variables to minimize or maximize the objective function for given constraints.Ising machines, including quantum annealing machines and non-quantum type Ising machines, have attracted attention as accurate and efficient solvers for combinatorial optimization problems.However, the performance of Ising machines is limited because of hardware restrictions.This study proposes algorithms to overcome or mitigate these hardware restrictions and provide theoretical analysis of the algorithms.This thesis consists of five chapters.Chapter 1 introduces the research background and objectives.Chapter 2 presents basic knowledge, including methods to formulate combinatorial optimization problems in the Ising model, hardware restrictions, and internal algorithms such as Simulated Annealing (SA) and Quantum Annealing (QA), following the flow of solving combinatorial optimization problems with Ising machines.Chapter 3 describes a method to mitigate bit-width restriction.The study found a difference in the dynamical processes of the Ising model with SA before and after bit-width reduction.Thus, the SA parameters that align the dynamical processes of the reduced bit-width Ising model with the original Ising model, based on statistical mechanics analysis and these results.Chapter 4 describes a method to mitigate the problem size restrictions for quantum annealing machines.This study explains a hybrid optimization method that combines the larger problem size capability of non-quantum type Ising machines with the high-speed solution finding capability of quantum annealing machines.The performance of this hybrid method is evaluated using simulations with SA as the non-quantum type Ising machine and D-Wave Advantage as the quantum annealing machine.These simulations evaluate solution accuracy for problem sizes both feasible and infeasible for the quantum annealing machine, along with the parameter dependence of the hybrid method.In addition, simulations are performed with SA and QA using the master equation and the Schrödinger equation to evaluate the properties revealed by these simulations and the potential capabilities of the hybrid method.Chapter 5 describes the conclusions of this study and prospects.
Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.
To enhance the performance of quantum annealing machines, several methods have been proposed to reduce the number of spins by fixing spin values through preprocessing. We proposed a hybrid optimization method that combines a simulated annealing (SA)-based non-quantum-type Ising machine with a quantum annealing machine. However, its applicability remains unclear. Therefore, we evaluated the performance of the hybrid method on large-size Ising models and analyzed its characteristics. The results indicate that the hybrid method improves upon solutions obtained by the preprocessing SA, even if the Ising models cannot be embedded in the quantum annealing machine. We analyzed the method from three perspectives: preprocessing, spin-fixed sub-Ising model generation method, and the accuracy of the quantum annealing machine. From the viewpoint of the minimum energy gap, we found that solving the sub-Ising model with a quantum annealing machine results in a higher solution accuracy than solving the original Ising model. Additionally, we demonstrated that the number of fixed spins and the accuracy of the quantum annealing machine affect the dependency of the solution accuracy on the sub-Ising model size.
Ising machines are expected to be dedicated computers that are capable of efficiently searching for good solutions to combinatorial optimization problems. When solving combinatorial optimization problems with an Ising machine, the objective function and constraints of the combinatorial optimization problems are expressed using the Ising model. Then, the low-energy states of the Ising model are searched by the internal algorithms of Ising machines. Typical internal algorithms are Simulated Annealing (SA) and Quantum Annealing (QA). Both algorithms exhibit stochastic behavior, so the final solution may contain errors. Therefore, it is an essential issue in the field of Ising machines to reduce errors as much as possible. A previous study proposed an error reduction method for QA machines, namely the Quantum Annealing Correction (QAC) model. This method reduces error by introducing penalty interaction and performing a specific decoding method. Building on these valuable insights, we proposed an alternative error reduction method, the stacked model. To verify the effectiveness, we examined on the relationship between the penalty interaction and the success probability of the QAC model and the stacked model on SA. The obtained results differ from the facts observed in QA. In summary, a decoding method different from the one considered effective in QA was found to be effective in SA. This result suggests that when considering an appropriate error reduction method, it is necessary to consider the internal algorithm of the Ising machine.
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 is the problem of minimizing the energy function among many combinations of variables, which is often difficult to solve with conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. Among various methods for solving such problems using Ising machines, one prominent approach is the three-stage annealing method. The approach effectively solves a combinatorial optimization problem, utilizing an initial solution, but it performs the annealing process only once. Repeating the annealing process several times may enhance the solution more efficiently. In this paper, we propose a novel hybrid iterative annealing method that consists of an initial process using a classical computer, an annealing process using a quantum annealer, and a correction process/selection process using a classical computer. The proposed method repeats the annealing process and the correction process/selection process until the solution is sufficiently converged. In the experimental evaluations through the three types of typical combinatorial optimization problems, the proposed method shows improvements by up to 54.0% compared to the three-stage annealing method.