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• 2 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

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•6 citations

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•22 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•132 citations

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.

arXiv:2505.17944•Physical Review Applied•Jun 30, 2026•1 citation

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•15 citations

Optimized QAOA ansatz circuit design for two-body Hamiltonian problems

Ritajit Majumdar, Dhiraj Madan, Debasmita Bhoumik +3 more

Quantum Approximate Optimization Algorithm (QAOA) is a prospective candidate for providing quantum advantage in finding approximate solutions to optimization problems using near-term quantum devices. In this paper, the goal is to reduce the number of CNOT gates and the depth of quantum ansatz circuits for QAOA. First, we present a generalized QAOA formulation for any Hamiltonian that involves upto two-body interactions, as a graph. The circuit realization of the depth-p QAOA requires $2mp$ CNOT gates where the graph for the Hamiltonian has n vertices and m edges. Presently, a CNOT gate is one of the primary sources of error. We propose a graph-theoretic algorithm which can eliminate $n-1$ CNOTs from the QAOA ansatz while retaining functional equivalence with the original circuit. This improves upon previously proposed Depth First Search (DFS) method by restricting the increase in depth of the circuit, which was a drawback of the method, by $\simeq 84.8\%$ for Erdős-Renyi graphs. Finally, if the underlying connectivity (hardware coupling map) and the initial qubit placement for a hardware are known, then we present how to extend the greedy heuristic method in order to obtain a functionally equivalent circuit with $\simeq 5\%$; fewer SWAP gates for Erdős-Renyi graphs.

International Conference on VLSI Design•Jan 6, 2024•6 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.
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.
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.
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.
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.
Quantum Approximate Optimization Algorithm (QAOA) is a prospective candidate for providing quantum advantage in finding approximate solutions to optimization problems using near-term quantum devices. In this paper, the goal is to reduce the number of CNOT gates and the depth of quantum ansatz circuits for QAOA. First, we present a generalized QAOA formulation for any Hamiltonian that involves upto two-body interactions, as a graph. The circuit realization of the depth-p QAOA requires 2mp2mp2mp CNOT gates where the graph for the Hamiltonian has n vertices and m edges. Presently, a CNOT gate is one of the primary sources of error. We propose a graph-theoretic algorithm which can eliminate n−1n-1n−1 CNOTs from the QAOA ansatz while retaining functional equivalence with the original circuit. This improves upon previously proposed Depth First Search (DFS) method by restricting the increase in depth of the circuit, which was a drawback of the method, by ≃84.8%\simeq 84.8\%≃84.8% for Erdős-Renyi graphs. Finally, if the underlying connectivity (hardware coupling map) and the initial qubit placement for a hardware are known, then we present how to extend the greedy heuristic method in order to obtain a functionally equivalent circuit with ≃5%\simeq 5\%≃5%; fewer SWAP gates for Erdős-Renyi graphs.