Strongly Regular Graph Construction via Quadratic Binary Optimization

arXiv:2610.30142 · math.OC, math.CO, quant-ph · Submitted 2026-07-31 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Strongly Regular Graph Construction via Quadratic Binary Optimization".

Mira: Here's the gist of the paper. The gist is that a quadratic function of edge variables whose global minimizers are exactly the labeled Strongly Regular Graphs exists only when every k-regular graph is already the target, which happens for the perfect matchings, cocktail-party graphs and the pentagon, and for no other feasible parameter set How it works The paper develops two complementary routes to address Strongly Regular Graph construction via quadratic binary optimization.

Kai: The first route involves a pure-QUBO formulation, which is exact on the three degenerate families, and beyond them it operates as a generate–prune–verify pipeline.

Mira: The second route involves enlarging the variable space by introducing auxiliary variables through Rosenberg quadratization to cast the full problem as a single QUBO instance.

Kai: Pure-QUBO Route The pure-QUBO route relies on minimizing the generation Hamiltonian Hgen, which is a quadratic polynomial over binary variables.

Paper summary: Mira: To wrap up "Strongly Regular Graph Construction via Quadratic Binary Optimization," they establish that a quadratic function of the edge variables can only have labeled SRGs as its exact set of global minimizers for three degenerate families: perfect matchings, cocktail-party graphs, and pentagons.

Kai: They also formally prove that for every other feasible parameter set, including Conway’s problem with ninety-nine vertices and fourteen degrees, auxiliary variables are unavoidable if you want to encode it all into one QUBO instance <ref:2610.30142#pg2,for every other feasible parameter set, including>.

Lev: The implication is that for any SRG beyond those three types, the method requires enlarging the variable space using Rosenberg auxiliary variables to cast the full quartic penalty into a quadratic form.

Mira: So they’ve given us a very clear picture of what quadratic binary optimization can and cannot do for graph construction. It’s not as powerful as people might have hoped when it comes to general SRGs without that extra machinery.

Kai: The paper shows the two routes are complementary in scope and empirically complementary on the same targets, meaning you get insight from both ways of thinking about this problem.

Lev: For anyone building error-correcting codes or trying to model these structures, it means you either need a pipeline for smaller sets or you need to prepare for a much larger QUBO problem if your target graph is not one of the three simple ones.

Conclusion: Kai: So, we’ve been looking at how you can build these strongly regular graphs using quadratic binary optimization, and this paper is all about setting some firm boundaries on what that optimization can actually achieve.

Mira: It really cuts through the noise by showing that there are very strict limits to when a simple quadratic function of the edge variables can land exactly on a labeled SRG.

Lev: So if you want to build something complex, you have to go beyond just trying to make one big QUBO and introduce these auxiliary variables.

Kai: Exactly. They’re saying that for most graphs, including the ninety-nine-vertex one Conway worked on, you can't just do it without some extra help from those auxiliary variables.

Mira: And they formally prove that this isn't just a suggestion; it’s a hard constraint based on the structure of the problem itself.

Lev: From an error correction standpoint, that means if we want to model these structures with real hardware, we have to account for the overhead of those extra variables.

Kai: It really highlights the difference between what’s theoretically possible in a pure QUBO setup and what you can actually implement on a chip.

Mira: The main point is that this quadratic method isn't a magic tool for constructing any SRG, just like we learned it’s not a magic tool for everything else in this field.

Lev: It gives us two clear paths forward, either stick to the simpler three special cases or prepare to deal with the complexity of those auxiliary variables.

Kai: And that sets up a really interesting comparison between those two approaches we discussed earlier.

Instituto de Física, Pontificia Universidad Católica de Chile · Departamento de Física, Universidad de Antofagasta, Chile · Jagiellonian University, Marian Smoluchowski Institute of Physics · School of Physics, Trinity College Dublin

math.OC, math.CO, quant-ph

Submitted: 2026-07-31

Updated: 2026-07-31

Comments: 26 pages, 4 figures, 5 tables, 3 appendices. Includes a no-go theorem ruling out auxiliary-free QUBO encodings of strongly regular graphs, with an application to Conway's 99-graph problem. Comments welcome!

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 86/100

The gist: The gist is that a quadratic function of edge variables whose global minimizers are exactly the labeled Strongly Regular Graphs exists only when every k-regular graph is already the target, which

Key concepts

Strongly Regular Graphs (SRGs): These are highly structured combinatorial objects defined by specific properties related to the number of connections between vertices. They are central to algebraic graph theory and quantum information, but their explicit construction becomes very difficult as the number of vertices increases.
QUBO (Quadratic Unconstrained Binary Optimization): This is a type of optimization problem where you want to find a set of binary variables that minimizes a quadratic function. The paper explores whether the exact set of solutions for SRGs can be found by minimizing such a function directly, without needing extra variables.
Rosenberg Auxiliary Variables: These are extra binary variables introduced into the optimization problem to transform a higher-order (quartic) penalty term into a quadratic one. This technique allows the full SRG problem to be solved as a single QUBO instance, though it significantly increases the total number of variables.
Generate–Prune–Verify Pipeline: This is an alternative strategy used when direct QUBO formulation fails. It involves generating candidate graphs using a quadratic penalty and then filtering these candidates through spectral analysis (like maximum clique checks) before performing a final algebraic verification to ensure they are true SRGs.

Terminology

Graph Construction — 1× in this paper · explained in 3 episodes

Summary

The gist is that a quadratic function of edge variables whose global minimizers are exactly the labeled Strongly Regular Graphs exists only when every k-regular graph is already the target, which happens for the perfect matchings, cocktail-party graphs and the pentagon, and for no other feasible parameter set

How it works

The paper develops two complementary routes to address Strongly Regular Graph construction via quadratic binary optimization. The first route involves a pure-QUBO formulation, which is exact on the three degenerate families, and beyond them it operates as a generate–prune–verify pipeline. The second route involves enlarging the variable space by introducing auxiliary variables through Rosenberg quadratization to cast the full problem as a single QUBO instance.

Pure-QUBO Route

The pure-QUBO route relies on minimizing the generation Hamiltonian Hgen, which is a quadratic polynomial over binary variables. This Hamiltonian is defined by the k-regularity condition and the common neighbor conditions, resulting in a HUBO rather than a QUBO problem. The paper shows that for every other feasible parameter set, auxiliary variables are unavoidable for an exact single-QUBO formulation.

Generate–Prune–Verify Pipeline

When an exact pure-QUBO formulation is forbidden, the authors adopt a strategy that approaches the problem as closely as a pure QUBO over the edge variables permits, adopting a transparent generate–prune–verify pipeline consisting of two QUBO stages. Stage I involves Graph Generation, which generates highly restricted k-regular candidate graphs through the quadratic penalty Hgen coupled with a symmetry-breaking mechanism. Stage II is QUBO-Based Spectral Postselection of the generated candidates using maximum clique analysis and the Hoffman bound. A final exact algebraic verification against Eq. (1) is then applied to the reduced output of the two QUBO stages.

Auxiliary-Variable Route

The auxiliary-variable route solves the full problem by quadratizing the quartic penalty Hλµ through Rosenberg auxiliary variables. This process eliminates all terms of degree higher than two from the original HUBO Hamiltonian, resulting in a complete QUBO Hamiltonian HSRG = w1 Hgen + w2 H(q)λµ + w3 Haux. The global minimizers of this full SRG Hamiltonian are in one-to-one correspondence with the adjacency matrices of the target SRGs.

Variable Counting and Scaling

The benefit of a fully QUBO encoding comes at the cost of a polynomial increase in the number of binary variables. The set of edge variables has cardinality N(N − 1)/2, whereas the set of auxiliary variables indexed by 0 ≤ i < j ≤ N − 1 and l /∈ i, j has cardinality N 2(N − 2) = N(N − 1)(N − 2) squared. For the Conway’s problem target, the count evaluates to roughly 4.7 × 10 5 binary variables before canonical fixing.

Empirical Results and Complementarity

The two formulations are not only complementary in scope but are empirically complementary on the same targets, as the cross-comparison of Tables III and IV makes explicit. The pipeline succeeds on Petersen, with 78 verified SRGs in 104 SA reads on Hgen, and on the small-N controls T5 and L2(3), but fails on Paley(13), on T6 and Clebsch within the same budget. The auxiliary-variable formulation succeeds on Clebsch, with psucc ≃ 0.95 at nreads = 105, and on Paley(13), with psucc = 0.65 at nreads = 2 × 10 5. The two formulations are therefore empirically complementary on the same targets.

Conclusion

The central result of this work is a sharp delimitation of what quadratic binary optimization can and cannot do for strongly regular graph construction. Theorem 1 shows that a quadratic function of the edge variables whose global minimizers are exactly the labeled SRGs exists only when every k-regular graph is already the target, which happens for the perfect matchings, cocktail-party graphs and the pentagon, and for no other feasible parameter set. The result covers arbitrary quadratics, symmetric or not, and therefore closes the door on any hope of an ingenious auxiliary-free encoding. In particular, we have formally established that the 99-vertex graph of Conway’s 1000 problem cannot be obtained, whether or not it exists, as the exact ground-state set of any QUBO over the 4851 edge variables. The proof is a short symmetry argument. The two routes are not only complementary in scope but are empirically complementary on the same targets, as the cross-comparison of Tables III and IV makes explicit.

Improvements for AI systems

Pure QUBO route with generate-prune-verify pipeline: The system can generate k-regular candidates using Stage I QUBO with symmetry breaking, postselect them via a Max Clique instance guided by the Hoffman bound, and certify survivors with a classical O(N3) test to reduce the search space while staying within pure QUBO.
Auxiliary variable route for exact construction: The system can solve the full SRG problem by quadratizing the quartic penalty through Rosenberg auxiliary variables, resulting in a single QUBO instance whose global minimizers correspond one-to-one with target SRG adjacency matrices.
Hybrid quantum-classical division of labor: The system can deploy a hybrid approach where a quantum or quantum inspired sampler handles Stage I candidate generation, while the Hoffman filter and algebraic certification run classically, which is advantageous in regimes where quantum sampling outperforms classical alternatives.
Parameter selection guided by feasibility table: The system can select the appropriate route based on target family discriminativeness, choosing the pipeline route for informative bounds like Petersen and T5, or the auxiliary formulation for targets like Paley(13) and Clebsch where the pipeline fails due to structural constraints.