Strongly Regular Graph Construction via Quadratic Binary Optimization

summary

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

In short

The paper investigates whether Strongly Regular Graphs (SRGs) can be found as exact solutions to a quadratic optimization problem over edge variables (QUBO). It proves that this is only possible for three specific graph families: perfect matchings, cocktail-party graphs, and the pentagon. For all other SRGs, auxiliary variables are required. The authors propose two methods: a pure QUBO approach with a generate-prune pipeline and an auxiliary-variable route using Rosenberg quadratization.

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 used across episodes

Reinforcement Learning (RL) — explained in 26 episodes
Flow Matching — explained in 22 episodes
Quantum Fisher Information (QFI) — explained in 21 episodes
Retrieval-Augmented Generation (RAG) — explained in 21 episodes
Sample Complexity — explained in 20 episodes
Federated Learning — explained in 18 episodes

This episode discusses

The paper

Strongly Regular Graph Construction via Quadratic Binary Optimization · Read on arXiv

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

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.

More episodes

← Home