Structure-Aware Routing of QAOA Cost Layers on Thin Hardware

Quantum chips can only apply a two-qubit gate between physically neighboring qubits. Before an optimization circuit can run, a compiler must therefore insert SWAP gates that move qubits next to each other. In the Quantum Approximate Optimization Algorithm (QAOA, a quantum circuit with a few tunable angles whose output is scored and re-tuned by a classical optimizer), the costly part is the "cost layer." It applies one two-qubit gate per edge of the problem graph, and because these gates commute, they can run in any order. Finding the shallowest SWAP schedule for such a layer is NP-hard. Exact integer programs only reach small chips, and generic heuristics waste depth.

We propose that the shape of the problem graph, measured against the shape of the chip, determines how hard this routing is. Concretely, when the chip is a thin strip of height $h$ and the problem graph can be laid out along the strip with bandwidth $b$ (every edge joins vertices at most $b$ apart in some ordering), a sliding-window dynamic program can compute a depth-optimal schedule in time linear in the number of qubits and exponential only in $h$ and $b$. We expect this tractability to break sharply once a few long-range edges appear, much as Dominating Set flips from tractable to hard when one forbidden pattern is relaxed. We also expect the depth savings to matter for the classical optimization loop only within a measurable window.

Core Claim and What Is New

The claim has three parts. The first is algorithmic: depth-optimal routing of a commuting cost layer is fixed-parameter tractable in $(h, b)$ on $h \times n$ strip hardware. The second is a boundary: parameterized by hardware height $h$ alone, the problem is hard. The third is empirical: the depth gap between our exact schedules and standard routers decides whether the QAOA loop can absorb routing noise. Here "fixed-parameter tractable" means the running time is $f(h,b)\cdot n^{O(1)}$, so the exponential cost depends only on the parameters, not on the instance size $n$.

Three lines of prior work are closest. Optimized Qubit Routing for Commuting Gates via Integer Programming proves commuting-gate routing NP-hard and solves it exactly as a "token meeting" integer program. It supplies our problem formulation and our exactness oracle, but it does not scale and explicitly leaves approximability on specific hardware graphs open. Algorithmic Theory of Qubit Routing gives a fixed-parameter algorithm in gate count $k$ and a closed-form "gaps minus crossings" formula for disjoint gates on a path. Its parameter is unbounded for a full cost layer, and its exact results stop at one-dimensional hardware. Parallel token swapping for qubit routing gives constant-factor approximations on cycles, stars, and $h \times n$ grids. It treats routing as one isolated permutation rather than as "every edge must meet once." No paper in this set parameterizes cost-layer routing by structural width of the problem graph relative to the chip, and none connects compiled depth to the behavior of the variational loop.

The logic lower bounds play a constraining role rather than supplying a method. Lower bounds on the complexity of MSO1 model-checking shows that checking properties in monadic second-order logic over vertex sets is not even in XP on subgraph-closed classes whose treewidth grows polylogarithmically, assuming the non-uniform Exponential Time Hypothesis. Treewidth measures how tree-like a graph is. Schedule feasibility within $D$ layers is naturally a property of the time-expanded hardware graph, which has $D$ copies of the chip linked over time. For 2D grids, the time-expanded graphs fall squarely inside such hard classes, so a generic Courcelle-style "write it in logic and run the tree-decomposition algorithm" approach is ruled out on full 2D chips. On a strip of height $h$ with a window of width $O(b)$, the windowed time-expanded graph has treewidth bounded by a function of $(h, b, D)$. Courcelle's theorem then guarantees tractability in principle, and our dynamic program makes it practical. We do not claim the logic lower bounds transfer automatically to routing, because they concern arbitrary formulas. A direct reduction is part of the work.

Research Program

The algorithmic core fixes a linear order of the problem graph and sweeps a window of width $O(b)$ columns along the strip. The state is the arrangement of the qubits inside the window, together with the set of edges among them that have already met. Transitions apply one layer of disjoint parallel SWAPs plus the cost gates that the layer makes adjacent. A qubit can leave the window only after all of its edges have been executed. This gives $n \cdot g(h,b)$ states, where $g(h,b)$ is a function of $h$ and $b$ only that bounds the number of window states, and shortest-path search over these states yields the optimal depth among window-respecting schedules.

We will then prove two things. First, window-respecting schedules lose at most an additive $O(b)$ layers against unrestricted optima. The plan is an exchange argument: any qubit that travels further than the window can be rerouted. Second, minimizing depth parameterized by $h$ alone is W[1]-hard. W[1]-hardness is the standard evidence that no algorithm of the form $f(h)\cdot n^{O(1)}$ exists. The planned reduction encodes grid tiling into a strip of height $h$, reusing the grid-embedding gadgets from Lower Bounds on the Complexity of MSO_1 Model-Checking. If the reduction fails, we will report the XP algorithm we can prove, with running time $n^{f(h)}$, and the open status honestly.

Second, we study the boundary empirically, in the spirit of the "one extra edge" dichotomy of Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. Starting from bandwidth-$b$ problem graphs, we add $m$ random long-range edges. We then measure how both optimal depth and solver time grow with $m$. A simple extension handles $m$ extra edges by solving the bandwidth-bounded part with the dynamic program and finishing the long edges with an inserted line swap network. We test whether this extension stays within a constant factor of the integer-program optimum.

Third, we close the loop with the optimizer. Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware argues that routed QAOA on dense problems needs two-qubit fidelities near 99.99% to help at all. In contrast, Quantum algorithms for electronic structure calculations: Particle-hole Hamiltonian and optimized wave-function expansions and Realization of a quantum autoencoder for lossless compression of quantum data report that variational loops absorb systematic errors. Those two claims meet at depth: SWAP noise is stochastic rather than systematic, so we predict the loop does not absorb it, and that approximation ratio tracks compiled two-qubit depth almost one-for-one.

Baselines

The naive reference is the line swap network of Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware. It routes every pair on a line in about $n$ layers, whatever the problem graph looks like, and it is the strongest structure-blind schedule for commuting layers. We run it on the same strips and orderings. Beating it means lower depth on bounded-bandwidth graphs, together with a demonstration that the method falls back to its depth on dense graphs. No reported depth number for this strategy was found on Lacuna, so we will measure it ourselves.

The strongest exact competitor is the token-meeting integer program of Optimized Qubit Routing for Commuting Gates via Integer Programming. It reports "up to 10x fewer swaps and 3x shallower circuits" than other methods. We reimplement it with the same solver, thread count, and per-instance time limit as our dynamic program. On instances it solves to optimality, our depth must match it within the proven additive window slack. Beating it means solving instances of 100 or more qubits within the time limit where it times out.

The strongest scalable heuristics are Route-Forcing, from Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures, and Duostra, from Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits. Route-Forcing reports a 4.7× depth reduction and a 3.7× compile speedup over SABRE, at 1.3× more SWAPs. Duostra reports a 21.75% average mapping-cost improvement over the best of QMAP, t|ket⟩, Qiskit, and SABRE on circuits above 50 qubits. Both receive the cost layer as a circuit, and we let them exploit commutation where their interface allows. We compare depth and SWAP count at matched compile-time budgets.

The ablation removes the problem-graph ordering. We run the same window dynamic program with a random linear order instead of a bandwidth-minimizing one, which isolates whether the structural fit, rather than the search itself, produces the gains.

Why not just…?

Why not just use the line swap network for everything? It is the real threat on dense or expander-like problem graphs, where bandwidth is close to $n$ and our method reduces to it. Random 3-regular graphs have large bandwidth, so we predict essentially no gain there and include them as a negative control. The proposal's value rests on showing gains that grow with $n/b$ on structured graphs. If the measured gain stays flat, the claim is refuted.

Why not just run SABRE-style heuristics and accept the depth? The integer-program results show such heuristics can produce up to 10× more SWAPs on commuting layers. Our loop experiment asks whether that extra depth changes optimizer outcomes. If heuristic depth turns out to be within a few percent of optimal on strips, we will say the exact method is unnecessary in practice.

Why not just solve the problem classically, since bounded-bandwidth graphs have bounded treewidth? This is correct. Max-Cut on such graphs falls to classical dynamic programming, and we do not claim quantum advantage on them. We turn the fact into a tool. These instances come with exact optima at hundreds of qubits, so QAOA output under realistic routing can be scored exactly well beyond brute-force sizes. The compiler result itself is independent of the problem objective.

Why not just extend the integer program with symmetry breaking? Its reported solver speedups of up to 12× do not change the exponential scaling in $n$. Our scaling experiment measures the crossover point directly.

Proposed Experiments

The first experiment tests exactness. On grid and heavy-hex strip instances in the style of the integer-program benchmark, with up to the program's solvable size, we compare optimal depths. This checks the additive-slack theorem.

The second experiment tests scaling. On $h \in \{1,2,3,4\}$ strips with $n$ up to 1,000, and on heavy-hex chips cut into thin strips, we use problem graphs with bandwidth $b \in \{2,4,8\}$, planar lattices, and random 3-regular graphs. We report depth, SWAPs, and compile time against all baselines, and plot depth against $n/b$.

The third experiment probes the boundary with the long-edge interpolation described above, measuring depth and runtime as $m$ grows. A sharp knee would support the razor's-edge claim. Smooth degradation would refute it.

The fourth experiment is the decisive check on the loop. We run noisy simulations of QAOA with $p=1,2$ under depolarizing two-qubit noise. Up to about 25 qubits we use density matrices. Beyond that we compute light-cone expectation values with Pauli noise. We use the 3-regular Max-Cut protocol of Benchmarking variational quantum algorithms for combinatorial optimization in practice: 25 instances per size, 10 initializations, COBYLA, and a cap of $10^6$ evaluations. That paper reports success above 75% at $N=11$ and an advantage over random sampling in roughly 95% of instances at $N=31$, with the margin over greedy search shrinking by $N=61$. We add bounded-bandwidth instances scored against exact classical optima. For each router's compiled circuit we record approximation ratio and its gap to greedy search and random sampling.

The proposal succeeds if two things hold on structured instances: depth-optimal routing keeps QAOA above greedy search at sizes where heuristic routing falls below it, and the effect vanishes on random 3-regular graphs as predicted.