⚛️ quantum physics

Efficient Circuit Transpilation of Commuting Gates on 2D Grids

This paper introduces an adaptive transpilation scheme for commuting gate circuits on 2D grids that alternates between problem-dependent SWAP sequences and qubit layout updates, significantly reducing circuit depth and gate count to enhance the performance of QAOA on Maximum Cut and Maximum Independent Set problems.

Original authors: Sabina Drăgoi, Daniel J. Egger

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sabina Drăgoi, Daniel J. Egger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, messy puzzle on a table, but there's a catch: you can only move pieces if they are sitting right next to each other. If two pieces you need to connect are on opposite sides of the table, you have to shuffle the whole table around, swapping neighbors until they finally touch. This is exactly the headache quantum computers face when running complex optimization algorithms like QAOA.

The problem is that the "table" (the quantum hardware) is often laid out in a grid, like a checkerboard. But the "puzzle pieces" (the math problem) often only need to talk to a few specific neighbors, not everyone. The old way of solving this was to ignore the grid's extra connections and pretend the table was just a single long line. You'd shuffle pieces back and forth along that line, swapping them over and over until they could interact. It worked, but it was like taking a winding, 10-mile detour just to walk across a 1-mile field.

The Main Discovery: The "Smart Shuffle"
In this paper, the authors propose a much smarter way to shuffle the pieces. Instead of forcing everything into a single line, they invented a "greedy" strategy that looks at the specific puzzle you are trying to solve and builds a custom shuffle plan.

Think of it like a traffic controller at a busy intersection. The old method (the "linear strategy") would make every car drive in a single-file line, even if a side street was open. The new method looks at the map, sees that a car only needs to go two blocks east, and says, "Hey, you can just take the side street!" It builds a sequence of swaps that takes the shortest possible path for the specific connections needed.

What They Ruled Out
The authors explicitly argue against the idea that a "one-size-fits-all" shuffle plan is the best approach. They show that using a pre-determined, fixed pattern of swaps (like the standard "line" strategy) is often suboptimal, especially when the problem doesn't require every single piece to talk to every other piece. They also show that simply using a standard, off-the-shelf traffic controller (like the Qiskit transpiler) on a grid layout results in much deeper, messier circuits than their custom approach. They don't just suggest this; they measured it.

The Results: Shorter Paths, Better Answers
The team tested this "greedy" shuffle on two types of puzzles: finding the best way to split a group of friends into two teams (Maximum Cut) and finding the largest group of friends who don't know each other (Maximum Independent Set).

They ran simulations on graphs with up to 90 nodes (pieces). Here is what they found:

Fewer Steps: Their custom shuffle reduced the number of "swap" moves needed by about half compared to the old line-based method.
Fewer Mistakes: Because the circuit is shorter, there are fewer places for errors to sneak in. In their simulations, this allowed them to handle problems with up to 80 qubits (the puzzle pieces) that were previously too noisy to run effectively.
Better Scores: When they actually ran these circuits on real IBM quantum hardware, the results were impressive. For the "splitting teams" problem, their method improved the quality of the answer by up to 6.6%. For the "finding the group" problem, the improvement was even higher, reaching 9.3%.

How Sure Are They?
The authors are very confident in their numbers, but they are careful to distinguish between what they simulated and what they measured.

Simulations: The massive reduction in circuit depth and gate counts (up to a factor of two) comes from running thousands of simulations on classical computers. These simulations show that the new method scales much better as the problem gets bigger, growing with the square root of the size rather than the size itself.
Real Hardware: The improvements in the "approximation ratio" (the score of the solution) were measured on actual IBM quantum devices. They ran these experiments on graphs with up to 80 nodes. The results consistently showed that their greedy method outperformed the standard linear method, even without using any fancy error-correction tricks.

The Bottom Line
This paper suggests that if you want to get the most out of today's noisy quantum computers, you shouldn't just force the problem into a shape that fits the hardware. Instead, you should tailor the hardware's movements to fit the problem. By using a "greedy" approach that adapts the shuffle to the specific connections needed, they managed to squeeze more performance out of existing machines, potentially allowing us to solve bigger, more complex puzzles than we could before. It's not a magic wand that solves everything instantly, but it's a very effective way to make the tools we have work much harder and smarter.

Technical Summary: Efficient Circuit Transpilation of Commuting Gates on 2D Grids

Problem Statement

Combinatorial optimization problems, such as Maximum Cut (MC) and Maximum Independent Set (MIS), are central to many applications but are often NP-complete. The Quantum Approximate Optimization Algorithm (QAOA) offers a quantum approach to these problems by mapping them to Hamiltonians. However, practical implementation on digital quantum computers faces significant hurdles due to limited hardware connectivity.

The problem Hamiltonian $H_C$ typically induces interactions between many pairs of qubits. On hardware with restricted connectivity (e.g., 2D grids), these non-adjacent interactions must be realized using SWAP gates to route qubits into adjacent positions. This routing process increases circuit depth and accumulated error, often negating the benefits of quantum algorithms. While standard transpilation methods (like those in Qiskit) use random initial mappings and fixed routing, they often produce suboptimal circuits, particularly for sparse interaction graphs. Furthermore, pre-determined SWAP networks designed for fully connected graphs are inefficient for sparse cost Hamiltonians.

Methodology

The authors propose a transpilation scheme specifically designed for circuits consisting of blocks of commuting two-qubit gates (typical of QAOA) on two-dimensional (2D) lattice hardware. The core methodology involves alternating between constructing problem-dependent SWAP-layer sequences and updating the qubit layout.

The paper introduces and compares several strategies:

Linear Strategy ( $S_{line}, C_{line}^{grid}$ ): The state-of-the-art baseline where the 2D grid is treated as a 1D line. SWAP layers alternate between even and odd edges of the longest line in the grid.
Hybrid Strategy ( $S_{line}, C_{grid}$ ): A modification of the linear strategy that applies the line-based SWAP routing but leverages unused edges in the 2D grid to apply $R_{ZZ}$ gates (interactions) directly when possible, without altering the underlying SWAP network.
Grid Strategy ( $S_{grid}, C_{grid}$ ): A strategy utilizing a tailored basis set of SWAP layers ( $B_{grid}$ ) that alternates horizontal and vertical swaps to fully exploit 2D connectivity.
Greedy Problem-Dependent Strategy ( $S_{greedy}, C_{grid}$ ): The authors' primary contribution. This method employs a greedy search algorithm to tailor the SWAP sequence and initial qubit mapping to the specific cost Hamiltonian of the problem instance.
- Inner Loop: Uses a depth-first search (DFS) to explore a tree of reachable qubit configurations. It searches for the shortest path of SWAP layers that implements all required interactions. To manage complexity, the search is limited to a maximum depth $k_{max}$ before selecting the best partial sequence and continuing.
- Outer Loop: Iteratively updates the initial qubit mapping ( $\pi_0$ ) using a SAT-based mapping solver. If the current SWAP sequence length exceeds a reference length, the algorithm resets the search with a new initial mapping to potentially find a shorter sequence.
- Basis Set: The search utilizes an extended basis set ( $B_{extended}^{grid}$ ) including additional SWAP layers beyond the standard grid basis to trade search overhead for reduced circuit depth.

Key Contributions

Problem-Dependent Transpilation: The paper introduces a greedy algorithm that dynamically constructs SWAP strategies and initial mappings tailored to the specific interaction graph of the optimization problem, rather than relying on fixed, problem-agnostic networks.
Hybrid Baseline: The proposal of a hybrid strategy that utilizes 2D grid edges for interactions while maintaining a linear SWAP backbone, serving as an intermediate baseline.
Scalability Analysis: Theoretical and empirical demonstration that grid-based strategies, particularly the greedy approach, achieve an asymptotic $O(\sqrt{n})$ improvement in circuit complexity metrics (SWAP layers, depth, gate count) compared to linear strategies for sparse graphs, whereas linear strategies scale as $O(n)$ .
Hardware Validation: Experimental execution of QAOA circuits on IBM's rectangular-lattice hardware for problems up to 80 qubits, validating the simulation results.

Results

The authors benchmarked their approach on MC instances on Random Regular (RR) graphs (degree $d=3$ ) and MIS instances on Erdős–Rényi (ER) graphs (edge probability $q=0.08$ ).

Circuit Complexity: Compared to standard methods (including the linear strategy and Qiskit's SABRE transpiler), the greedy strategy reduced circuit depth and two-qubit gate counts by approximately a factor of two for sparse graphs.
- For RR graphs, the number of SWAP layers, depth, and CZ gates scaled as $n$ , $n$ , and $n^2$ for linear strategies, while the greedy strategy maintained lower constants and better scaling behavior.
- For ER graphs, the greedy strategy significantly outperformed linear strategies, with CZ gate counts scaling as $O(n^{5/2})$ compared to $O(n^3)$ for linear strategies.
Feasibility Regime: The reduction in gate count extended the feasible problem size for noisy hardware. For a fixed CZ gate budget (e.g., 3,600 gates), the greedy strategy enabled the execution of instances with up to 100 nodes, whereas the linear strategy was limited to approximately 60 nodes.
Approximation Ratios: Hardware experiments demonstrated improved performance:
- Maximum Cut (MC): The greedy strategy improved the mean approximation ratio by up to 6.62% (at 72 qubits) compared to the linear strategy.
- Maximum Independent Set (MIS): The improvement was even more pronounced, reaching 9.32% (at 56 qubits).
Truncation Comparison: Unlike approaches that truncate the cost Hamiltonian to reduce depth (sacrificing theoretical guarantees), the greedy strategy implemented a significantly larger subset of target interactions for the same number of SWAP layers, preserving more problem structure.

Significance and Claims

The paper claims that efficient transpilation is critical for the practical performance of QAOA on near-term hardware. The authors assert that their problem-aware transpilation scheme is key to improving quantum algorithm performance on noisy devices, particularly for sparse optimization problems.

Key claims regarding significance include:

Enabling Larger Experiments: The method enables experiments with up to 80 qubits on current hardware by reducing the circuit depth and error accumulation.
Amplifying Hardware Improvements: As hardware quality improves (increasing the available CZ gate budget), the benefits of efficient transpilation are amplified. The greedy strategy allows for a larger increase in accessible problem size compared to linear strategies as the gate budget grows.
Relevance to Quantum Advantage: The approach is particularly relevant for probing regimes of potential quantum advantage, including hardness regimes where classical solvers struggle (e.g., low-density MIS instances with 500 nodes).
Future-Proofing: The work highlights that as error correction codes (like the bivariate bicycle code) require structured, non-local connectivity based on rectangular lattices, adapting transpilation strategies to exploit 2D connectivity will be essential for reducing circuit complexity in future architectures.

The authors conclude that while their method relies on predefined SWAP layers, it demonstrates that problem-aware transpilation is a necessary step to bridge the gap between theoretical quantum algorithms and practical, noisy hardware execution.