Motzkin-Straus Optimization on an Entropy-Computing Platform

AI summary

Overview

Research area: Combinatorial optimization on unconventional/analog hardware — specifically quantum photonic "entropy computing" (Quantum Computing Inc.'s Dirac-3S platform) applied to the maximum clique and maximum independent set problems via the Motzkin-Straus theorem.

Technical level: Intermediate. The paper is readable with a background in optimization or graph theory; the hardware details are described physically but the key idea (map a clique problem to a constrained quadratic program, run it on photonic hardware) is accessible.

Scope: A framework plus extensive DIMACS benchmark comparison (75 graphs) of the Dirac-3S entropy computer against two classical baselines on the same unregularized Motzkin-Straus quadratic program.

What This Paper Is About

The maximum clique problem asks for the largest set of mutually connected vertices in a graph, and it is NP-hard. A 1965 result called the Motzkin-Straus theorem shows this discrete problem is exactly equivalent to maximizing a quadratic function over the probability simplex — a continuous, non-convex problem littered with spurious local optima. The paper's goal is to solve that continuous problem directly on a photonic entropy computer whose hardware constraints (non-negative variables summing to a fixed total) happen to match the simplex constraint exactly, and then to measure how well this hardware competes against well-tuned classical solvers.

Key Contributions

1. A hardware-native Motzkin-Straus oracle. The authors implement the clique-number optimization directly on QCi's Dirac-3S entropy computer. Because the device's photon-number variables are intrinsically non-negative and conserved in total ($\sum_i v_i = R$, with $R$ set by total photon flux), the simplex constraint and non-negativity are satisfied by the physics rather than by penalty terms, slack variables, quadratization, or minor embedding. Setting $R=1$ reproduces the standard simplex.

2. A clique-extraction pipeline from continuous solutions. Because continuous optima can be supported on non-cliques, the authors round the Motzkin-Straus formula $\omega(G) = 1/(1 + 2f^/R^2)$ to an integer, and also apply a support-based method: threshold the solution ($x_i^ > \tau$), enumerate all subsets when the support has size $|S| \le 20$, otherwise use greedy peeling (iteratively remove the vertex with the most non-adjacencies) and greedy building (iteratively add the heaviest vertex adjacent to all selected), keeping the best result and extending candidates to maximal cliques.

3. A rigorous 75-graph DIMACS benchmark against two independent classical baselines. The comparison holds the formulation fixed (the same unregularized quadratic program) and uses projected gradient descent with Armijo backtracking (Armijo-PGD, 100 restarts, up to 20,000 iterations each, JAX-implemented) and Hexaly 15.0, a commercial general-purpose solver given a 300-second time limit and an analytic gradient.

4. A family-level difficulty analysis. Approximation ratios are broken out by graph family, showing that the difficulty gradient is largely consistent across three mechanistically unrelated solvers — evidence that it reflects the Motzkin-Straus landscape itself rather than any one solver's weakness.

Main Findings

• Head-to-head on 75 DIMACS graphs (28 to 4,000 vertices): Dirac-3S matches or exceeds both classical solvers on 62 of the 75 instances, "more than four-fifths" of the benchmark. Armijo-PGD is at or above both competitors on 53 instances, Hexaly on 39.

• Sole-leader counts: On the 29 graphs where a single solver stands alone at the top, Dirac-3S leads on 17, Armijo-PGD on 12, and Hexaly on none. Where Dirac-3S is the sole leader, its margin is only 1–3 vertices.

• Best-known agreement: Dirac-3S and Armijo-PGD each reach the best known value on 33 of 75 graphs; Hexaly on 26. Across all 75, all three solvers return the same clique size on 33 instances (25 of which are the best known), and on a further 13 instances two of the three tie for highest. On 46 of 75 graphs no single solver stands alone at the top.

• Large instances favor Dirac-3S: Among the 14 graphs with at least 1,000 vertices, Dirac-3S is at or above both classical solvers on 13 of 14. It is the sole leader on C1000.9, C2000.5, C2000.9, hamming10-4, keller6, and p_hat1000-2; Armijo-PGD is the sole leader only on p_hat1000-3.

• Planted-clique instances are the exception: On the gen and san families, Armijo-PGD's many independent restarts give it a clear advantage. On the hardest planted cases it recovers the planted clique outright on san400_0.5_1, san400_0.7_1, and san400_0.7_2 with margins of up to 20 vertices. Armijo-PGD's leads outside the planted families are 1–2 vertices, apart from gen200-p0.9-55 where the margin is 5 vertices.

• Family-level approximation ratios (Table 3): Structured (Hamming, Johnson, c-fat; 17 instances): 99.4% Dirac-3S, 99.3% Armijo-PGD, 99.0% Hexaly. Dense random C-series (7): 92.9 / 90.3 / 88.0. Brock (12): 84.3 / 81.3 / 82.7. Planted clique (15): 71.0 / 86.5 / 70.8. p_hat (15): 98.8 / 98.6 / 95.8. Random (sanr, DSJC, keller; 9): 88.3 / 85.4 / 84.9. All 75: 89.2 / 91.2 / 87.4. Dirac-3S has the highest average ratio in five of six families; the planted-clique family alone gives Armijo-PGD the best overall average.

• Solution distributions differ qualitatively: On C125.9 (best known clique 34), Dirac-3S's energy histogram is sharply concentrated at the theoretical energies for $l = 33$ and $l = 34$, while Armijo-PGD's restarts spread across $l = 28$ through 34. On the harder C250.9 (best known 44), Dirac-3S's mass shifts toward higher clique sizes and samples reach $l = 44$, whereas Armijo-PGD's shown runs concentrate in the $l = 34$–42 range and do not reach 44.

• Time-to-solution trade-offs (Table 2): C125.9 — all three find 34/34, at roughly 15 s (Armijo-PGD, GPU), 65 s (Dirac-3S, 100 samples), 300 s (Hexaly). C250.9 — Dirac-3S finds 44/44 (100%) in roughly 120 s; Armijo-PGD and Hexaly both find 42/44 (95.5%) in roughly 10 s and 300 s respectively. brock400_2 — Armijo-PGD and Dirac-3S both find 24/29 (82.8%) in roughly 150 s and 200 s; Hexaly finds 23/29 (79.3%) in 300 s.

• Hardware noise as an exploration resource: Photon counting follows Poisson statistics with a fluctuation coefficient $1/\sqrt{N}$, so lower mean photon number increases relative shot noise and stochastic exploration. The paper cites prior Dirac-3 results showing that operating in the deep single-photon regime, where multi-photon event probability is below 1%, improves solution quality on non-convex problems — functionally analogous to temperature in simulated annealing but arising from quantum measurement physics.

• Device scale: Dirac-3S supports up to 9,980 independent variables under summation constraints, with num_samples in [1, 100] and relaxation_schedule in {1, 2, 3, 4}; the reported experiments use graphs up to approximately 4,000 vertices.

• Comparison scope is explicitly limited: The study compares only the unregularized Motzkin-Straus formulation and only two classical baselines; it does not include specialized maximum-clique heuristics, local-search/tabu methods, or graph neural network approaches, so it does not claim competitiveness against the strongest specialized clique algorithms.

Methodology in Plain English

The authors start from a classical theorem that turns "find the biggest clique" into "maximize a quadratic score over all non-negative vectors whose entries sum to one." That continuous problem has the same optimal value as the clique problem, but its landscape is full of decoy peaks that are not cliques.

Instead of solving that problem on a digital computer with penalty terms, the team loads the graph's adjacency matrix into a photonic machine where the optimization variables are literally photon counts in time bins. Photon counts cannot be negative, and the machine conserves the total photon flux, so two of the three mathematical constraints come for free; the third is just the quadratic interaction term, programmed by setting the coupling matrix to minus the adjacency matrix. Quantum shot noise in the photon counting acts as a built-in randomizing force that helps the system escape decoy peaks.

To read out an answer, they convert the machine's best energy back into a clique-size estimate and then extract an actual clique from the largest-magnitude entries of the solution, using exhaustive subset search for small supports and greedy peeling/building for large ones.

For comparison, they run the identical mathematical problem on two very different classical solvers: projected gradient descent with Armijo backtracking (100 random restarts from Dirichlet initializations), and Hexaly, a commercial heuristic-portfolio solver given 300 seconds. They then count, graph by graph, which solver returned the largest clique and how far each fell short of the literature's best known value.

Why This Matters

Impact on research. The work offers a concrete, quantitatively benchmarked alternative to the penalty-and-embedding pipeline that dominates quantum approaches to graph problems. On quantum annealers, dense graphs must be minor-embedded onto sparse hardware connectivity, which introduces overhead and degrades quality; here the mapping is direct. The paper also provides a template for how emerging analog hardware should be evaluated: against multiple independently implemented classical baselines on the same formulation, with family-level breakdowns rather than a single aggregate number. Its honest framing — margins of 1–2 vertices, advantages confined to certain families, possible equivalence to hardware-implemented stochastic optimization — is itself a contribution to benchmark rigor.

Real-world applications (as motivated in the paper):

• Logistics and resource allocation, where independent-set structure underlies packing and assignment decisions.
• Scheduling, where mutually conflicting tasks form a graph whose independent sets are feasible schedules.
• Network analysis, including finding tightly connected groups.
• Community detection, named explicitly in the paper's Figure 1 as an application of maximum clique.
• Bioinformatics and coding theory: the paper notes Hamming graphs encode error-correcting code structures, giving the benchmarks practical relevance beyond academic testing.

Industry relevance. Entropy computing runs on existing hardware rather than requiring fault-tolerant quantum computers, so it is deployable and iteratively improvable now. It occupies a distinct niche from gate-based quantum computing, which needs error-correction infrastructure the paper describes as potentially years from maturity. For practitioners, the immediate lesson is that a second, architecturally distinct solver can add value on large dense graphs even when its average performance is comparable.

Future Directions

• Hybrid quantum-classical algorithms. The paper's stated view is that the paradigm's real power may lie in combining the Dirac-3S oracle's fast identification of promising regions with classical refinement — the truncated text ends mid-sentence at "using the Dirac-3S entropy computing oracle to quickly identify promising re[gions]."

• Characterizing when physical dynamics beat gradient methods. The authors identify this as a key open question, specifically understanding behavior "near energy barriers," and whether the platform's advantage is qualitative or is better understood as hardware-implemented stochastic optimization.

• Closing the planted-clique gap. Solution quality is weakest on the gen and san instances and on Brock graphs, where the maximum clique hides among many competing local optima. Applying regularization or alternative formulations on the hardware is an obvious next step, though both baselines were deliberately restricted to the unregularized form here.

• Richer readout and broader baselines. Each run currently yields a single clique extracted from the highest-weight solution, and the comparison omits specialized clique heuristics, local-search/tabu methods, parallel clique algorithms, and graph neural network approaches — all natural extensions.

Target Audience

Researchers and engineers working on quantum and unconventional computing for combinatorial optimization; benchmarking specialists who need a model for comparing analog hardware against strong classical baselines; practitioners in graph algorithms interested in continuous relaxations of clique and independent-set problems; and graduate students in physics, applied mathematics, or operations research who want a clear worked example of mapping a classical NP-hard problem directly onto physical hardware constraints. Readers seeking a definitive claim of quantum advantage will not find one here — the paper is explicit that its margins are small and its evidence suggestive rather than conclusive.

Authors’ 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.