A virtually connected probabilistic computer as a solver for higher-order, densely connected, or reconfigurable combinatorial optimisation problems
For researchers and practitioners solving NP-hard combinatorial optimization problems, this work offers a hardware architecture that avoids solution quality deterioration from topological constraints, potentially enabling faster and better solutions.
The authors propose a probabilistic computing architecture using virtual hardware connections to solve combinatorial optimization problems without requiring embedding, sparsification, or quadratisation. Simulations predict that this photonic probabilistic computer would outperform digital annealing units on Erdos-Renyi graph spin-glass ground state approximation by orders of magnitude.
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.