A High-Performance Multilevel Framework for Quantum Layout Synthesis

Shuohao Ping, Naren K Sathishkumar, Wan-Hsuan Lin, H. Wang, Jason CongarXiv 2025 · DOI · arXiv

TL;DR

ML-SABRE is a new multilevel framework that solves the Quantum Layout Synthesis (QLS) problem by combining hierarchical circuit coarsening with state-of-the-art heuristics. By replacing slow exact solvers with the efficient LightSABRE heuristic at every level of the optimization process, it achieves a "best of both worlds" result: reducing SWAP gate overhead by over 60% while running significantly faster than previous multilevel approaches.

What Problem Does This Paper Address?

Quantum computers have a "connectivity problem." While a quantum algorithm might require any two qubits to interact, physical hardware (like superconducting chips) usually only allows interactions between adjacent qubits on a specific coupling graph. To run a circuit, compilers must perform Quantum Layout Synthesis (QLS)—mapping logical qubits to physical ones and inserting SWAP gates to move qubits around until they are adjacent.

The challenge is that SWAP gates are "expensive": they introduce noise, increase the chance of error, and extend the circuit's execution time (depth). Finding the absolute minimum number of SWAPs is an NP-hard problem. Current tools fall into two camps:

  1. Heuristics (like SABRE): Very fast but often get stuck in "local minima," producing suboptimal mappings.
  2. Exact Solvers (SMT/SAT): Produce optimal results but take hours or days to solve even medium-sized circuits, making them unscalable for the 100+ qubit era.

Methods

The authors propose ML-SABRE, which uses a multilevel (V-cycle) framework. This is a strategy borrowed from classical VLSI design that simplifies a problem, solves it, and then progressively adds detail back in.

The ML-SABRE flow consists of three main phases:

  • Coarsening (Clustering): The algorithm groups "strongly interacting" qubits into clusters, creating a smaller, simplified version of the circuit and the hardware graph. A key innovation here is a topology-aware initial embedding that identifies common structures like "lines" or "stars" to guide the clustering.
  • Coarsest-Level Solving: Once the circuit is small enough, it is solved. Unlike previous work that used slow exact solvers here, ML-SABRE uses LightSABRE, a fast heuristic, which keeps the runtime low.
  • Refinement (Interpolation): The solution is projected back to the original, larger circuit. At each step, LightSABRE is used again to "polish" the mapping and fix any local issues introduced by the clustering.

The framework also uses multiple V-cycles and random restarts to explore different parts of the solution space, ensuring it doesn't get stuck with a mediocre mapping.

Datasets

The authors evaluated ML-SABRE using several standard quantum benchmarking suites:

  • QASMBench: A collection of real-world quantum algorithms (e.g., QFT, Adder, Multiplier).
  • QUEKO: A benchmark suite with known optimal circuit depths.
  • QUBIKOS: A benchmark suite with known optimal SWAP counts.

Testing was performed on two distinct hardware architectures:

  1. IBM Eagle: A 127-qubit "heavy-hex" architecture (sparse connectivity).
  2. Google Willow: A 105-qubit grid architecture (dense connectivity).

Key Insights and Ideas

  • Heuristics are "Good Enough" at Small Scales: The authors realized that while heuristics struggle with 100 qubits, they are nearly optimal for 10-20 qubits. By coarsening the problem down to this size, they can use fast heuristics instead of slow exact solvers without losing much quality.
  • The "Goldilocks" Clustering: If you cluster qubits too aggressively, you lose the structural information of the circuit (over-clustering). ML-SABRE uses an adaptive clustering strategy that stops just before the mapping becomes trivial, ensuring the coarsest level still provides meaningful global guidance.
  • Structure Matters: Quantum circuits aren't random; they often have linear chains or star-like hubs. By explicitly looking for these shapes during the initial mapping, ML-SABRE starts the optimization process much closer to a good solution.

Key Results

ML-SABRE significantly outperformed both the standard SABRE heuristic and the previous state-of-the-art multilevel tool (ML-QLS):

  • On IBM Eagle: Compared to SABRE, it reduced the SWAP count by 65% and circuit depth by 17%, while actually being 2.5x faster.
  • Scalability: Compared to the previous multilevel framework (ML-QLS), ML-SABRE was up to 240x faster on certain circuits, solving in seconds what previously took 30 minutes.
  • Optimality Gap: In studies using QUEKO/QUBIKOS, ML-SABRE reduced the gap to the theoretical "perfect" solution by up to 82% for SWAP counts.

Limitations and Future Work

The authors noted that the performance gains vary by hardware topology. On the Google Willow (a dense 2D grid), the improvements were less dramatic than on the sparse IBM Eagle. This is because dense grids offer many "shortest paths" for SWAPs, making the global guidance of a multilevel framework less critical than in sparse, constrained layouts.

Future work could involve further tuning the refinement stage or exploring how this multilevel approach could be adapted for "noise-aware" synthesis, where the goal isn't just to minimize SWAPs, but to avoid the specific physical qubits that have the highest error rates.

Summary updated

Abstract

Quantum Layout Synthesis (QLS) is a critical compilation stage that adapts quantum circuits to hardware constraints with an objective of minimizing the SWAP overhead. While heuristic tools demonstrate good efficiency, they often produce suboptimal solutions, and exact methods suffer from limited scalability. In this work, we propose ML-SABRE, a high-performance multilevel framework for QLS that improves both solution quality and compilation time through a hierarchical optimization approach. We employ the state-of-the-art heuristic method, LightSABRE, at all levels to ensure both efficiency and performance. Our evaluation on real benchmarks and hardware architectures shows that ML-SABRE decreases SWAP count by over 60%, circuit depth by 17%, and delivers a 60% compilation time reduction compared to state-of-the-art solvers. Further optimality studies reveal that ML-SABRE can significantly reduce the optimality gap by up to 82% for SWAP count and 49% for circuit depth, making it well-suited for emerging quantum devices with increasing size and architectural complexity.
BibTeX
@misc{ping2025high,
  author = {Shuohao Ping and Naren K Sathishkumar and Wan-Hsuan Lin and H. Wang and Jason Cong},
  title = {{A High-Performance Multilevel Framework for Quantum Layout Synthesis}},
  year = {2025},
  eprint = {2505.24169},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.24169},
  howpublished = {arXiv},
}
Figure