Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.10274

Efficient Circuit Transpilation of Commuting Gates on 2D Grids

Sabina Drăgoi, Daniel J. Egger

quant-phSubmitted Jul 11, 2026• Announced Jul 14, 2026• 0 citations
arXivHTMLPDF

Abstract

Combinatorial optimization problems are central to many applications but can be challenging to solve. Quantum approaches such as the Quantum Approximate Optimization Algorithm (QAOA) offer new tools with which to tackle such problems. However, QAOA circuits inherit the interaction structure of the target Hamiltonian, often resulting in deep circuits when compiled onto hardware with limited connectivity. Efficient transpilation is therefore critical to their practical performance. In this work, we propose a transpilation scheme for circuits consisting of blocks of commuting two-qubit gates on two-dimensional lattices. Unlike standard approaches based on random initial mappings and fixed routing, our method alternates between constructing problem-dependent SWAP-layer sequences and updating the qubit layout. By adapting the routing to the required interactions, this yields significantly shorter circuits for graphs with few edges. We benchmark our approach on QAOA instances for Maximum Cut (MC) on Random Regular graphs and Maximum Independent Set (MIS) on Erdős-Rényi graphs. Compared to standard methods, we reduce circuit depth and gate count by about a factor of two, enabling experiments with up to $80$ qubits and improving approximation ratios by up to $6.6\%$ for MC and $9.3\%$ for MIS.

Comments
20 pages, 17 figures

Related papers

A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates

Atsushi Matsuo, Shigeru Yamashita, Daniel J. Egger

Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.

arXiv:2212.05666•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 16, 2023•17 citations

Improved Qubit Routing for QAOA Circuits

Ayse Kotil, Fedor Šimkovic, Martin Leib

We develop a qubit routing algorithm with polynomial classical run time for the Quantum Approximate Optimization Algorithm (QAOA). The algorithm follows a two step process. First, it obtains a near-optimal solution, based on Vizing's theorem for the edge coloring problem, consisting of subsets of the interaction gates that can be executed in parallel on a fully parallelized all-to-all connected QPU. Second, it proceeds with greedy application of SWAP gates based on their net effect on the distance of remaining interaction gates on a specific hardware connectivity graph. Our algorithm strikes a balance between optimizing for both the circuit depth and total SWAP gate count. We show that it improves upon existing state-of-the-art routing algorithms for QAOA circuits defined on $k$-regular as well as Erdös-Renyi problem graphs of sizes up to $N \leq 400$.

arXiv:2312.15982•Dec 26, 2023•1 citation

Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings

J. A. Montañez-Barrera, Yanjun Ji, Michael R. von Spakovsky +2 more

Mapping quantum approximate optimization algorithm (QAOA) circuits with nontrivial connectivity in fixed-layout quantum platforms, such as superconducting quantum processing units (QPUs), requires a transpilation process to match the circuit to the hardware layout. This step is critical for reducing error rates on noisy QPUs. Two approaches that improve the resources required for such transpilation are the SWAP network and parity twine chains (PTC), which reduce the two-qubit gate count and circuit depth needed to represent fully connected circuits. In this work, we introduce a simulated annealing-based method that further reduces the encoding overhead of PTC and SWAP networks for QAOA circuits with nonfully connected two-qubit interactions. The method is benchmarked against various transpilers, including the Qiskit SAT mapper, demonstrating that beyond specific connectivity thresholds it achieves significant reductions in both two-qubit gate count and circuit depth. For example, for a 120-qubit QAOA instance with 25% connectivity, our method achieves an 87% reduction in depth and a 29% reduction in two-qubit gates compared with the Qiskit transpiler. Finally, the practical impact of PTC encoding is validated by benchmarking QAOA on the and devices, showing improved performance for systems of up to 20 qubits.

Physical Review Applied•Jun 30, 2026•0 citations

A Structured Method for Compilation of QAOA Circuits in Quantum Computing

Yuwei Jin, Luo, Jason, Lucent Fong +5 more

Quantum Approximation Optimization Algorithm (QAOA) is a highly advocated variational algorithm for solving the combinatorial optimization problem. One critical feature in the quantum circuit of QAOA algorithm is that it consists of two-qubit operators that commute. The flexibility in reordering the two-qubit gates allows compiler optimizations to generate circuits with better depths, gate count, and fidelity. However, it also imposes significant challenges due to additional freedom exposed in the compilation. Prior studies lack the following: (1) Performance guarantee, (2) Scalability, and (3) Awareness of regularity in scalable hardware. We propose a structured method that ensures linear depth for any compiled QAOA circuit on multi-dimensional quantum architectures. We also demonstrate how our method runs on Google Sycamore and IBM Non-linear architectures in a scalable manner and in linear time. Overall, we can compile a circuit with up to 1024 qubits in 10 seconds with a 3.8X speedup in depth, 17% reduction in gate count, and 18X improvement for circuit ESP.

arXiv:2112.06143•Dec 12, 2021•4 citations

Generalized swap networks for near-term quantum computing

Bryan O’Gorman, William J. Huggins, Eleanor Gilbert Rieffel +1 more

The practical use of many types of near-term quantum computers requires accounting for their limited connectivity. One way of overcoming limited connectivity is to insert swaps in the circuit so that logical operations can be performed on physically adjacent qubits, which we refer to as solving the `routing via matchings' problem. We address the routing problem for families of quantum circuits defined by a hypergraph wherein each hyperedge corresponds to a potential gate. Our main result is that any unordered set of $k$-qubit gates on distinct $k$-qubit subsets of $n$ logical qubits can be ordered and parallelized in $O(n^{k-1})$ depth using a linear arrangement of $n$ physical qubits; the construction is completely general and achieves optimal scaling in the case where gates acting on all $\binom{n}{k}$ sets of $k$ qubits are desired. We highlight two classes of problems for which our method is particularly useful. First, it applies to sets of mutually commuting gates, as in the (diagonal) phase separators of Quantum Alternating Operator Ansatz (Quantum Approximate Optimization Algorithm) circuits. For example, a single level of a QAOA circuit for Maximum Cut can be implemented in linear depth, and a single level for $3$-SAT in quadratic depth. Second, it applies to sets of gates that do not commute but for which compilation efficiency is the dominant criterion in their ordering. In particular, it can be adapted to Trotterized time-evolution of fermionic Hamiltonians under the Jordan-Wigner transformation, and also to non-standard mixers in QAOA. Using our method, a single Trotter step of the electronic structure Hamiltonian in an arbitrary basis of $n$ orbitals can be done in $O(n^3)$ depth while a Trotter step of the unitary coupled cluster singles and doubles method can be implemented in $O(n^2 η)$ depth, where $η$ is the number of electrons.

arXiv:1905.05118•May 13, 2019•54 citations

Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid algorithm to solve hard combinatorial optimization problems. The multi-qubit CPHASE gates used in the quantum circuit for QAOA are commutative i.e., the order of the gates can be altered without changing the output state. This re-ordering leads to the execution of more gates in parallel and a smaller number of additional SWAP gates to compile the QAOA-circuit. Consequently, the circuit-depth and cumulative gate-count become lower which is beneficial for circuit execution time and noise resilience. A less number of gates indicates a lower accumulation of gate-errors, and a reduced circuit-depth means less decoherence time for the qubits. However, finding the best-ordered circuit is a difficult problem and does not scale well with circuit size. This paper presents four generic methodologies to optimize QAOA-circuits by exploiting gate re-ordering. We demonstrate a reduction in gate-count by ≈23.0% and circuit-depth by ≈53.0% on average over a conventional approach without incurring any compilation-time penalty. We also present a variation-aware compilation which enhances the compiled circuit success probability by ≈62.7% for the target hardware over the variation unaware approach. A new metric, Approximation Ratio Gap (ARG), is proposed to validate the quality of the compiled QAOA-circuit instances on actual devices. Hardware implementation of a number of QAOA instances shows ≈25.8% improvement in the proposed metric on average over the conventional approach on ibmq 16 melbourne.

IEEE/ACM International Symposium on Microarchitecture (MICRO)•Oct 1, 2020•71 citations
Combinatorial optimization problems are central to many applications but can be challenging to solve. Quantum approaches such as the Quantum Approximate Optimization Algorithm (QAOA) offer new tools with which to tackle such problems. However, QAOA circuits inherit the interaction structure of the target Hamiltonian, often resulting in deep circuits when compiled onto hardware with limited connectivity. Efficient transpilation is therefore critical to their practical performance. In this work, we propose a transpilation scheme for circuits consisting of blocks of commuting two-qubit gates on two-dimensional lattices. Unlike standard approaches based on random initial mappings and fixed routing, our method alternates between constructing problem-dependent SWAP-layer sequences and updating the qubit layout. By adapting the routing to the required interactions, this yields significantly shorter circuits for graphs with few edges. We benchmark our approach on QAOA instances for Maximum Cut (MC) on Random Regular graphs and Maximum Independent Set (MIS) on Erdős-Rényi graphs. Compared to standard methods, we reduce circuit depth and gate count by about a factor of two, enabling experiments with up to 808080 qubits and improving approximation ratios by up to 6.6%6.6\%6.6% for MC and 9.3%9.3\%9.3% for MIS.
Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.
We develop a qubit routing algorithm with polynomial classical run time for the Quantum Approximate Optimization Algorithm (QAOA). The algorithm follows a two step process. First, it obtains a near-optimal solution, based on Vizing's theorem for the edge coloring problem, consisting of subsets of the interaction gates that can be executed in parallel on a fully parallelized all-to-all connected QPU. Second, it proceeds with greedy application of SWAP gates based on their net effect on the distance of remaining interaction gates on a specific hardware connectivity graph. Our algorithm strikes a balance between optimizing for both the circuit depth and total SWAP gate count. We show that it improves upon existing state-of-the-art routing algorithms for QAOA circuits defined on kkk-regular as well as Erdös-Renyi problem graphs of sizes up to N≤400N \leq 400N≤400.
Mapping quantum approximate optimization algorithm (QAOA) circuits with nontrivial connectivity in fixed-layout quantum platforms, such as superconducting quantum processing units (QPUs), requires a transpilation process to match the circuit to the hardware layout. This step is critical for reducing error rates on noisy QPUs. Two approaches that improve the resources required for such transpilation are the SWAP network and parity twine chains (PTC), which reduce the two-qubit gate count and circuit depth needed to represent fully connected circuits. In this work, we introduce a simulated annealing-based method that further reduces the encoding overhead of PTC and SWAP networks for QAOA circuits with nonfully connected two-qubit interactions. The method is benchmarked against various transpilers, including the Qiskit SAT mapper, demonstrating that beyond specific connectivity thresholds it achieves significant reductions in both two-qubit gate count and circuit depth. For example, for a 120-qubit QAOA instance with 25% connectivity, our method achieves an 87% reduction in depth and a 29% reduction in two-qubit gates compared with the Qiskit transpiler. Finally, the practical impact of PTC encoding is validated by benchmarking QAOA on the and devices, showing improved performance for systems of up to 20 qubits.
Quantum Approximation Optimization Algorithm (QAOA) is a highly advocated variational algorithm for solving the combinatorial optimization problem. One critical feature in the quantum circuit of QAOA algorithm is that it consists of two-qubit operators that commute. The flexibility in reordering the two-qubit gates allows compiler optimizations to generate circuits with better depths, gate count, and fidelity. However, it also imposes significant challenges due to additional freedom exposed in the compilation. Prior studies lack the following: (1) Performance guarantee, (2) Scalability, and (3) Awareness of regularity in scalable hardware. We propose a structured method that ensures linear depth for any compiled QAOA circuit on multi-dimensional quantum architectures. We also demonstrate how our method runs on Google Sycamore and IBM Non-linear architectures in a scalable manner and in linear time. Overall, we can compile a circuit with up to 1024 qubits in 10 seconds with a 3.8X speedup in depth, 17% reduction in gate count, and 18X improvement for circuit ESP.
The practical use of many types of near-term quantum computers requires accounting for their limited connectivity. One way of overcoming limited connectivity is to insert swaps in the circuit so that logical operations can be performed on physically adjacent qubits, which we refer to as solving the `routing via matchings' problem. We address the routing problem for families of quantum circuits defined by a hypergraph wherein each hyperedge corresponds to a potential gate. Our main result is that any unordered set of kkk-qubit gates on distinct kkk-qubit subsets of nnn logical qubits can be ordered and parallelized in O(nk−1)O(n^{k-1})O(nk−1) depth using a linear arrangement of nnn physical qubits; the construction is completely general and achieves optimal scaling in the case where gates acting on all (nk)\binom{n}{k}(kn​) sets of kkk qubits are desired. We highlight two classes of problems for which our method is particularly useful. First, it applies to sets of mutually commuting gates, as in the (diagonal) phase separators of Quantum Alternating Operator Ansatz (Quantum Approximate Optimization Algorithm) circuits. For example, a single level of a QAOA circuit for Maximum Cut can be implemented in linear depth, and a single level for 333-SAT in quadratic depth. Second, it applies to sets of gates that do not commute but for which compilation efficiency is the dominant criterion in their ordering. In particular, it can be adapted to Trotterized time-evolution of fermionic Hamiltonians under the Jordan-Wigner transformation, and also to non-standard mixers in QAOA. Using our method, a single Trotter step of the electronic structure Hamiltonian in an arbitrary basis of nnn orbitals can be done in O(n3)O(n^3)O(n3) depth while a Trotter step of the unitary coupled cluster singles and doubles method can be implemented in O(n2η)O(n^2 η)O(n2η) depth, where ηηη is the number of electrons.
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid algorithm to solve hard combinatorial optimization problems. The multi-qubit CPHASE gates used in the quantum circuit for QAOA are commutative i.e., the order of the gates can be altered without changing the output state. This re-ordering leads to the execution of more gates in parallel and a smaller number of additional SWAP gates to compile the QAOA-circuit. Consequently, the circuit-depth and cumulative gate-count become lower which is beneficial for circuit execution time and noise resilience. A less number of gates indicates a lower accumulation of gate-errors, and a reduced circuit-depth means less decoherence time for the qubits. However, finding the best-ordered circuit is a difficult problem and does not scale well with circuit size. This paper presents four generic methodologies to optimize QAOA-circuits by exploiting gate re-ordering. We demonstrate a reduction in gate-count by ≈23.0% and circuit-depth by ≈53.0% on average over a conventional approach without incurring any compilation-time penalty. We also present a variation-aware compilation which enhances the compiled circuit success probability by ≈62.7% for the target hardware over the variation unaware approach. A new metric, Approximation Ratio Gap (ARG), is proposed to validate the quality of the compiled QAOA-circuit instances on actual devices. Hardware implementation of a number of QAOA instances shows ≈25.8% improvement in the proposed metric on average over the conventional approach on ibmq 16 melbourne.