Source-linked AI summary
Motzkin-Straus Optimization on an Entropy-Computing Platform
PoJen Wang, Sutapa Samanta, Yuntai Song, Mohammad-Ali Miri
TL;DR
The paper addresses the challenge of solving NP-hard combinatorial problems and explores a direct Motzkin–Straus optimization mapping to QCI’s Dirac-3S entropy computer. On DIMACS benchmarks, Dirac-3S matches or exceeds both classical baselines on 62 of 75 graphs; the study identifies reduced accuracy on planted-clique instances as a limitation.
Problem
Exact methods can be prohibitive on large or difficult combinatorial instances, while practical heuristics surrender guarantees of optimality.
Source: §1 · p. 2Method
The framework maps maximum clique through the Motzkin–Straus theorem to a continuous quadratic program that Dirac-3S can optimize directly, and benchmarks it against Armijo-PGD and Hexaly.
Source: §1 · p. 3, §2.1 · p. 5Results
Dirac-3S matches or exceeds both classical solvers on 62 of the 75 DIMACS graphs.
Source: §4.1 · p. 10Takeaways & Limitations
The study presents entropy computing as a complementary approach to gate-based quantum algorithms and points to hybrid quantum-classical algorithms as a path forward.
Source: §5.3 · p. 16, §6 · p. 17Solution quality is weakest on planted-clique gen and san instances and Brock graphs, and the comparison excludes specialized clique heuristics.
Source: §5.4 · p. 16
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses the difficulty of solving non-convex Motzkin–Straus programs and introduces a direct implementation on QCI’s Dirac-3S entropy computer. It evaluates the approach against two classical solvers on DIMACS graphs.
Motivation
- Exact methods can become prohibitive on large or difficult instances, while practical heuristics do not guarantee optimality.The paper identifies this challenge across applications including resource allocation, scheduling, and network analysis.Source: §1 · p. 2
Background
- The Motzkin–Straus formulation has spurious local optima, while regularization can remove non-clique solutions at the cost of problem-dependent parameters.Alternative reformulations can also raise objective complexity or require computationally intensive multi-restart strategies.Source: §1 · p. 2
Entropy computing
- Dirac-3S uses controlled dissipation and measurement-feedback, treating quantum fluctuations and shot noise as resources for escaping local minima.The paper distinguishes this approach from mainstream quantum computing’s reliance on fragile, isolated quantum systems.Source: §1 · p. 3
Contribution
- The Dirac-3S Motzkin–Straus oracle is benchmarked on DIMACS graphs against Armijo-PGD and Hexaly on the same unregularized quadratic program.The Motzkin–Straus mapping and hardware constraints are illustrated in Fig. 1.Source: §1 · p. 3, Figure 1 · p. 4
2 Max-clique Problem
The Motzkin–Straus theorem connects maximum clique to continuous quadratic optimization over a simplex. The section extends this formulation to maximum independent set and describes how continuous solutions yield discrete cliques.
2.1 Problem Formulation
- The Motzkin–Straus theorem links graph structure to continuous optimization over non-negative variables with a sum constraint.The standard probability simplex consists of non-negative variables summing to one.Source: §2.1 · p. 4
- Optimizing the complement graph gives a framework for maximum independent set because its independence number equals the maximum clique number of the complement.Source: §2.1 · p. 5
2.2 Clique Extraction from Continuous Solutions
- Continuous estimates may be non-integer and supported on non-cliques, so the method rounds the estimated clique number and extracts candidates from thresholded supports.For supports of at most 20 vertices, it enumerates subsets; for larger supports, it applies greedy peeling and building, then extends candidates to maximal cliques.Source: §2.2 · p. 5
3 Solvers
Dirac-3S natively supports the non-negativity and sum constraints of the Motzkin–Straus program, while classical baselines solve the same formulation using distinct optimization strategies. The section details the hardware mapping, fluctuation trade-off, and solver implementations.
3.1 Dirac-3S
- Dirac-3S is a hybrid quantum-classical measurement-feedback system that encodes optimization variables in time-multiplexed photon qudits.The current implementation supports up to 9,980 independent variables under summation constraints.Source: §3.1 · pp. 5, 7
- The photonic architecture directly maps the Motzkin–Straus quadratic objective, simplex constraint, and non-negativity to hardware without encoding overhead.The objective maps to two-body interactions, the sum constraint to photon conservation, and non-negativity to photon counting; no slack variables or penalties are required.Source: §3.1 · p. 6
- Lower photon numbers increase shot-noise-driven exploration of the non-convex landscape but require more measurement time for photon accumulation.The fluctuation coefficient is 1/N, where N is the number of photons accumulated per time bin.Source: §3.1 · p. 6
3.2 Classical Solvers
- The evaluation compares Dirac-3S with Armijo-PGD and Hexaly on the same unregularized Motzkin–Straus program, not with specialized maximum-clique algorithms.The authors note that specialized approaches use different formulations or search strategies and are not evaluated.Source: §3.2 · p. 7
3.2.1 Armijo-PGD
- Armijo-PGD combines simplex-projected gradient steps, adaptive Armijo backtracking, and multiple initializations to explore the non-convex landscape.The implementation uses 100 restarts, with up to 20,000 iterations per restart.Source: §3.2.1 · pp. 7–8
3.2.2 Hexaly
- Hexaly is a general-purpose solver using local-search and direct-search heuristics with exact components, supplied the quadratic objective and its analytic gradient.The experiments use a 300-second time limit; supplying the gradient rather than finite-differencing helps it scale to large variable counts.Source: §3.2.2 · p. 8
4 Results
Across 75 DIMACS graphs, Dirac-3S matches or exceeds both classical solvers on most instances, though performance varies by graph family and difficulty. On the illustrated C125.9 and C250.9 cases, its sampled solutions cluster nearer the best-known clique sizes than Armijo-PGD’s.
4.1 Benchmark On DIMACS
- On 13 of the 14 graphs with at least 1,000 vertices, Dirac-3S ties or leads; all three solvers struggle on Brock graphs, while Armijo-PGD leads on planted gen and san instances.Armijo-PGD’s many independent restarts give it a clear advantage on the planted-clique instances.Source: §4.1 · p. 11
4.2 Energy Histogram of Specific Examples
- On C125.9 and C250.9, Dirac-3S’s sampled energies cluster nearer the best-known clique sizes than Armijo-PGD’s, which spreads across lower energies and misses 44 in the shown C250.9 runs.On C125.9, most Dirac-3S runs across all relaxation-schedule settings land at clique sizes 33 or 34.Source: §4.2 · p. 11
4.1 Benchmark On DIMACS
- On 62 of 75 graphs, Dirac-3S matches or exceeds both classical solvers; it is sole leader on 17, versus 12 for Armijo-PGD and none for Hexaly.Dirac-3S and Armijo-PGD each reach the best-known value on 33 graphs, compared with 26 for Hexaly.Source: §4.1 · pp. 10–11, Figure 2 · p. 12
4.2 Energy Histogram of Specific Examples
- With 100 Dirac-3S samples and Hexaly’s fixed 300-second limit, all solvers reach C125.9’s optimum; only Dirac-3S reaches 44 on C250.9, and none reach 29 on brock400_2.The three instances represent easy, moderate, and hard cases, respectively.Source: Table 2 · p. 12, §4.2 · p. 12
5 Discussion
Dirac-3S performs strongly across DIMACS graph families, while planted-clique instances remain a notable weakness. The discussion interprets its large-instance results as suggestive, describes hardware-level practical advantages, and identifies scope limits and hybrid methods as directions for future work.
5.1 Graph Family Analysis
- Structured families average 95–99%, while Brock graphs average 81–84% and planted-clique gen and san average 71% for Dirac-3S and Hexaly.Armijo-PGD averages 86.5% on the planted-clique family; difficulty rankings are broadly consistent across the three solvers, suggesting a role for Motzkin-Straus landscape structure.Source: §5.1 · p. 13
5.2 Interpreting Benchmark Results Through Platform Characteristics
- On 13 of 14 instances with at least 1,000 vertices, Dirac-3S is at or above both classical baselines, but its usual one- or two-vertex margins make the evidence suggestive rather than conclusive.The authors note that some apparent advantage may reflect consulting a second independent solver; determining when physical dynamics help near energy barriers remains future work.Source: §5.2 · p. 15
5.3 Assessment and Practical Considerations
- Dirac-3S matches or leads Armijo-PGD and Hexaly on more than four-fifths of DIMACS instances and has the highest average approximation ratio in five of six families.Armijo-PGD leads on planted-clique instances, giving it the highest overall average ratio: 91.2% versus 89.2% for Dirac-3S and 87.4% for Hexaly.Source: §5.1 · p. 13, §5.3 · p. 15, Table 3 · p. 15
- Dirac-3S implements the Motzkin-Straus quadratic program directly without dense-graph embedding overhead, satisfying the simplex constraint at the hardware level.The authors position existing entropy-computing hardware as a platform for iterative benchmarking, complementary to gate-based algorithms requiring extensive error-correction infrastructure.Source: §5.3 · pp. 15–16
5.4 Current Limitations and a Roadmap for the Future
- The comparison is limited to the unregularized quadratic formulation and Armijo-PGD and Hexaly, and excludes specialized clique heuristics.Solution quality is weakest on planted-clique gen and san instances and Brock graphs; the authors propose hybrid quantum-classical algorithms as a future direction.Source: §5.4 · p. 16
6 Conclusion
Dirac-3S is competitive with classical baselines across the benchmark, though well-tuned classical solvers retain an advantage on the hardest planted-clique instances. The conclusion presents reduced planted-clique accuracy as an algorithm-design issue and hybrid algorithms as a pathway toward closing that gap.
6 Conclusion
- Across 75 DIMACS instances, Dirac-3S matches or leads both classical baselines on the majority, while well-tuned classical solvers retain an advantage on the hardest planted-clique benchmarks.The baselines are Armijo-PGD and Hexaly.Source: §6 · p. 16
- Reduced accuracy on planted-clique instances is the main limitation, characterized as a matter of algorithm design rather than a fundamental barrier.Hybrid quantum-classical algorithms are described as a pathway toward closing the gap with classical solvers.Source: §6 · pp. 16–17
- The work is framed as a foundational experiment in applying entropy computing to canonical NP-hard problems, with hybrid algorithms offering a route toward practical quantum advantage.Source: §6 · pp. 16–17