Sequential QUBO Steps for Binary Topology Optimization

Topology optimization decides where to put material inside a design region, for example to make the stiffest bracket from a fixed amount of metal. The standard method, SIMP (Solid Isotropic Material with Penalization), treats each element's material density as a continuous number between 0 and 1. It improves the design using gradients, runs a full finite-element simulation at every step, and pushes densities toward 0 or 1 over hundreds of iterations. Fast neural generators such as OAT, NITO and DOM now produce a good first guess in under a second. All three still need "5–10 steps of traditional SIMP optimization" afterwards to reach engineering precision. So the remaining cost sits in a short, simulation-bound polishing loop that works on a continuous stand-in for what is really a yes/no material decision.

We propose to replace each polishing step with a quadratic unconstrained binary optimization (QUBO) problem, and to build that problem from the physics rather than from a learned model. A QUBO is a problem of choosing a 0/1 vector to minimize a quadratic score. Recent GPU solvers handle QUBOs with thousands of variables in milliseconds. Each step works as follows. We factorize the stiffness matrix of the current binary design once. We reuse that factorization to compute, cheaply, how removing or adding pairs of elements jointly changes stiffness. We then hand the resulting local quadratic model to a millisecond solver, which flips many elements at once. The bet is that a step which sees element-to-element interactions and searches binary layouts directly gets further per expensive simulation than a SIMP step or a sensitivity-sorting step does.

Core Claim

Use linear interpolation of stiffness between void and solid, $K(x)=\sum_e(\rho_{\min}+(1-\rho_{\min})x_e)K_e$, with $x\in\{0,1\}^n$ marking material. Then the compliance $C(x)=F^\top K(x)^{-1}F$ (compliance is the inverse of stiffness, and $F$ is the load) has an exact and cheap second derivative at the current design $x^k$ with displacement $u$:

$$H_{ij}=2\,(K_i u)^\top K(x^k)^{-1}(K_j u),\qquad g_i=-u^\top K_i u,$$

where $K_i=\partial K/\partial x_i$ is the scaled element stiffness. Each column of $H$ costs one back-substitution with a factorization that already exists, not a new factorization. The off-diagonal entries measure load-path interaction. Removing two elements that share a load path costs more than the sum of removing each one alone. First-order methods cannot see this. SIMP's method of moving asymptotes (MMA) uses a separable convex approximation and discards these couplings, and sensitivity-thresholding methods discard them too.

Each outer step then solves

$$\min_{x\in\{0,1\}^{m}}\; g^\top(x-x^k)+\tfrac12(x-x^k)^\top H(x-x^k)+\beta\sum_{(i,j)}w_{ij}(x_i-x_j)^2+\mu\sum_e(x_e-x^k_e)^2+\lambda\Big(\sum_e x_e-V^*\Big).$$

The variables are restricted to a candidate band of $m$ elements near the current material boundary. The $\beta$ term is the usual density-filter kernel written as neighbour couplings, and it enforces a minimum feature size. The $\mu$ term is a trust region. Because $x_e$ is binary, it reduces to a linear term that penalizes flips, so it adds no auxiliary variables. For the volume constraint we do not use the squared penalty $\gamma(\sum x-V^*)^2$ that QUBO compilers normally apply. That penalty makes $Q$ dense, and it distorts the energy landscape exactly as the file's QUBO literature warns. Instead we bisect on the linear multiplier $\lambda$, as the optimality-criteria method does, and re-solve the QUBO for each trial value. That is affordable only because each solve takes milliseconds.

The expected result is that this sequential QUBO scheme reaches a given compliance with measurably fewer factorizations than SIMP/MMA or sensitivity thresholding. We also expect it to outperform both when it polishes a neural warm start. Its output is binary by construction, with no loss from final thresholding.

Relation to Prior Work

Three existing papers bring binary quadratic formulations into structural design, and each shows a boundary we must cross.

Matsumori et al. fit a factorization machine, which is a quadratic model in binary variables, to finite-element results. They optimized it with quantum or simulated annealing to place 17–27 mounting screws. Their quadratic model is learned from samples. Ours is derived exactly from the governing equations at each iterate, which is what allows thousands of variables.

The symbolic quantum-annealing truss study compiled stiffness symbolically into a QUBO. It collapsed at 12 variables because inverting the symbolic stiffness matrix exploded, and the annealer found the optimum in only one of ten trials. That negative result constrains our design: global symbolic compilation is ruled out. We only ever need a numerical, local, second-order model around a known design, so no symbolic inverse ever appears.

SOLO ran simulated annealing on a neural surrogate and found fluid-structure designs that MMA missed. This motivates the claim that binary global search can escape the local traps of gradient methods. SOLO never writes an explicit quadratic, however, and it retrains a network online.

Two further lines of work supply parts of our method. Rashed et al. argue that adjoint sensitivity fields are the information-optimal signal for binary topology, and they fed that signal to a transformer. We place the same signal in the linear term $g$ and add the curvature term $H$. Giannone et al. replace online simulation with Green's-function kernels. Our $H$ is precisely a Green's function, $K^{-1}$ sandwiched between element loads, evaluated exactly on the current mesh rather than approximated from data.

Gabor et al. contribute the order-preserving principle: a QUBO need only preserve where the minimum lies, not the exact function values. That principle is why a local, truncated model is acceptable inside a trust region.

On the solver side, AMFD, which descends a mean-field energy under annealing on a GPU, and VCM, a one-shot neural QUBO classifier, supply the millisecond solves. They have only ever been run on abstract benchmarks such as Max-Cut and ORLIB.

Research Program

The first part is the Hessian construction. For $64\times64$ meshes and a candidate band of $m$ up to about 2,000 elements, we compute $H$ exactly from $m$ back-substitutions. For $256\times256$ meshes we compare two cheaper routes. One is a randomized low-rank sketch of $H$ with $r\ll m$ back-substitutions. The other is truncating $H$ to elements within a fixed radius, which yields a sparse coupling matrix of the kind annealing hardware prefers. We will report the cost of building $H$ in units of "factorization equivalents," so that it is never hidden.

Because compliance under linear interpolation is convex in the relaxed variables, $H$ is positive semidefinite. The whole difficulty therefore sits in the binary constraint. That is exactly what separates a QUBO step from a continuous Newton step, and the ablations below are built around it.

The second part is the solver loop. Each outer iteration consists of one factorization, the construction of $H$, and a bisection on $\lambda$ with roughly ten AMFD solves. Then the flipped design is accepted or rejected against the true compliance, and the trust-region weight $\mu$ is adjusted as in standard trust-region methods. We run the loop both from a solid or uniform start and from the thresholded output of OAT or NITO.

The third part is analysis. We will measure how often the QUBO-predicted compliance change ranks candidate designs in the same order as the true change. This checks the order-preserving property directly. We will also check whether floating material appears. Disconnected elements carry near-zero $g$, so the solver should remove them, but this has to be verified.

Baselines

The naive reference point is BESO-style sensitivity thresholding (bi-directional evolutionary structural optimization). It keeps the linear term $g$ and the volume multiplier and drops $H$ and the filter couplings, so each step simply sorts elements by sensitivity. This is exactly our method with the quadratic term removed, so it is also the main ablation isolating the proposal's key ingredient. It uses the same factorization per step, the same candidate band and the same trust-region schedule. Beating it means reaching the same compliance in at least 30% fewer factorizations, or reaching lower compliance at equal factorizations, on the 33k TopoDiff test splits.

The strongest classical competitor is SIMP with MMA, using a density filter implemented as in the k-d-tree filter work, continuation on the penalty, and a final threshold. It is the method that generated every dataset here, and it is what the neural methods fall back on. We give it the same meshes, the same filter radius, the same volume fraction, and its move limit and continuation schedule tuned on a held-out split with the same tuning budget as our $\mu$ and $\beta$. It is scored after thresholding to binary, because that is the design actually built. Beating it means matching its final binary compliance within 1% using fewer factorizations. As a secondary target, we would find strictly better designs on a share of cases comparable to the "approximately 19% of test cases" in which NITO reports its refined output beating SIMP. No reported number for SIMP's iteration count on these benchmarks was found on Lacuna, so we measure it ourselves.

The strongest overall pipeline is OAT followed by 5–10 SIMP steps. OAT reports "sub-1 second" inference, a "~135x speedup" over SIMP at $256\times256$, and mean compliance error reduced "up to 90%" relative to earlier models. We run the released model on OpenTO test cases and then apply either SIMP polishing or our QUBO steps. Everything is matched by number of factorizations, and both routes are scored on binary compliance. Beating it means our 1–3 QUBO steps give lower binary compliance than 5–10 SIMP steps. Among discrete-output generators, Bernoulli flow matching reports a 33% mean compliance error reduction versus TopoDiff at "~3.2 seconds," which serves as the reference for no polishing at all.

A solver ablation swaps AMFD for Gurobi on the identical QUBO under a 1-second limit. This separates the value of the formulation from the value of the solver. VCM reports that it rivals 1-second Gurobi on large instances, and AMFD reports 99.4% accuracy on G72 Max-Cut faster than Gurobi. Neither result has been tested on physics-derived $Q$ matrices.

Why not just…?

Why not just use a continuous second-order method, since you already have the Hessian? This is the most serious threat. The relaxed compliance is convex, so a projected Newton or box-constrained quadratic step with the same $H$, rounded to binary, might capture most of the gain. We include exactly this as a baseline: same $g$, $H$, filter and volume multiplier, solved over $[0,1]^m$ and then thresholded. If it matches the QUBO step, the contribution shrinks to "use exact curvature from a reused factorization," and binary search adds nothing. We would report that honestly. Our reason to expect a gap is that rounding a relaxed solution breaks the joint flips that the couplings reward. SOLO's discovery of gap-containing designs that MMA missed (Deng et al.) is indirect evidence that binary search finds designs relaxations do not.

Why not just take more SIMP polishing steps, or trust the neural generator alone? Extra SIMP steps cost one factorization each and still end in a thresholding step that shifts compliance. Neural outputs alone carry the physics gap that OAT, NITO and DOM all acknowledge by prescribing polishing. The warm-start experiment settles this directly, because it compares binary compliance against matched factorization budgets.

Why not just run simulated annealing or a genetic algorithm on the true compliance? Every candidate those methods evaluate requires a new simulation. That is the "millions of FEM simulations" cost that motivated SOLO. Our QUBO lets the solver evaluate millions of candidate flips against a quadratic model that costs one factorization to build. We will also run simulated annealing on our QUBO in place of AMFD, to show that the gain comes from the model and not from one particular solver.

Why not just use the standard squared volume penalty? It works in principle, but it adds a dense rank-one coupling and a weight $\gamma$ that must be tuned. We run it head to head against $\lambda$-bisection, and we report both the rate of volume violations and the final compliance across a sweep of $\gamma$.

Proposed Experiments

We run four experiments. The first establishes correctness at small scale. On SOLO's $5\times5$ compliance grid, all $2^{25}$ binary designs can be enumerated, so we check whether sequential QUBO steps reach the global optimum, and how often BESO and thresholded SIMP do not. On the $11\times11$ grid we compare against SOLO's reported designs.

The second covers the main cost-quality curves on the TopoDiff 33k benchmark at $64\times64$. We use both Level 1 (unseen combinations of known conditions) and Level 2 (out-of-distribution boundary conditions). We plot binary compliance relative to the SIMP reference against cumulative factorization equivalents, and against wall-clock time on one GPU. We also report floating-material rate, using TopoDiff's definition, under which GANs fail about 68% of the time and TopoDiff about 6%.

The third tests scale and warm starts on OpenTO and on the multi-fidelity SIMP dataset at $256\times256$. Here we compare the exact, sketched and radius-truncated versions of $H$, and we compare QUBO polishing with SIMP polishing of OAT outputs.

The decisive checks come from the ablations. If removing $H$ (BESO) costs little, or if the relaxed-Newton-plus-rounding baseline matches us, the central claim fails. The claim survives only if the QUBO step beats both at matched factorization count on Level 2 cases, where local traps should matter most.

Quantum annealers are out of scope for the main results. We will, however, report the sparsity and dynamic range of the radius-truncated $Q$, since those two properties decide whether later hardware experiments are even plausible.