Exploiting the Regular Structure of Modern Quantum Architectures for Compiling and Optimizing Programs with Permutable Operators

Many near-term quantum algorithms are built from two-qubit operations that all commute, so a compiler is free to run them in any order — a huge opportunity to route them cheaply onto hardware where only neighboring qubits can interact, but the freedom explodes the search space; this work from Rutgers exploits the regular, repeating layout of real quantum chips to find structured schedules that tile across the whole device, decomposing the giant problem into small pieces it can solve exactly and scaling to 1,024 qubits with up to 72 percent less depth and 66 percent fewer gates.

The argument in one glance

Problem

Commuting quantum operators give freedom that is hard to use

A critical feature of many of today's quantum programs is that their two-qubit operators are permutable — they commute, so they can be applied in any order. On hardware where only neighboring qubits can interact, the order deeply affects how many expensive routing operations are needed. The reordering freedom is thus a real optimization opportunity, but it piles an extra combinatorial degree of freedom onto an already hard compilation problem.
What people did

Fix an order, or search over orderings

Compilers take one of two routes. The simple route fixes an order for the operators and then solves the usual mapping-and-routing problem, inserting SWAP gates to bring distant qubits together. The ambitious route searches over possible orderings with solvers or heuristics, hoping to find one that routes cheaply.
Why it fell short

Fixing the order wastes savings; searching does not scale

Fixing the order throws away the very flexibility that could have cut the routing cost, leaving substantial savings on the table. Searching over orderings can find better schedules, but the search space grows explosively with the number of qubits and operators, so these methods bog down and cannot handle the hundreds or thousands of qubits that modern quantum architectures now offer. Neither approach delivers high-quality compilation that scales.
This paper's idea

Find structured, tileable solutions from the hardware's regularity

This work exploits the fact that modern quantum chips have a regular, repeating layout. It proposes a general methodology that finds structured solutions which scale, by breaking the complex compilation into two subproblems each solvable at small scale and then composing them across the regular architecture. It further adapts the structured method to practical realities — sparse problem graphs that do not fill the lattice, and hardware where some qubits and links are noisier than others — scaling to 1,024 qubits with large reductions in depth and gate count.

Why this problem is worth solving

The routing cost this work attacks comes from a basic mismatch between programs and machines.

A quantum program is written as if any qubit can interact with any other, but a real quantum chip has a fixed coupling graph: each qubit is wired to only a few physical neighbors, and a two-qubit gate can be applied directly only between adjacent qubits. IBM’s machines use a heavy-hexagon lattice and Google’s use a grid, and in both, most pairs of qubits are not neighbors. To perform a two-qubit operation between qubits that are far apart on the chip, the compiler must first move them next to each other by inserting SWAP gates, each of which physically exchanges the states of two adjacent qubits. Those SWAPs are pure overhead: they add to the circuit’s depth, which is how long the computation takes, and to its total gate count, and on today’s noisy hardware every extra gate is another chance for an error to creep in and corrupt the result. Because near-term quantum devices can only run shallow, low-gate-count circuits before noise overwhelms the signal, minimizing this routing overhead is not a minor tuning concern — it often decides whether a program produces a usable answer at all. This is the qubit-mapping-and-routing problem, and it is NP-hard in general, which is why so much compiler effort goes into it.

What makes this particular class of programs special is a property that is simultaneously a blessing and a trap.

In an important family of quantum algorithms — including the Quantum Approximate Optimization Algorithm used for combinatorial optimization, and more broadly the simulation of Ising-style Hamiltonians — the core of the computation is a large set of two-qubit operators, one for each edge of a problem graph, and all of these operators commute with one another. Commuting means the final result is identical no matter what order they are applied in. For a compiler this is a genuine gift, because the order is now a free variable it can choose to its advantage: a well-chosen order can bring the qubits that need to interact next to each other naturally, slashing the number of SWAPs needed. But the same freedom is a trap. Every ordering is a different compilation instance, and the number of orderings explodes with the size of the program, so the compiler now faces not just the hard mapping-and-routing problem but that problem multiplied by an enormous space of possible orders. Turning this extra degree of freedom from a combinatorial burden into a source of scalable, structured savings is exactly the challenge the paper takes on.

What people did before, and where it broke

Fix the operator order. Commit to one order for the commuting two-qubit operators, then solve the standard mapping-and-routing problem for it. Where it broke. It ignores the reordering freedom entirely, so it inserts far more SWAP gates than necessary and leaves large depth and gate-count savings unrealized.
Search over orderings with solvers or heuristics. Treat the order as something to optimize, exploring many orderings to find one that routes cheaply. Where it broke. The space of orderings grows explosively with qubit and operator count, so the search bogs down and cannot handle the hundreds or thousands of qubits on modern devices.
General mapping-and-routing compilers. Apply strong generic qubit-routing techniques without exploiting the program’s commutativity or the hardware’s regularity. Where it broke. By treating each instance as unstructured, they miss the repeating patterns that would let a solution scale, and re-solve essentially the same routing problem across the chip.
The gap. No approach used the reordering freedom in a way that scaled: something that turns the commutativity of the operators and the regularity of the hardware into a structured solution reusable across a large device, rather than an ever-larger search. Producing such structured, scalable schedules is what this work sets out to do.

How the structured method works

From an explosive search to a tileable structured schedule

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Turn the freedom to reorder into a resource, not a burden. The commuting operators can be applied in any order, and rather than either ignoring that or drowning in the search space it creates, the method treats the order as something to shape deliberately so that interacting qubits fall next to each other. Exploiting the fact that a computation’s pieces are independent enough to be reordered freely, and using that latitude to schedule them for efficiency instead of accepting a fixed sequence, is the same instinct the automatic-parallelism work covered elsewhere on this site follows, treating loop iterations whose order does not matter as a scheduling opportunity to be arranged for the hardware rather than a fixed program to be executed as written.

Decompose the intractable whole into small pieces you can solve well. A compilation problem over a thousand qubits is hopeless to solve directly, so the method breaks it into two subproblems each small enough to solve near-exactly, then composes their solutions. Reducing a large, structured problem to small well-understood pieces whose answers combine, instead of attacking the monolith, is exactly the strategy the concurrency data-structure work covered elsewhere on this site uses, decomposing a big reachability question into per-chain pieces small enough to handle with a standard primitive and then stitching them together.

Exploit that the hardware repeats itself, and reuse one solution everywhere. Because modern chips tile the same connectivity pattern across the whole device, a schedule crafted for one patch is valid for every patch, so the compiler produces one structured solution and lays it down across the lattice. Finding the repeated structural unit and reusing a single solution across all its copies, rather than solving each instance afresh, is the same move the circuit-deduplication work covered elsewhere on this site makes, recognizing that a design is built of identical repeated modules and generating one shared answer that serves them all.

Following a program through the structured compiler

Compiling a commuting-operator program onto a regular chip

Tracing the flow shows structure replacing search at every step.

Step 1 of 5

Start from a set of commuting two-qubit operators

The program is a large collection of two-qubit operators, one per edge of a problem graph, that all commute. The compiler is free to choose any order for them, and must place the program's qubits onto the chip and route non-adjacent interactions.

This is the structure of QAOA and Ising-style Hamiltonian simulation.

Why it works

Reordering brings interactions close. Only neighboring qubits can interact, so distant operations need SWAP routing → but commuting operators can be placed in any order → so the compiler can choose an order that brings interacting qubits together and avoids most SWAPs.
Regularity makes a local answer global. Real chips repeat the same connectivity pattern across the device → so a schedule found for one small patch applies to every other patch → so the compiler avoids re-solving the routing problem everywhere.
Small scale makes quality reachable. The full compilation over a thousand qubits is intractable to solve directly → but it decomposes into two subproblems each solvable at small scale → so near-exact, high-quality solutions become reachable and then compose across the chip.
Structure replaces search. The composed solution is a repeating pattern → so it tiles across the lattice with no global search → so the method scales to over a thousand qubits where search-based compilers stall.
Adaptation keeps it real. Real problems are sparse and real hardware is unevenly noisy → but the structured method is adapted to skip missing interactions and avoid noisy regions → so it still cuts depth and gate count and improves solution quality on actual devices.

What it costs (trade-offs and scope)

It targets programs with permutable operators. The whole approach rests on the two-qubit operators commuting, as in QAOA and Ising-style Hamiltonian simulation; programs without that structure gain nothing from the reordering freedom it exploits.
It leans on hardware regularity. The tiling works because modern chips repeat a fixed lattice; irregular or highly custom topologies would weaken the structured, reusable solution.
Sparse and irregular inputs need adaptation. Real problem graphs rarely match the regular lattice exactly, so the method must handle the mismatch, and heavily irregular graphs give back some of the benefit.
Structured is not always globally optimal. Decomposing into small subproblems and tiling trades a guarantee of the single best schedule for one that scales; a bespoke search might still do better on a small circuit.
Noise handling is necessarily heuristic. Adapting to hardware noise variability improves real-device results, but noise is dynamic and imperfectly known, so the gains depend on how well the noise profile is captured at compile time.
The reported gains are on specific benchmarks and devices. The depth and gate-count reductions are against a particular baseline on IBM and Google coupling graphs, and the real-hardware energy result is on one IBM device; other problems, baselines, or machines would need their own evaluation.

The evaluation

Three ways to compile commuting-operator quantum programs

Property	Fixed order	Search over orderings
Uses the reordering freedom		Yes, by brute-force search
Scales to	Large chips, but leaves savings
Depth and gate count	Baseline	Better, but not scalable
On real noisy hardware	Baseline	Impractical at scale

Three ways to compile programs whose two-qubit operators commute, from the paper's reported results on IBM and Google coupling graphs for up to 1,024 qubits. By exploiting the hardware's regular structure to build a tileable structured schedule rather than searching over orderings, the method reduces circuit depth by up to 72 percent and gate count by up to 66 percent versus the baseline, and real experiments on the IBM Mumbai device find a better expected minimal energy than the state-of-the-art baseline. (This explainer is drawn from the paper's abstract and standard background on quantum compilation; the full text was not available.)Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The appeal of this work is that it converts a liability into an asset: the freedom to reorder commuting operators, which makes compilation combinatorially harder, becomes the very thing that lets a structured, hardware-aware schedule be built and reused across a whole chip. By decomposing the intractable full problem into two small-scale subproblems and tiling their solution over the regular lattice of modern devices, it scales to 1,024 qubits — far beyond search-based methods — and reports large reductions in depth (up to 72 percent) and gate count (up to 66 percent), plus better solution quality on a real IBM device. Read the result with its scope. The method is specific to programs with permutable operators (QAOA and Ising-style simulation) and to hardware with a regular, repeating layout; it trades the guarantee of an optimal schedule for one that scales, so a dedicated search might still win on a small circuit; and its handling of sparse problem graphs and hardware noise is adaptive and imperfect, since real noise is dynamic and only partly known at compile time. This page is written from the paper’s abstract and standard background on quantum compilation, because the full text was behind an inaccessible paywall; the method is described only at the level the abstract states — a two-subproblem decomposition exploiting hardware regularity — and the specific internal construction should be confirmed against the paper itself.

Background

Why compilation is where near-term quantum lives or dies

It helps to see this work against the reality of near-term quantum computing. Today’s machines have limited qubit connectivity and are noisy enough that only shallow, low-gate-count circuits survive long enough to give a useful answer, which puts enormous weight on the compiler: how well a program is mapped, ordered, and routed onto the hardware often decides whether it works at all. That is why so much research targets squeezing depth and gate count out of exactly the algorithms, like QAOA, that people hope to run on this generation of devices. The work on reducing QAOA’s cost covered elsewhere on this site pushes the same goal from the algorithm side, cutting the resources a QAOA instance demands so it fits within what noisy hardware can sustain, where this paper cuts them from the compilation side. The broad lesson is that in the near term, the scarce resource is not qubits but reliable circuit depth, and progress comes as much from clever compilers and problem reductions that respect the hardware’s structure and noise as from building bigger machines — the software and the silicon have to meet in the middle.

If you remember only three things

1. A large class of important quantum programs — the Quantum Approximate Optimization Algorithm and Ising-style Hamiltonian simulation — is built from two-qubit operators that all commute, so a compiler may apply them in any order. On hardware where only neighboring qubits can interact, that order strongly affects how many SWAP routing gates are needed (which add depth and error), making the freedom a real optimization opportunity. But it is also a combinatorial trap: it multiplies the already NP-hard mapping-and-routing problem by an exploding space of orderings, so fixing the order wastes savings while searching over orderings does not scale.
2. This work proposes a general methodology that finds structured, scalable solutions by exploiting the regular, repeating layout of modern quantum chips (IBM heavy-hexagon, Google grid). It breaks the complex compilation into two subproblems each solvable at small scale, composes them, and tiles the resulting structured pattern across the whole device rather than searching the full machine. It then adapts the structured method to practical realities — sparse problem graphs that do not fill the lattice, and hardware where some qubits and links are noisier than others — so it holds up on real devices.
3. Evaluated on IBM and Google coupling graphs for up to 1,024 qubits, the method reduces circuit depth by up to 72 percent and gate count by up to 66 percent versus the baseline, and real experiments on the IBM Mumbai device find a better expected minimal energy than the state-of-the-art baseline. Its scope: it needs permutable operators and regular hardware, trades optimality for scalability (a bespoke search might win on small circuits), handles sparsity and noise heuristically, and its numbers are tied to specific benchmarks and devices. This explainer is written from the abstract and standard background, as the full text was unavailable.

Check yourself

Check your understanding

1. Why is the freedom to reorder commuting operators both an opportunity and a challenge for a quantum compiler?
2. What is the key insight the paper exploits to make compilation scale?
3. How does the structured method turn an intractable problem into a scalable one?
4. Which statement best reflects the results and scope of this work?

Sources

The paper is “Exploiting the Regular Structure of Modern Quantum Architectures for Compiling and Optimizing Programs with Permutable Operators” by Yuwei Jin, Fei Hua, Yanhao Chen, Ari B. Hayes, Chi Zhang, and Eddy Z. Zhang, published at ASPLOS 2023, DOI 10.1145/3623278.3624751. The authors are at Rutgers University.

This explainer is marked as a draft because the full text was not accessible: the paper is gold open access on the ACM Digital Library, but that page was protected by an anti-bot challenge that blocked automated retrieval, and no arXiv preprint, author-hosted copy, or repository version could be found. The account above is written from the paper’s published abstract together with standard, well-established background on quantum compilation — the qubit-mapping-and-routing problem and SWAP overhead, the limited connectivity and noise of near-term (NISQ) hardware, the regular coupling graphs of IBM (heavy-hexagon) and Google (grid) devices, and the commuting-operator structure of QAOA and Ising-style Hamiltonian simulation. The specific claims attributed to the paper — that today’s quantum circuits have permutable two-qubit operators whose ordering freedom is both an opportunity and a challenge, that the method finds structured scalable solutions by breaking the compilation into two subproblems solvable at small scale, that it is adapted for the sparsity of input problem graphs and the noise variability of real hardware, that it is evaluated on IBM and Google coupling graphs up to 1,024 qubits with up to 72 percent depth reduction and 66 percent gate-count reduction, and that real experiments on IBM Mumbai find a better expected minimal energy than the state-of-the-art baseline — come directly from the abstract. The precise internal construction (what the two subproblems are and how they compose and tile) is described only at the level the abstract supports and should be confirmed against the full paper.