Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.04200 · npj Unconventional Computing

Restoring sparsity in potts machines via mean-field constraints

Kevin Callahan-Coray, K. Lee, Kyle Jiang, Kerem Yunus Camsari

Published Sep 2, 2026• 3 citations
arXivHTMLPDF

Abstract

Abstract Ising machines and related probabilistic hardware have emerged as promising platforms for NP-hard optimization and sampling. However, many practical problems involve constraints that induce dense or all-to-all couplings, undermining scalability and hardware efficiency. We address this constraint-induced density through two complementary approaches. First, we introduce a hardware-aware native formulation for multi-state probabilistic digits (p-dits) that avoids the locally dense intra-variable couplings required by binary Ising encodings. We validate p-dit dynamics by reproducing known critical behavior of the 2D Potts model. Second, we propose mean-field constraints (MFC), a hybrid scheme that replaces dense pairwise constraint couplings with dynamically updated single-node biases. Applied to balanced graph partitioning, MFC achieves solution quality comparable to exact all-to-all constraint formulations while dramatically reducing graph density. Finally, we demonstrate the practical impact of restored sparsity through an FPGA implementation. In comparisons using FPGA kernel time and CPU solver-loop time, and excluding the current prototype’s host-device schedule-transfer overhead, the FPGA reaches the 50% success threshold more than an order of magnitude faster than the CPU probabilistic solvers and more than two orders of magnitude faster than the Tabu Ising baseline. Together, these results outline a pathway for scaling constrained optimization on probabilistic hardware.

DOI
10.1038/s44335-026-00097-x

Related papers

A neuromorphic digital Ising solver with Tabu-inspired inhibitory dynamics for scalable graph optimization

Juan Núñez, Rafaella Fiorelli

Abstract We present a fully digital Ising solver for maximum-cut implemented on a low-cost Artix-7 field-programmable gate array (FPGA), where tabu-inspired inhibitory dynamics are realized as a compact, Block RAM-resident short-term memory. The solver operates in deterministic fixed-point arithmetic and scales up to the on-chip limit of N = 850 spins across multiple graph sizes and sparsity regimes. We benchmark the proposed Tabu-based dynamics against (i) a parallel Hopfield-network update rule implemented on the same FPGA, and (ii) a CPU-based quantum approximate optimization algorithm (QAOA) reference used as a fixed variational baseline for solution quality under a prescribed budget. Across the tested graph families, the Tabu-enhanced solver reaches higher cut values with reduced run-to-run dispersion than purely deterministic descent. Quantitatively, field-aligned warm start improves the median normalized cut of TS by 0.014 and reduces solve time by 0.18 ms at N = 100 , ρ = 20 % . At the largest tested size ( N = 850 ), TS improves the median normalized cut over the fixed-budget CPU-QAOA reference by 0.014–0.016, with median CPU–FPGA solve-time differences of 640–720 ms under the reported protocol. The N = 850 FPGA implementation closes timing at 100 MHz, demonstrating that short-term inhibitory memory can be embedded in a fully digital Ising network without relying on stochasticity, analog variability, or annealing schedules.

Neuromorphic Computing and Engineering•Jul 24, 2026•0 citations

Scalable connectivity for Ising machines: Dense to sparse

M. Mahmudul Hasan Sajeeb, Navid Anjum Aadit, Shuvro Chowdhury +7 more

In recent years, hardware implementations of Ising machines have emerged as a viable alternative to quantum computing for solving hard optimization problems among other applications. Unlike quantum hardware, dense connectivity can be achieved in classical systems. However, we show that dense connectivity leads to severe frequency slowdowns and interconnect congestion scaling unfavorably with system sizes. As a scalable solution, we propose a systematic sparsification method for dense graphs by introducing copy nodes to limit the number of neighbors per graph node. In addition to solving interconnect congestion, this approach enables constant frequency scaling where all spins in a network can be updated in constant time. On the other hand, sparsification introduces new difficulties, such as constraint-breaking between copied spins and increased convergence times to solve optimization problems, especially if exact ground states are sought. Relaxing the exact solution requirements, we find that the overheads in convergence times are milder. We demonstrate these ideas by designing probabilistic bit Ising machines using ASAP7 (a predictive 7nm FinFET technology model) process design kits as well as Field Programmable Gate Array (FPGA)-based implementations. Finally, we show how formulating problems in naturally sparse networks (e.g., by invertible logic) sidesteps challenges introduced by sparsification methods. Our results are applicable to a broad family of Ising machines using different hardware implementations.

arXiv:2503.01177•Physical Review Applied•Jun 2, 2025•22 citations

Efficient optimization accelerator framework for multi-state spin Ising problems

Chirag Garg, Sayeef Salahuddin

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 $$\sim$$ ~ 10000 $$\times$$ × performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5 $$-$$ − 4 $$\times$$ × over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.

arXiv:2505.20250•Nature Communications•Oct 30, 2025•5 citations

Scalable Optimization with GIS-PIM: A Generalized Integer-State Probabilistic Ising Machine

Chirag Garg, Sayeef Salahuddin

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.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 19, 2026•0 citations

Hardware-Aware Quantum Optimization

Gerlach, Thore Thassilo

Quantum Optimization (QO) is emerging as a promising approach to tackle hard combinatorial optimization problems by leveraging the unique computational properties of quantum hardware. In recent years, QO has gained traction in Machine Learning (ML), where problems such as clustering and vector quantization can be naturally expressed as Quadratic Unconstrained Binary Optimization (QUBO) problems. These ML applications often involve complex, high-dimensional data, which directly influences both the structure and scale of the resulting QUBO formulations. However, current quantum devices fall under the category of Noisy Intermediate-Scale Quantum (NISQ) hardware, which imposes significant limitations on qubit counts and small error rates. This dissertation investigates the impact of data complexity and data scale—as encountered in ML settings—on the effectiveness and feasibility of QO on NISQ devices. We propose novel, hardware-aware methods to overcome these challenges. The first part of this thesis focuses on the effect of data complexity for QO. We analyze how problem structure—particularly when QUBO formulations are derived from ML tasks—affects quantum solvability. We identify the spectral gap as a key factor in the success of adiabatic quantum algorithms and provide a theoretical and empirical analysis linking data-induced complexity to optimization performance.To address noise sensitivity and limited precision, we introduce a preprocessing framework based on a principled Branch-and-Bound algorithm that reduces dynamic range while preserving global optima. This improves robustness on both quantum annealers and classical solvers. In the second part, the thesis addresses challenges introduced by data scale. First, we propose a recursive Divide-and-Conquer strategy that breaks down large QUBO problems into tractable subproblems, demonstrated through an application to Bundle Adjustment in 3D scene reconstruction. Second, we introduce a variable and constraint generation method inspired by column generation for Integer Linear Programming, enabling dynamic QUBO size growth. This technique is successfully applied to Multi-Agent Pathfinding, where it scales well on NISQ devices while maintaining compatibility with classical solvers. Finally, we explore QUBO reformulations that reduce problem size through compact encodings and cyclic expansion, enabling the use of quantum hardware for tasks such as FPGA placement in chip design. Across all contributions, the developed algorithms are evaluated both theoretically and empirically, with experiments conducted on real quantum and quantum-inspired hardware. These methods significantly improve solution quality, scalability, and hardware compatibility, paving the way for more effective use of QO in practical settings. While tailored for NISQ era constraints, the results remain relevant for fault-tolerant quantum computing, offering insights into the long-term viability of QO across hardware generations.

•Nov 3, 2025•0 citations

Quantum- Inspired Structure- Preserving Probabilistic Inference

Sascha Mücke, Nico Piatkowski

Probabilistic methods serve as the underlying frame-work of various machine learning techniques. When using these models, a central problem is that of computing the partition function, whose computation is intractable for many models of interest. Here, we present the first quantum-inspired method that is especially designed for computing fast approximations to the partition function. Our approach uses a novel hardware solver for quadratic unconstrained binary optimization problems that relies on evolutionary computation. The specialized design allows us to assess millions of candidate solutions per second, leading to high quality maximum a-posterior (MAP) estimates, even for hard instances. We investigate the expected run-time of our solver and devise new ultra-sparse parity constraints to combine our device with the WISH approximation scheme. A SIMD-like packing strategy further allows us to solve multiple MAP instances at once, resulting in high efficiency and an additional speed-up. Numerical experiments show that our quantum-inspired approach produces accurate and robust results. While pure software implementations of the WISH algorithm typically run on large compute clusters with hundreds of CPUs, our results are achieved on two FPGA boards which both consume below 10 Watts. Moreover, our results extend seamlessly to adiabatic quantum computers.

IEEE Congress on Evolutionary Computation (CEC)•Jul 18, 2022•3 citations
Abstract Ising machines and related probabilistic hardware have emerged as promising platforms for NP-hard optimization and sampling. However, many practical problems involve constraints that induce dense or all-to-all couplings, undermining scalability and hardware efficiency. We address this constraint-induced density through two complementary approaches. First, we introduce a hardware-aware native formulation for multi-state probabilistic digits (p-dits) that avoids the locally dense intra-variable couplings required by binary Ising encodings. We validate p-dit dynamics by reproducing known critical behavior of the 2D Potts model. Second, we propose mean-field constraints (MFC), a hybrid scheme that replaces dense pairwise constraint couplings with dynamically updated single-node biases. Applied to balanced graph partitioning, MFC achieves solution quality comparable to exact all-to-all constraint formulations while dramatically reducing graph density. Finally, we demonstrate the practical impact of restored sparsity through an FPGA implementation. In comparisons using FPGA kernel time and CPU solver-loop time, and excluding the current prototype’s host-device schedule-transfer overhead, the FPGA reaches the 50% success threshold more than an order of magnitude faster than the CPU probabilistic solvers and more than two orders of magnitude faster than the Tabu Ising baseline. Together, these results outline a pathway for scaling constrained optimization on probabilistic hardware.
Abstract We present a fully digital Ising solver for maximum-cut implemented on a low-cost Artix-7 field-programmable gate array (FPGA), where tabu-inspired inhibitory dynamics are realized as a compact, Block RAM-resident short-term memory. The solver operates in deterministic fixed-point arithmetic and scales up to the on-chip limit of N = 850 spins across multiple graph sizes and sparsity regimes. We benchmark the proposed Tabu-based dynamics against (i) a parallel Hopfield-network update rule implemented on the same FPGA, and (ii) a CPU-based quantum approximate optimization algorithm (QAOA) reference used as a fixed variational baseline for solution quality under a prescribed budget. Across the tested graph families, the Tabu-enhanced solver reaches higher cut values with reduced run-to-run dispersion than purely deterministic descent. Quantitatively, field-aligned warm start improves the median normalized cut of TS by 0.014 and reduces solve time by 0.18 ms at N = 100 , ρ = 20 % . At the largest tested size ( N = 850 ), TS improves the median normalized cut over the fixed-budget CPU-QAOA reference by 0.014–0.016, with median CPU–FPGA solve-time differences of 640–720 ms under the reported protocol. The N = 850 FPGA implementation closes timing at 100 MHz, demonstrating that short-term inhibitory memory can be embedded in a fully digital Ising network without relying on stochasticity, analog variability, or annealing schedules.
In recent years, hardware implementations of Ising machines have emerged as a viable alternative to quantum computing for solving hard optimization problems among other applications. Unlike quantum hardware, dense connectivity can be achieved in classical systems. However, we show that dense connectivity leads to severe frequency slowdowns and interconnect congestion scaling unfavorably with system sizes. As a scalable solution, we propose a systematic sparsification method for dense graphs by introducing copy nodes to limit the number of neighbors per graph node. In addition to solving interconnect congestion, this approach enables constant frequency scaling where all spins in a network can be updated in constant time. On the other hand, sparsification introduces new difficulties, such as constraint-breaking between copied spins and increased convergence times to solve optimization problems, especially if exact ground states are sought. Relaxing the exact solution requirements, we find that the overheads in convergence times are milder. We demonstrate these ideas by designing probabilistic bit Ising machines using ASAP7 (a predictive 7nm FinFET technology model) process design kits as well as Field Programmable Gate Array (FPGA)-based implementations. Finally, we show how formulating problems in naturally sparse networks (e.g., by invertible logic) sidesteps challenges introduced by sparsification methods. Our results are applicable to a broad family of Ising machines using different hardware implementations.
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 ∼\sim∼ ~ 10000 ×\times× × performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5 −-− − 4 ×\times× × over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.
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.
Quantum Optimization (QO) is emerging as a promising approach to tackle hard combinatorial optimization problems by leveraging the unique computational properties of quantum hardware. In recent years, QO has gained traction in Machine Learning (ML), where problems such as clustering and vector quantization can be naturally expressed as Quadratic Unconstrained Binary Optimization (QUBO) problems. These ML applications often involve complex, high-dimensional data, which directly influences both the structure and scale of the resulting QUBO formulations. However, current quantum devices fall under the category of Noisy Intermediate-Scale Quantum (NISQ) hardware, which imposes significant limitations on qubit counts and small error rates. This dissertation investigates the impact of data complexity and data scale—as encountered in ML settings—on the effectiveness and feasibility of QO on NISQ devices. We propose novel, hardware-aware methods to overcome these challenges. The first part of this thesis focuses on the effect of data complexity for QO. We analyze how problem structure—particularly when QUBO formulations are derived from ML tasks—affects quantum solvability. We identify the spectral gap as a key factor in the success of adiabatic quantum algorithms and provide a theoretical and empirical analysis linking data-induced complexity to optimization performance.To address noise sensitivity and limited precision, we introduce a preprocessing framework based on a principled Branch-and-Bound algorithm that reduces dynamic range while preserving global optima. This improves robustness on both quantum annealers and classical solvers. In the second part, the thesis addresses challenges introduced by data scale. First, we propose a recursive Divide-and-Conquer strategy that breaks down large QUBO problems into tractable subproblems, demonstrated through an application to Bundle Adjustment in 3D scene reconstruction. Second, we introduce a variable and constraint generation method inspired by column generation for Integer Linear Programming, enabling dynamic QUBO size growth. This technique is successfully applied to Multi-Agent Pathfinding, where it scales well on NISQ devices while maintaining compatibility with classical solvers. Finally, we explore QUBO reformulations that reduce problem size through compact encodings and cyclic expansion, enabling the use of quantum hardware for tasks such as FPGA placement in chip design. Across all contributions, the developed algorithms are evaluated both theoretically and empirically, with experiments conducted on real quantum and quantum-inspired hardware. These methods significantly improve solution quality, scalability, and hardware compatibility, paving the way for more effective use of QO in practical settings. While tailored for NISQ era constraints, the results remain relevant for fault-tolerant quantum computing, offering insights into the long-term viability of QO across hardware generations.
Probabilistic methods serve as the underlying frame-work of various machine learning techniques. When using these models, a central problem is that of computing the partition function, whose computation is intractable for many models of interest. Here, we present the first quantum-inspired method that is especially designed for computing fast approximations to the partition function. Our approach uses a novel hardware solver for quadratic unconstrained binary optimization problems that relies on evolutionary computation. The specialized design allows us to assess millions of candidate solutions per second, leading to high quality maximum a-posterior (MAP) estimates, even for hard instances. We investigate the expected run-time of our solver and devise new ultra-sparse parity constraints to combine our device with the WISH approximation scheme. A SIMD-like packing strategy further allows us to solve multiple MAP instances at once, resulting in high efficiency and an additional speed-up. Numerical experiments show that our quantum-inspired approach produces accurate and robust results. While pure software implementations of the WISH algorithm typically run on large compute clusters with hundreds of CPUs, our results are achieved on two FPGA boards which both consume below 10 Watts. Moreover, our results extend seamlessly to adiabatic quantum computers.