Combinatorial optimization problems represent a wide range of real-world scenarios where complicated interactions make it difficult to find the best solution. One example is the quadratic assignment problem (QAP), which involves determining the optimal placement of facilities at set locations which minimizes the products of material flow and facility distance. This representation is descriptive of many real-world scenarios, including the aggregate transportation costs of a supply chain. In this work, a probabilistic Ising machine (PIM) approach is implemented using probabilistic d-dimensional variables (p-dits), which are generalized, multi-state and multi-dimensional extensions to probabilistic bits (p-bits). Each p-dit corresponds to a location and stochastically oscillates between facility assignments based on the influence of the other p-dits. We show that with the same runtime and CPU, the PIM finds the best-known solution on 95% of considered instances from the QAP Library dataset, compared to just 36% for the standard Gurobi solver. For the unique largest problem in the library, a 2 to 3 order-of-magnitude decrease is observed in the time needed to reach specific solution qualities. We also show parallelization of our PIM through GPU implementations. A comparison to state-of-the-art QAP solver algorithms shows that they are consistently outperformed by both CPU and GPU implementations of the p-dit Ising machine.
Combinatorial optimization problems represent a wide range of real-world scenarios where complicated interactions make it difficult to find the best solution. One example is the quadratic assignment problem (QAP), which involves determining the optimal placement of facilities at set locations which minimizes the products of material flow and facility distance. This representation is descriptive of many real-world scenarios, including the aggregate transportation costs of a supply chain. In this work, a probabilistic Ising machine (PIM) approach is implemented using probabilistic d-dimensional variables (p-dits), which are generalized, multi-state and multi-dimensional extensions to probabilistic bits (p-bits). Each p-dit corresponds to a location and stochastically oscillates between facility assignments based on the influence of the other p-dits. We show that with the same runtime and CPU, the PIM finds the best-known solution on 95% of considered instances from the QAP Library dataset, compared to just 36% for the standard Gurobi solver. For the unique largest problem in the library, a 2 to 3 order-of-magnitude decrease is observed in the time needed to reach specific solution qualities. We also show parallelization of our PIM through GPU implementations. A comparison to state-of-the-art QAP solver algorithms shows that they are consistently outperformed by both CPU and GPU implementations of the p-dit Ising machine.
Physics-inspired hardware solvers based on Ising machines have gained significant attention for addressing combinatorial optimization problems across diverse domains, including logistics, communication networks, and financial optimization. While the problems in these domains typically involve integer states, they are often reformulated to fit the quadratic unconstrained binary optimization (QUBO) framework supported by Ising machines. This is usually achieved by introducing penalty terms, which can degrade solution quality. In this work, we present a generalized integer-state probabilistic Ising machine (GIS-PIM) that natively supports integer-state encoding using compact binary representations. By avoiding one-hot encoding and associated constraints, GIS-PIM efficiently explores the solution space with fewer spin variables. The framework is implemented on a GPU and evaluated on publicly available graph coloring benchmarks, including both synthetic and realworld datasets. It demonstrates strong scalability, solving problem instances with up to 13 colors and graph sizes reaching approximately 20,000 nodes, a level not previously reported for other Ising-based methods. Our results indicate that the proposed approach: i) achieves solution accuracies exceeding 98%, competitive with leading classical methods such as Tabucol and graph neural network-based solver; and ii) significantly performs better over state-of-the-art simulated bifurcation (SBM) and QUBObased probabilistic Ising machines (Qu-PIM), achieving higher success probability and faster time-to-solution.
Permutation problems, such as the Travelling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP), form a well-established class of combinatorial optimisation problems with broad applications in routing, assignment, and scheduling. Metaheuristics, particularly Evolutionary Algorithms (EAs), have been widely demonstrated to yield high-quality solutions for these problems. In parallel, classical commercial solvers based on Mixed-Integer Programming (MIP), including CPLEX and Gurobi, have also been extensively applied. In recent years, there has been growing interest in quantum, quantum-inspired, and quantum-hybrid approaches for solving combinatorial optimisation problems. This paper presents a comparative analysis of six optimisation solvers: Genetic Algorithm (GA), Estimation of Distribution Algorithm (EDA), CPLEX, Gurobi, Digital Annealer (DA), and a quantum-hybrid Nonlinear solver (NL), applied to permutation problems. We evaluate solver performance in terms of runtime, solution quality relative to optimality, and scalability across instances of TSP and QAP. Our results highlight the promising performance of the quantum-hybrid Nonlinear solver across all evaluation metrics.
Ising Machines are emerging hardware architectures that efficiently solve NP-Hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ~10000x performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5-4x over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.
Ising machines including quantum annealers have attracted attention as efficient solvers for combinatorial optimization problems (COPs). To use Ising machines, the objective function and constraints of a COP must be expressed in a QUBO (quadratic unconstrained binary optimization) form. However, their application range is practically limited since some COPs are difficult to formulate in a QUBO form, or require a large number of binary variables. Quadratic three-dimensional assignment problem (Q3AP) is a challenging problem for Ising machines to solve since the number of required binary variables rapidly increases with the problem size N. In this paper, to overcome the difficulty, we propose a method to reduce the number of necessary variables fromN3to2N2by using a factorization machine with quantum annealing (FMQA) to estimate QUBO through machine learning. Experimental results with a real Ising machine demonstrate that the proposed method can obtain the best-known solution in a short time.
Abstract Ising Machines are emerging hardware architectures that efficiently solve NP-hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ∼ ~ 10000 × × performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5 − − 4 × × over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.
Abstract The Quadratic Assignment Problem (QAP) is an NP-hard fundamental combinatorial optimization problem introduced by Koopmans and Beckmann in 1957. The problem is to assign n facilities to n different locations with the goal of minimizing the cost of the total distances between facilities weighted by the corresponding flows. We initiate the study of using Rydberg arrays to find optimal solutions to the QAP and provide a complementing circuit theory to facilitate an easy representation of other hard problems. We provide an algorithm for finding valid and optimal solutions to the QAP using Rydberg arrays.