Many combinatorial scientific computing problems are NP-hard which in practice requires using heuristics that either decompose a large-scale problem and solve many smaller local subproblems in parallel or iteratively improve the solution by local processing for sufficiently many steps to achieve a good quality/performance trade-off. These subproblems are NP-hard by themselves and the quality of their solution that depends on the subproblem size vitally affects the global solution of the entire problem. As we approach the physical limits predicted by Moore’s law, a variety of specialized combinatorial optimization hardware (such as adiabatic quantum computers, CMOS annealers, and optical parametric oscillators) is emerging to tackle specialized tasks in different domains. Many researchers anticipate that in the near future, these devices will be hybridized with high-performance computing systems to tackle large-scale problems which will open a door for the next breakthrough in performance of the combinatorial scientific computing algorithms. Most of these devices solve the Ising combinatorial optimization model that can represent many fundamental combinatorial scientific computing models. In this paper, we tackle the main challenges of problem size and precision limitation that the Ising hardware model typically suffers from. Although, our demonstration uses one of these novel devices, the models we propose can be generally used in any local search and refinement solvers that are broadly employed in combinatorial scientific computing algorithms.
Many combinatorial scientific computing problems are NP-hard which in practice requires using heuristics that either decompose a large-scale problem and solve many smaller local subproblems in parallel or iteratively improve the solution by local processing for sufficiently many steps to achieve a good quality/performance trade-off. These subproblems are NP-hard by themselves and the quality of their solution that depends on the subproblem size vitally affects the global solution of the entire problem. As we approach the physical limits predicted by Moore’s law, a variety of specialized combinatorial optimization hardware (such as adiabatic quantum computers, CMOS annealers, and optical parametric oscillators) is emerging to tackle specialized tasks in different domains. Many researchers anticipate that in the near future, these devices will be hybridized with high-performance computing systems to tackle large-scale problems which will open a door for the next breakthrough in performance of the combinatorial scientific computing algorithms. Most of these devices solve the Ising combinatorial optimization model that can represent many fundamental combinatorial scientific computing models. In this paper, we tackle the main challenges of problem size and precision limitation that the Ising hardware model typically suffers from. Although, our demonstration uses one of these novel devices, the models we propose can be generally used in any local search and refinement solvers that are broadly employed in combinatorial scientific computing algorithms.
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.
Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.
Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
The emergence of specialized optimization hardware such as CMOS annealers and adiabatic quantum computers carries the promise of solving hard combinatorial optimization problems more efficiently in hardware. Recent work has focused on formulating different combinatorial optimization problems as Ising models, the core mathematical abstraction used by a large number of these hardware platforms, and evaluating the performance of these models when solved on specialized hardware. An interesting area of application is data mining, where combinatorial optimization problems underlie many core tasks. In this work, we focus on consensus clustering (clustering aggregation), an important combinatorial problem that has received much attention over the last two decades. We present two Ising models for consensus clustering and evaluate them using the Fujitsu Digital Annealer, a quantum-inspired CMOS annealer. Our empirical evaluation shows that our approach outperforms existing techniques and is a promising direction for future research.
NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.