Reproduce “A virtually connected probabilistic computer as a solver for higher-order, densely connected, or reconfigurable combinatorial optimisation problems” on OpenResearch

About this paper

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

A virtually connected probabilistic computer (VCPC) capable of handling higher-order, densely connected, and dynamically reconfigurable combinatorial optimization problems is evaluated via simulation. The system demonstrates a capacity to avoid significant pre-processing overheads like quadratization or sparsification, leading to improved solution quality and estimated orders-of-magnitude faster time to solution for complex problems compared to traditional architectures.

Key insights

• Virtual connectivity fundamentally decouples problem structure from physical hardware constraints, enabling direct and efficient solutions for problems that typically incur high pre-processing overheads on physically connected solvers.
• Directly solving native HUBO problems on the VCPC yields better solution quality than solving quadratized QUBO versions, even with equivalent computational resources, indicating that quadratization introduces a more rugged energy landscape.
• The VCPC's reconfigurability is crucial for dynamically evolving problems, as demonstrated by the K-means clustering pre-processed TSP, where coupling patterns change at each step, making fixed-topology hardware inefficient.

Summary by alphaXiv.