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:2605.06037

A virtually connected probabilistic computer as a solver for higher-order, densely connected, or reconfigurable combinatorial optimisation problems

Amy J. Searle, Harry Youel, Fredrik Hasselgren, Annika Moslein, Ramy Aboushelbaya, Marko von der Leyen

Published May 7, 2026• 0 citations
arXivHTMLPDF

Abstract

Recently, there has been growing interest in unconventional computing as an approach for solving NP-hard problems, by developing dedicated hardware to find solutions more efficiently than conventional CPUs. In many of these approaches, however, certain problem geometries must be transformed into forms that are more amenable to the available hardware topology through techniques such as embedding, sparsification, and quadratisation, leading to a deterioration in solution quality. A probabilistic computing architecture based on high speed photonic quantum random number generators was recently proposed which utilises virtual hardware connections (Aboushelbaya et al., 2025), circumventing the necessity for such procedures. Here, we discuss the applicability of virtually connected hardware for running heuristic solving methods to solve a selection of problems, which due to their geometry, would suffer from topological hardware restrictions. We also employ greedy graph colouring algorithms for hardware parallelisation, allowing favourable scaling for desirable solution qualities. To emphasise the difficulty in solving these problems on physically connected hardware, we demonstrate the increase in problem size that would occur with quadratisation or sparsification. Using simulations to emulate hardware, we predict that a photonic probabilistic computer would outperform the time to solution recently reported for digital annealing units, on the ground state approximation of Erdos-Renyi graph spin-glasses, by orders of magnitude.

DOI
10.48550/arxiv.2605.06037

Related papers

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•11 citations

Probabilistic Prime Factorization based on Virtually Connected Boltzmann Machine and Probabilistic Annealing

Hyundo Jung, Hyunjin Kim, Lee, Woojin +4 more

Probabilistic computing has been introduced to operate functional networks using a probabilistic bit (p-bit), generating 0 or 1 probabilistically from its electrical input. In contrast to quantum computers, probabilistic computing enables the operation of adiabatic algorithms even at room temperature, and is expected to broaden computational abilities in non-deterministic polynomial searching and learning problems. However, previous developments of probabilistic machines have focused on emulating the operation of quantum computers similarly, implementing every p-bit with large weight-sum matrix multiplication blocks or requiring tens of times more p-bits than semiprime bits. Furthermore, previous probabilistic machines adopted the graph model of quantum computers for updating the hardware connections, which further increased the number of sampling operations. Here we introduce a digitally accelerated prime factorization machine with a virtually connected Boltzmann machine and probabilistic annealing method, designed to reduce the complexity and number of sampling operations to below those of previous probabilistic factorization machines. In 10-bit to 64-bit factorizations were performed to assess the effectiveness of the machine, and the machine offers 1.2 X 10^8 times improvement in the number of sampling operations compared with previous factorization machines, with a 22-fold smaller hardware resource. This work shows that probabilistic machines can be implemented in a cost-effective manner using a field-programmable gate array, and hence we suggest that probabilistic computers can be employed for solving various large NP searching problems in the near future.

arXiv:2210.14519•Oct 26, 2022•1 citation

Efficient Optimization Accelerator Framework for Multistate Ising Problems

Chirag Garg, Sayeef Salahuddin

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.

arXiv:2505.20250•May 26, 2025•0 citations

On Modeling Local Search with Special-Purpose Combinatorial Optimization Hardware

Xiaoyuan Liu, Hayato Ushijima‐Mwesigwa, Avradip Mandal +3 more

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.

•Jan 1, 2019•4 citations

Classical combinatorial optimization scaling for random Ising models on 2D heavy-hex graphs

Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz

Abstract Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.

arXiv:2412.15572•Journal of Physics Communications•Apr 27, 2026•0 citations

Ising accelerator with a reconfigurable interferometric photonic processor

Rausell-Campo, José Roberto, Kayed, Nayem Al, Pérez-Lppez, Daniel +3 more

The general-purpose programmable photonic processors offer a scalable and reconfigurable solution for a wide range of RF and optical applications. Therefore, implementing photonic Ising machines using programmable processors leverages the advantages of high speed and parallelism, enabling efficient hardware acceleration for finding ground-state solutions to combinatorial optimization problems. In this work, we demonstrate a novel programmable photonic Ising solver based on a hexagonal mesh general-purpose programmable photonic platform. The integrated system allows reconfigurable matrix multiplication and computes the Hamiltonian iteratively using an annealing algorithm that facilitates spin updates and effectively searches for the ground state. As a proof of concept, we experimentally solve two benchmark optimization problems, a fundamental three-node ferromagnetic coupling problem with external bias that demonstrates nontrivial spin interactions, and a four-node Max-Cut problem with arbitrary coupling matrices. Furthermore, to establish a large-scale capability, we emulated Ising problems with sizes up to N = 50, achieving success probabilities exceeding 80\%. Additionally, we examined the impact of errors, such as phase and coupling, on the performance of the programmable photonic Ising machine. Our general-purpose photonic Ising machine paves the way for implementing large-scale, programmable architectures for solving optimization problems.

arXiv:2511.13284•Nov 17, 2025•0 citations
Recently, there has been growing interest in unconventional computing as an approach for solving NP-hard problems, by developing dedicated hardware to find solutions more efficiently than conventional CPUs. In many of these approaches, however, certain problem geometries must be transformed into forms that are more amenable to the available hardware topology through techniques such as embedding, sparsification, and quadratisation, leading to a deterioration in solution quality. A probabilistic computing architecture based on high speed photonic quantum random number generators was recently proposed which utilises virtual hardware connections (Aboushelbaya et al., 2025), circumventing the necessity for such procedures. Here, we discuss the applicability of virtually connected hardware for running heuristic solving methods to solve a selection of problems, which due to their geometry, would suffer from topological hardware restrictions. We also employ greedy graph colouring algorithms for hardware parallelisation, allowing favourable scaling for desirable solution qualities. To emphasise the difficulty in solving these problems on physically connected hardware, we demonstrate the increase in problem size that would occur with quadratisation or sparsification. Using simulations to emulate hardware, we predict that a photonic probabilistic computer would outperform the time to solution recently reported for digital annealing units, on the ground state approximation of Erdos-Renyi graph spin-glasses, by orders of magnitude.
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.
Probabilistic computing has been introduced to operate functional networks using a probabilistic bit (p-bit), generating 0 or 1 probabilistically from its electrical input. In contrast to quantum computers, probabilistic computing enables the operation of adiabatic algorithms even at room temperature, and is expected to broaden computational abilities in non-deterministic polynomial searching and learning problems. However, previous developments of probabilistic machines have focused on emulating the operation of quantum computers similarly, implementing every p-bit with large weight-sum matrix multiplication blocks or requiring tens of times more p-bits than semiprime bits. Furthermore, previous probabilistic machines adopted the graph model of quantum computers for updating the hardware connections, which further increased the number of sampling operations. Here we introduce a digitally accelerated prime factorization machine with a virtually connected Boltzmann machine and probabilistic annealing method, designed to reduce the complexity and number of sampling operations to below those of previous probabilistic factorization machines. In 10-bit to 64-bit factorizations were performed to assess the effectiveness of the machine, and the machine offers 1.2 X 10^8 times improvement in the number of sampling operations compared with previous factorization machines, with a 22-fold smaller hardware resource. This work shows that probabilistic machines can be implemented in a cost-effective manner using a field-programmable gate array, and hence we suggest that probabilistic computers can be employed for solving various large NP searching problems in the near future.
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.
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.
Abstract Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.
The general-purpose programmable photonic processors offer a scalable and reconfigurable solution for a wide range of RF and optical applications. Therefore, implementing photonic Ising machines using programmable processors leverages the advantages of high speed and parallelism, enabling efficient hardware acceleration for finding ground-state solutions to combinatorial optimization problems. In this work, we demonstrate a novel programmable photonic Ising solver based on a hexagonal mesh general-purpose programmable photonic platform. The integrated system allows reconfigurable matrix multiplication and computes the Hamiltonian iteratively using an annealing algorithm that facilitates spin updates and effectively searches for the ground state. As a proof of concept, we experimentally solve two benchmark optimization problems, a fundamental three-node ferromagnetic coupling problem with external bias that demonstrates nontrivial spin interactions, and a four-node Max-Cut problem with arbitrary coupling matrices. Furthermore, to establish a large-scale capability, we emulated Ising problems with sizes up to N = 50, achieving success probabilities exceeding 80\%. Additionally, we examined the impact of errors, such as phase and coupling, on the performance of the programmable photonic Ising machine. Our general-purpose photonic Ising machine paves the way for implementing large-scale, programmable architectures for solving optimization problems.