Entropy-based computing platform solves complex optimization problems efficiently
Motzkin-Straus Optimization on an Entropy-Computing Platform
Emerging Technologies
Summary
Finding the largest tightly connected group in a network is a tough problem for computers. The authors use a special theorem to turn this problem into one about numbers that add up to one, which their unique photonic computer can solve. Their system often matches or beats traditional computer methods on many benchmark tests. However, traditional methods still perform better on the trickiest cases. This work shows that new types of computers using light and entropy can help solve complex problems in new ways.
What this means in practice
- •For optimization engineers: Use entropy computing to solve complex graph-based optimization problems faster on diverse structured networks.
- •For quantum hardware developers: Develop new unconventional computing devices that exploit entropy computing to tackle non-convex optimization tasks.
Authors
PoJen Wang, Sutapa Samanta, Yuntai Song, Mohammad-Ali Miri
Abstract
We introduce a framework for combinatorial optimization using sum-constrained continuous quadratic programs solvable by QCi's Dirac-3S photonic entropy computer. This is enabled by the Motzkin-Straus theorem which provides a powerful bridge between discrete clique problems and optimization over the probability simplex. We demonstrate this framework's versatility by solving constraint satisfaction problems, providing extensive benchmarks on the DIMACS suite. The Dirac-3S platform matches or outright leads two independently implemented classical baselines on more than four-fifths of the benchmark instances, reaching the best known solution on nearly all structured graph families, even outperforming both classical solvers on several of the largest instances tested. On the other hand, well-tuned classical continuous optimizers retain an edge only on the hardest planted-clique instances. This work establishes a viable pathway for solving combinatorial optimization problems using natively analog unconventional computing platforms, while positioning entropy computing as a competitive approach for navigating non-convex landscapes and providing rigorous baselines for an emerging computational paradigm.