⚛️ quantum physics

Motzkin-Straus Optimization on an Entropy-Computing Platform

This paper introduces a framework that leverages the Motzkin-Straus theorem to solve combinatorial optimization problems on QCi's Dirac-3S photonic entropy computer, demonstrating that this analog platform matches or surpasses classical solvers on most benchmark instances while establishing entropy computing as a competitive approach for navigating non-convex landscapes.

Original authors: PoJen Wang, Sutapa Samanta, Yuntai Song, Mohammad-Ali Miri

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: PoJen Wang, Sutapa Samanta, Yuntai Song, Mohammad-Ali Miri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, some problems are so complex that they seem to defy the limits of speed and memory. These are known as combinatorial optimization problems, a class of challenges where the goal is to find the single best arrangement among a staggering number of possibilities. Imagine trying to organize a massive party where you must select a group of guests who all know each other, but you want the largest possible group. As the guest list grows, the number of ways to form this group explodes, making it nearly impossible for traditional computers to check every option. This specific puzzle, known as finding the "maximum clique," is not just a mathematical curiosity; it underpins real-world tasks like scheduling flights, allocating resources, and analyzing social networks. For decades, scientists have struggled to solve these problems efficiently, often having to settle for good-enough answers rather than the perfect one.

Recently, a team of researchers has explored a new way to tackle these puzzles by turning to a different kind of machine. Instead of relying on the standard logic gates found in everyday computers, they utilized a device called an entropy computer. This machine operates on a principle that might seem counterintuitive: it uses the natural, random fluctuations of light—specifically the way photons, or particles of light, arrive in a stream—to help it escape dead ends. In the world of optimization, getting stuck in a "local minimum" is like finding a small valley in a mountain range and thinking it is the bottom of the world, when a much deeper valley lies just over the next ridge. Traditional computers often get stuck in these small valleys. The entropy computer, however, uses the inherent noise of the quantum world to nudge the system, allowing it to hop over ridges and explore the landscape more freely, hoping to find the true lowest point.

The researchers, working with a device called the Dirac-3S, set out to see if this approach could solve the maximum clique problem better than the best methods currently available on standard computers. They did not try to force the problem into a format the machine didn't naturally understand. Instead, they used a mathematical insight from the 1960s that translates the discrete problem of counting connected groups into a smooth, continuous shape. This translation was crucial because the Dirac-3S is built to handle smooth shapes and constraints naturally. The machine counts photons in time slots, and because you cannot have a negative number of photons, the device automatically respects the rule that all values must be positive. Furthermore, the total number of photons is fixed by the machine's design, which automatically satisfies the requirement that the values must add up to a specific total. This meant the researchers could map their problem directly onto the hardware without needing complex workarounds or extra steps that usually slow down other quantum systems.

To test their system, the team ran the Dirac-3S against two highly sophisticated classical computer programs on a standard set of 75 difficult graph problems. These problems ranged from small networks of 28 nodes to massive structures with 4,000 nodes. The results were striking. On more than four-fifths of the test cases, the entropy computer matched or surpassed the performance of the classical programs. In many of the largest and most complex instances, the Dirac-3S found better solutions than either of the classical rivals, often reaching the best-known answers that had been established by years of prior research. The machine seemed particularly adept at navigating the rough, bumpy terrain of these problems, concentrating its search efforts near the best solutions much more effectively than the classical methods, which often scattered their attempts across many less promising areas.

However, the story is not one of total victory. The researchers found that on a specific type of difficult problem, known as "planted clique" instances where a solution is hidden within a sea of noise, the classical computer programs still held an advantage. These programs, which use a strategy of restarting the search many times from different starting points, were better at finding the hidden solution in these specific cases. This suggests that while the entropy computer offers a powerful new way to explore complex landscapes, it is not yet a magic bullet that solves every instance perfectly. The researchers noted that the difference in performance was often small, sometimes just a single node in the group, but the fact that the entropy computer could compete so closely with the best classical algorithms on such a wide variety of problems is a significant step forward.

The work highlights a promising path for the future of computing. By using the natural behavior of light to solve problems that are notoriously hard for traditional machines, the entropy computer demonstrates that unconventional hardware can be a serious competitor. The researchers suggest that the most powerful approach in the future may not be to choose between classical and quantum methods, but to combine them. They envision a hybrid system where the entropy computer quickly scans the landscape to find promising regions, and then a classical computer refines the answer to find the exact peak. This study establishes that entropy computing is a viable and competitive approach for navigating the difficult, non-convex landscapes of real-world optimization, offering a new tool for scientists and engineers who need to solve the hardest puzzles of our time.

Technical Summary: Motzkin-Straus Optimization on an Entropy-Computing Platform

Problem Statement
The paper addresses the challenge of solving combinatorial optimization problems, specifically the Maximum Independent Set (MIS) and Maximum Clique problems, which are NP-hard. Traditional exact methods become computationally prohibitive as problem scales increase, while heuristic methods often sacrifice optimality guarantees. The Maximum Clique problem is particularly difficult due to its non-convex optimization landscape, which is replete with spurious local optima that trap deterministic, gradient-based algorithms. While the Motzkin-Straus theorem provides a mathematical bridge mapping the discrete Maximum Clique problem to a continuous quadratic program over a probability simplex, solving this continuous formulation remains challenging due to the complex landscape and the need for specialized solvers or heavy parameter tuning.

Methodology
The authors propose a framework utilizing Quantum Computing Inc.'s (QCI) Dirac-3S, a photonic entropy computer, to solve the continuous quadratic formulation of the Maximum Clique problem derived from the Motzkin-Straus theorem.

Theoretical Foundation: The Motzkin-Straus theorem states that the size of the maximum clique $\omega(G)$ in a graph $G$ is directly related to the maximum value of the quadratic form $\frac{1}{2}x^T Ax$ over the standard probability simplex $\Delta_n$ . The authors utilize this to transform the discrete clique problem into a continuous optimization problem: $\max \frac{1}{2}x^T Ax$ subject to $\sum x_i = 1$ and $x_i \ge 0$ .
Hardware Implementation (Dirac-3S): The Dirac-3S platform natively implements this optimization without the encoding overhead typical of other quantum approaches (e.g., Ising models requiring penalty terms).
- Quadratic Objective: The quadratic term maps directly to the two-body interaction term of the photonic hardware.
- Simplex Constraint: The hardware enforces a sum constraint ( $\sum v_i = R$ ) via photon conservation in the feedback loop, naturally satisfying the simplex requirement.
- Non-negativity: Photon counts are intrinsically non-negative, satisfying the $x_i \ge 0$ constraint without slack variables.
Mechanism of Action: The system minimizes a cost function using a quantum reservoir conditioned by controlled dissipation and measurement-feedback loops. Crucially, it leverages quantum shot noise (Poisson statistics of photon counting) as a computational resource. This noise drives stochastic exploration of the solution space, allowing the system to escape local minima in a manner functionally analogous to temperature in simulated annealing but arising from physical quantum fluctuations.
Solution Extraction: Since the continuous solution yields a non-integer estimate of the clique number, the authors employ extraction methods including rounding to the nearest integer and support-based identification (thresholding the solution vector) followed by greedy clique construction or enumeration.

Key Contributions

Framework Design: The implementation of Motzkin-Straus oracles on an entropy computing platform, establishing a direct physical realization of the mathematical structure of the Maximum Clique problem.
Benchmarking: A rigorous comparative performance analysis against two independently implemented classical baselines: Armijo-PGD (Projected Gradient Descent with Armijo backtracking and multi-restart) and Hexaly (a commercial general-purpose mathematical programming solver).
Empirical Validation: Extensive testing on 75 standard DIMACS benchmark graphs, covering diverse structural families (e.g., Brock, C-fat, Hamming, Johnson, planted-clique instances).

Results
The study evaluated the Dirac-3S platform against the classical solvers on 75 graph instances ranging from 28 to 4,000 vertices.

Overall Performance: Dirac-3S matched or exceeded the performance of both classical solvers on 62 of the 75 instances (more than four-fifths).
Large-Scale Instances: On the 14 largest graphs (1,000+ vertices), Dirac-3S was at or above the level of the other solvers on 13 instances. It was the sole leader on several large structured graphs (e.g., $C_{1000.9}$ , $C_{2000.9}$ , $keller6$).
Structured vs. Hard Instances:
- For structured families (Hamming, Johnson, $c$ -fat, $p\_hat$ ), all solvers achieved high approximation ratios (95–99%).
- For the planted-clique families (gen and san instances), which are known to be difficult for continuous optimization, the well-tuned classical solver Armijo-PGD retained a clear advantage (86.5% average ratio vs. 71.0% for Dirac-3S), attributed to its multi-restart strategy effectively exploring the landscape.
- On Brock series graphs, all solvers struggled, suggesting the difficulty is inherent to the Motzkin-Straus landscape for these specific structures rather than a hardware-specific flaw.
Solution Distribution: Analysis of energy histograms (e.g., on $C_{125.9}$ and $C_{250.9}$ ) revealed that Dirac-3S solutions were more sharply concentrated near the theoretical optimum compared to the broader distribution of Armijo-PGD restarts, indicating effective exploration of the landscape by the entropy computing dynamics.

Significance and Claims
The paper positions this work as a foundational experiment establishing a viable pathway for solving combinatorial optimization problems using natively analog, unconventional computing platforms.

Competitive Paradigm: It demonstrates that entropy computing is a competitive approach for navigating non-convex landscapes, offering a distinct alternative to gate-based quantum algorithms and classical heuristics.
Hardware-Native Advantage: The study highlights a significant practical advantage over quantum annealing (e.g., D-Wave) for dense graphs: the elimination of embedding overhead. The simplex constraint and non-negativity are satisfied at the hardware level, avoiding the solution quality degradation associated with minor embedding.
Modest Claims: The authors acknowledge that the current performance gap on planted-clique instances is a matter of algorithm design rather than a fundamental barrier. They do not claim a definitive "quantum advantage" in all cases but suggest that the platform's physical dynamics offer complementary strengths to gradient-based methods.
Future Outlook: The paper suggests that the true potential of this paradigm lies in hybrid quantum-classical algorithms, where the entropy computer acts as an oracle to identify promising regions of the search space, which are then refined by classical solvers. This positions entropy computing as a near-term, iterative benchmarking tool complementary to future fault-tolerant quantum systems.

More like this