⚛️ quantum physics

SSR: A Swapping-Sweeping-and-Rewriting Optimizer for Quantum Circuit Transformation

This paper proposes SSR, a novel optimizer that combines a genetic algorithm for circuit rearrangement, a sweeping technique for CNOT subcircuit extraction, and an SAT solver for depth-optimal rewriting to significantly reduce the depth of quantum circuit transformations on NISQ devices.

Original authors: Yunqi Huang, Xiangzhen Zhou, Fanxu Meng, Pengcheng Zhu, Yu Luo, Zhenlong Du

Published 2026-06-23

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Yunqi Huang, Xiangzhen Zhou, Fanxu Meng, Pengcheng Zhu, Yu Luo, Zhenlong Du

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 send a message across a crowded city using a fleet of delivery drones. However, there's a catch: the drones can only talk to each other if they are flying right next to one another. If two drones need to exchange a package but are on opposite sides of the city, you have to send a third drone to physically carry the message back and forth. In the world of quantum computing, this is exactly what happens.

The Problem: The "Detour" Traffic Jam
Quantum computers (specifically the current noisy ones called NISQ devices) are like cities with very strict traffic rules. Their "drones" (qubits) can only interact if they are physically connected. When scientists design a quantum program, they often assume all drones can talk to each other instantly. To make this work on real hardware, a process called Quantum Circuit Transformation (QCT) is used.

Think of QCT as a traffic controller who inserts "SWAP" gates. These are like detours where drones have to swap places to get close enough to interact. While this solves the connectivity problem, it creates a massive traffic jam. The circuit becomes much longer (deeper), and because quantum signals are fragile, the longer the trip, the more likely the message gets garbled or lost.

The Solution: SSR (Swapping, Sweeping, and Rewriting)
The authors of this paper propose a new tool called SSR to clean up this traffic jam after the initial detours have been added. They use a three-step strategy that acts like a highly efficient traffic optimization team:

Swapping (The Genetic Algorithm):
Imagine the traffic controller just threw the drones into a random order to get them connected. SSR uses a "Genetic Algorithm," which is like a digital evolution simulator. It tries thousands of different ways to shuffle the order of the drones (gates) to see if moving a "detour" (SWAP) earlier or later in the sequence makes the whole trip shorter. It keeps the best arrangements and discards the bad ones, just like nature selects the fittest traits.
Sweeping (The Scanner):
Once the order is optimized, SSR acts like a vacuum cleaner sweeping across the circuit. It looks for clusters of "CNOT" gates (a specific type of quantum interaction) that are stuck together. It identifies these clusters as "sub-circuits" that are ripe for improvement.
Rewriting (The Smart Architect):
This is the most powerful part. For each cluster found, SSR doesn't just try to fix it; it asks a super-smart "architect" (a SAT solver) to design a brand-new, mathematically perfect version of that cluster that does the exact same job but in fewer steps.
- The Catch: If the architect designs a perfect cluster but places it in a spot where it blocks the next step, the whole trip gets longer. To prevent this, SSR uses "Gate Position Constraining." It tells the architect: "You can design the perfect cluster, but you must build it within these specific time and space boundaries so you don't block the other drones."
- The Speed Boost: Asking the architect to start from scratch every time is slow. So, SSR uses an Artificial Neural Network (ANN)—a type of AI trained on millions of examples—to guess the best possible number of steps needed before asking the architect. This acts like a shortcut, telling the architect, "Try to build it in 5 steps first," rather than starting at 1 and working up. This saves a huge amount of time.

The Results: A Clearer Road
The paper tests this SSR tool on various quantum circuits and different hardware layouts (like Google's Sycamore and IBM's processors).

The Outcome: Compared to existing methods, SSR successfully reduced the "depth" (the total travel time) of the circuits by an average of 16.59%, with some circuits improving by as much as 29.04%.
Comparison: Other tools tried to fix the traffic, but they often made things worse or only improved them slightly. SSR consistently found a smoother path.
Efficiency: Even when the circuits were already optimized by standard software (like Qiskit), SSR could still squeeze out an extra 10% of efficiency.

In Summary
SSR is a post-optimization tool that takes a quantum circuit that has already been forced to fit into a real machine's limitations and rearranges it. It shuffles the order of operations, finds groups of steps that can be simplified, and uses AI to predict the best way to rebuild them without causing new traffic jams. The result is a faster, more reliable quantum calculation that is less likely to fail due to noise.

Technical Summary: SSR: A Swapping-Sweeping-and-Rewriting Optimizer for Quantum Circuit Transformation

Problem Statement
Quantum Circuit Transformation (QCT) is a necessary process for adapting logical quantum circuits to the physical connectivity constraints of Noisy Intermediate-Scale Quantum (NISQ) devices. To satisfy these constraints, QCT algorithms typically insert numerous SWAP gates, which decompose into multiple CNOT gates, thereby increasing the circuit depth. This increased depth exacerbates error rates and reduces the success probability of quantum computations. While existing post-QCT optimization techniques exist, they often fail to sufficiently minimize depth or do not specifically address the structural inefficiencies introduced by the QCT process, such as the proliferation of consecutive CNOT and SWAP gates. The authors identify a need for a dedicated post-QCT optimization framework that can effectively reduce circuit depth while adhering to hardware connectivity constraints.

Methodology
The paper proposes SSR (Swapping-Sweeping-and-Rewriting), a unified optimization framework designed to reduce the depth of QCT-generated circuits. The methodology operates through an iterative loop comprising three core stages:

Swapping (Genetic Algorithm-based Commutation):
Before rewriting, the framework employs a Genetic Algorithm (GA) to explore generalized commutation rules between SWAP and CNOT gates. The GA treats the sequence of valid gate swaps as a solution space, evolving populations of circuits to find configurations that reduce overall depth and create more favorable subcircuit structures for subsequent optimization. Crucially, the GA enforces hardware connectivity constraints during the commutation process, ensuring that all generated candidate circuits remain valid for the target architecture.
Sweeping (Subcircuit Extraction and Scoring):
The framework scans the circuit to extract contiguous subcircuits composed of CNOT and SWAP gates. To manage computational complexity, a maximum qubit limit ( $n_q$ ) is imposed on extracted subcircuits. A scoring function evaluates the potential depth reduction of each subcircuit. This score estimates the difference between the current depth and the optimal depth of the subcircuit. To avoid the computational intractability of exact synthesis for every candidate, the authors utilize a supervised Artificial Neural Network (ANN) trained on Boolean matrix representations of CNOT circuits to predict the optimal depth. This prediction guides the selection of the top-scoring subcircuits for rewriting, rather than rewriting all subcircuits simultaneously, which the authors argue prevents premature fixation of local structures that could hinder global optimization.
Rewriting (SAT-based Synthesis with Constraints):
Selected subcircuits are rewritten using a Boolean Satisfiability (SAT) solver to find a functionally equivalent, depth-optimal circuit. The authors introduce two key modifications to standard SAT-based synthesis:
- ANN-Assisted Invoking: Instead of a trial-and-error approach starting from depth 1, the ANN's predicted depth serves as the initial target for the SAT solver, significantly reducing the number of solver invocations.
- Gate Position Constraining: To ensure that local optimizations do not negatively impact the global circuit depth, the SAT formulation includes "blocked position" constraints. These constraints prevent the placement of CNOT gates in time-space coordinates occupied by non-subcircuit gates (e.g., single-qubit gates or gates from adjacent subcircuits), forcing the solver to find solutions that fit within the existing global schedule.

Key Contributions
The paper outlines five primary contributions:

Unified Framework: The formulation of depth-oriented post-QCT optimization as a dedicated problem, addressed by the SSR framework, which complements existing QCT and synthesis techniques.
ANN-Assisted Acceleration: The introduction of an ANN-based depth prediction scheme to guide the SAT solver's search order and reduce invocation counts without compromising the completeness or optimality of the SAT procedure itself.
Gate Position Constraining: A mechanism within the SAT formulation that balances local subcircuit optimality with global circuit-level depth reduction by restricting gate placements to valid time-space windows.
Iterative Strategy: A subcircuit scoring and selection strategy combined with GA-based commutation, allowing the optimizer to prioritize promising subcircuits and iteratively expose new optimization opportunities.
Empirical Validation: Extensive experiments demonstrating consistent and significant depth reductions across various architectures and benchmark suites.

Experimental Results
The authors evaluated SSR on multiple architectures (Grid 5x4, Google Sycamore, IBM Rochester, IBM Heron) and benchmark suites (RevLib, Qiskit-extracted circuits, random circuits).

Depth Reduction: SSR achieved a maximum depth reduction of 29.04% and an average reduction of 16.59% across all benchmarks.
Comparison: SSR outperformed existing post-QCT optimizers CBIR and Q-Synth. On average, SSR improved depth by 16.59%, whereas CBIR and Q-Synth achieved average improvements of 6.45% and -0.53% (indicating a slight increase in depth for Q-Synth on some benchmarks), respectively.
Scalability: The runtime of SSR was observed to grow almost linearly with the number of qubits and the average number of gates, demonstrating scalability.
Component Analysis: Ablation studies confirmed that each component (GA, Gate Position Constraining, ANN) contributes to the overall performance. The ANN specifically reduced SAT solver calls by up to 95.87%, drastically cutting execution time with negligible impact on final circuit depth.

Significance
The paper claims that SSR provides a significant extension of SAT-Sweeping techniques to the domain of quantum circuit transformation. By integrating heuristic search (GA), machine learning (ANN), and exact synthesis (SAT) with specific constraints for hardware connectivity, SSR offers a robust method for mitigating the depth overhead introduced by QCT. The authors position SSR as a complementary tool to existing compilers, capable of further refining circuits that have already been mapped to hardware, thereby improving the fidelity and success rates of computations on NISQ devices. The work emphasizes that while the approach sacrifices exact global optimality for scalability (by focusing on CNOT subcircuits and using heuristics for selection), it achieves practical and significant depth reductions that are unattainable by purely local or purely exact methods in isolation.

More like this