⚛️ quantum physics

Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings

This paper introduces a simulated annealing-based method that optimizes QAOA circuit transpilation on fixed-layout quantum hardware by significantly reducing the encoding overhead of parity twine chains and SWAP networks, thereby achieving substantial decreases in circuit depth and two-qubit gate counts compared to standard transpilers.

Original authors: J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

Published 2026-08-12

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

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 organize a massive, chaotic dance party where every guest needs to hold hands with every other guest at some point to perform a special routine. Now, imagine the dance floor is a narrow, single-file hallway. In this hallway, people can only hold hands with the person immediately next to them. If Guest A needs to hold hands with Guest Z, who is at the very end of the line, they can't just reach across the crowd. They have to shuffle, swap places, and wiggle through the line until they are neighbors. This shuffling takes time, and every time two people bump into each other to swap, there's a chance they might trip, drop their hands, or mess up the routine. In the world of quantum computing, this dance floor is a quantum chip, the guests are tiny particles called qubits, and the "tripping" is a type of error that ruins the calculation. Scientists are constantly trying to figure out how to get these qubits to talk to each other efficiently without tripping over themselves, especially since current chips are like that narrow hallway and can't connect everyone to everyone else directly.

This paper is about finding the best choreography for that dance. The researchers focused on a specific algorithm called QAOA, which is used to solve complex puzzles like finding the best way to split a group of people into two teams. To make this work on a narrow, one-dimensional chip, they had to use "transpilation," which is just a fancy word for rearranging the instructions so the hardware can understand them. They tested two main ways to do the shuffling: the "SWAP network," which is like a standard, organized line dance where everyone moves step-by-step, and a newer, trickier method called "Parity Twine Chains" (PTC), which is more like encoding the information of two dancers into one person's moves to save space. The authors also invented a new "simulated annealing" technique, which is like a smart, trial-and-error coach that tries thousands of different starting lineups to find the one that requires the least amount of shuffling.

The team found that for small, sparse puzzles, the standard computer programs used by companies like IBM were actually quite good at minimizing the number of moves. However, as the puzzles got bigger and the connections between qubits became more frequent, their new methods started to shine. By using their smart coach to rearrange the starting order of the qubits, they could significantly cut down the number of times the qubits had to swap places. For a massive 120-qubit puzzle with 25% connectivity, their method shaved off 87% of the circuit depth (the time it takes to run) and 29% of the two-qubit gates (the risky moves) compared to the standard IBM software. They also tested this on real quantum computers, specifically the "ibm fez" and "ibm kingston" devices. On the "ibm fez," they managed to find the perfect solution for a 20-qubit problem using their PTC method, whereas the standard method only worked up to 15 qubits. Interestingly, on the "ibm kingston" device, the standard SWAP method actually performed slightly better than the PTC method for a specific type of problem, suggesting that sometimes having fewer moves isn't the only thing that matters; the way the information is encoded matters just as much. The researchers suggest that while their method is a powerful tool for reducing errors and saving time, it's not a magic bullet that works perfectly in every single scenario, and the best choice depends on the specific shape of the problem and the quirks of the hardware.

Technical Summary: Optimizing QAOA Circuit Transpilation with Parity Twine and SWAP Network Encodings

Problem Statement
Current superconducting quantum processors (QPUs) suffer from limited qubit connectivity, typically restricting interactions to nearest neighbors on specific topologies (e.g., heavy-hex lattices). Executing algorithms like the Quantum Approximate Optimization Algorithm (QAOA), which often require fully connected or dense two-qubit interactions, necessitates a transpilation process. This process maps logical qubits to physical qubits and inserts SWAP gates to satisfy connectivity constraints. However, SWAP gates are decomposed into multiple two-qubit gates (e.g., three CNOTs), which are the primary source of noise and error on near-term devices. While structured encodings like SWAP networks and Parity Twine Chains (PTC) offer analytical resource benefits for fully connected graphs, their application to sparsely connected (non-fully connected) graphs remains suboptimal. Furthermore, finding the optimal initial qubit mapping (a subgraph isomorphism problem) to minimize gate counts in these sparse scenarios is NP-hard, and existing solvers like SATMapper face scalability and runtime limitations for large systems.

Methodology
The authors propose a hybrid approach combining structured encoding strategies with a simulated annealing (SA) heuristic to optimize the initial logical-to-physical qubit mapping.

Encodings:
- SWAP Network: A structured routing schedule on a 1D chain where alternating layers of nearest-neighbor SWAP gates move logical qubits to create required adjacencies.
- Parity Twine Chains (PTC): A method encoding multi-qubit Z-information into single physical qubits via parity. This allows non-local interactions to be executed as local single-qubit rotations ( $R_Z$ ), reducing the two-qubit gate count compared to SWAP networks. The method utilizes a decoding strategy where measurements are taken in the parity basis, and classical post-processing recovers the logical bitstring, avoiding the need for additional CNOT gates to return to the computational basis.
Simulated Annealing (SA) Optimization:
- The authors introduce an SA-based algorithm to solve the subgraph isomorphism problem for both SWAP and PTC encodings.
- Cost Function: The cost function is combinatorial and non-smooth, evaluating the number of two-qubit gates that can be pruned (removed) from the circuit. It checks, layer by layer, whether the mapped qubit pairs correspond to native edges in the hardware coupling graph. If a required interaction is absent in the problem graph, the corresponding gates in the encoding schedule are omitted.
- Process: The algorithm iteratively swaps pairs of qubit labels to find a permutation that minimizes the total two-qubit gate count and circuit depth. This approach is chosen because gradient-based methods are unsuitable for the discrete search space, and exact methods are computationally prohibitive.
Benchmarking and Noise Modeling:
- The method is benchmarked against standard transpilers (Qiskit-T, Qiskit-P, Qiskit-AI, TKET) and the SATMapper.
- Noise simulations use a depolarizing noise model acting on two-qubit gates within a Linear Ramp QAOA (LR-QAOA) protocol for Weighted MaxCut (WMC) problems.
- Experimental validation is performed on IBM Quantum devices (ibm_fez and ibm_kingston).

Key Contributions

SA-Optimized Encodings: The introduction of a simulated annealing strategy to optimize the initial qubit ordering for both PTC and SWAP encodings, specifically targeting non-fully connected graphs.
Scalability: Demonstrating that the SA approach scales effectively to large qubit counts (up to 200 qubits in simulation), offering a runtime advantage of orders of magnitude over SATMapper while achieving comparable solution quality.
PTC Decoding: A detailed description of a decoding strategy for PTC that eliminates the need for circuit-depth-increasing CNOT gates to revert to the computational basis.
Experimental Validation: The first experimental implementation of PTC encoding on real quantum hardware.

Results

Gate Count and Depth Reduction: For QAOA circuits with edge densities ( $E_d$ $E_{d}$ ) exceeding specific thresholds, PTC+SA and SWAP+SA significantly outperform standard transpilers.
- For a 120-qubit instance with 25% connectivity, the proposed method achieved an 87% reduction in circuit depth and a 29% reduction in two-qubit gates compared to the Qiskit transpiler (optimization level 3).
- The threshold for PTC+SA to outperform Qiskit-T in gate count decreases as system size increases (from $E_d \approx 0.35$ for 20 qubits to $E_d \approx 0.13$ for 120 qubits).
Runtime Efficiency: The SA method converges to high-quality solutions in seconds for 200-qubit problems, whereas SATMapper requires hundreds to thousands of seconds.
Noise Resilience:
- Simulation: In noise simulations, PTC showed a higher success probability ( $p_{gs}$ ) than SWAP for low-to-moderate noise levels due to fewer gates, though the approximation ratio ( $r$ ) remained similar for both.
- Real Hardware (ibm_fez): PTC encoding extended the range of useful LR-QAOA experiments. Optimal solutions were found for problem sizes up to 20 qubits using PTC, compared to only 15 qubits with SWAP. The distinction from random sampling held up to 22 qubits for PTC versus 20 for SWAP.
- Real Hardware (ibm_kingston): For a 20-qubit problem with $E_d = 0.298$ , SWAP+SA achieved the best approximation ratio (20.83% improvement over random), outperforming PTC+SA (13.99%). The authors note that while PTC uses fewer gates, the encoding of logical pairs into single physical qubits may be more sensitive to noise accumulation in non-fully connected scenarios.
Transpiler Comparison: Standard transpilers (like Qiskit-T) often minimize gate counts at the expense of significantly increased circuit depth, which exacerbates noise. The proposed methods maintain compact circuits with lower depth.

Significance and Claims
The paper claims to present the first demonstration of SWAP and PTC encodings outperforming standard transpiler methods in scenarios with reduced qubit connectivity. It also constitutes the first experimental implementation of PTC encoding on real quantum hardware.

The authors emphasize that while optimal structured encodings are well-known for fully connected graphs, their application to partially connected graphs via the proposed SA-based optimization yields significant resource reductions. They conclude that for systems up to 20 qubits, PTC encoding improves performance on real hardware, extending the viable problem size for LR-QAOA. However, they modestly note that in non-fully connected experiments on ibm_kingston, SWAP+SA sometimes outperformed PTC+SA, suggesting that the trade-off between gate count and noise sensitivity depends heavily on the specific encoding structure and problem topology. The work establishes a practical pathway for executing QAOA on connectivity-constrained near-term devices with reduced overhead.

More like this