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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Connectivity-Aware Synthesis of Quantum Algorithms

Christoph Fleckenstein, Florian Dreier, Gregor Aigner, Michael Fellner, Reinhard Stahn, Martin Lanthaler, Wolfgang Lechner

Published Aug 30, 2025• 0 citations
Publisher

Abstract

We propose a versatile method for implementing quantum algorithms that simultaneously minimizes gate count and circuit depth. Central to our approach are Parity Twine chains-CNOT-based building blocks tailored to hardware connectivity. This technique surpasses existing state-of-the-art methods in executing key quantum algorithms, including the Quantum Fourier Transform and the Quantum Approximate Optimization Algorithm, across various quantum hardware architectures such as linear chains, square grids, hexagonal lattices, ladders, and fully connected systems.

DOI
10.1109/qce65121.2025.10362

Related papers

Connectivity-aware Synthesis of Quantum Algorithms

Florian Dreier, Christoph Fleckenstein, Gregor Aigner +5 more

We present a general method for the implementation of quantum algorithms that optimizes both gate count and circuit depth. Our approach introduces connectivity-adapted CNOT-based building blocks called Parity Twine chains. It outperforms all known state-of-the art methods for implementing prominent quantum algorithms such as the quantum Fourier transform or the Quantum Approximate Optimization Algorithm across a wide range of quantum hardware, including linear, square-grid, hexagonal, ladder and all-to-all connected devices. We show that even moderate increments in connectivity can yield significant efficiency improvements and reach the proven optimum for specific cases. Furthermore, we demonstrate a practical performance advantage of this approach for a wide range of compilation problems and quantum hardware.

arXiv:2501.14020•Jan 23, 2025•2 citations

Optimizing Atom Transport, Gate-Count and Depth with Parity Twine

Javad Kazemi, Michael Fellner, Riccardo J. Valencia-Tortora +2 more

We present an efficient implementation of the Parity Architecture for neutral-atom quantum processors. We adapt Parity Twine Networks (PTNs) to different atom layouts, native entangling gates, and atom-shuttling capabilities. This provides a general framework for hardware-aware optimization of gate count, circuit depth, and atom transport for quantum circuits encoding arbitrary interaction graphs in a common basis. Specifically, we develop PTN constructions based on different native entangling-gate realizations, namely CZ, CZSWAP, and iSWAP, providing flexibility to accommodate different hardware capabilities on both static and mobile neutral-atom platforms. Using the quantum Fourier transform (QFT) as a representative example, we demonstrate substantial reductions in two-qubit gate count, atom transport, and circuit depth. These resource savings translate into an estimated circuit fidelity three orders of magnitude higher than competing compilation strategies for a 30-qubit QFT. We further extend the construction to the recently introduced optimistic QFT and discuss the broader applicability of PTNs to other quantum algorithms on neutral-atom platforms.

quant-pharXiv:2609.03583•Sep 4, 2026•0 citations

SWAP-less implementation of quantum algorithms

Berend Klaver, Stefan M. A. Rombouts, Michael Fellner +4 more

We present a formalism based on tracking the flow of parity quantum information to implement algorithms on devices with limited connectivity without qubit overhead, SWAP operations, or shuttling. Instead, we leverage the fact that entangling gates not only manipulate quantum states but can also be exploited to transport quantum information. We demonstrate the effectiveness of this method by applying it to the quantum Fourier transform (QFT) and the quantum approximate optimization algorithm (QAOA) with n qubits. This improves upon all state-of-the-art implementations of the QFT on a linear nearest-neighbor architecture, resulting in a total circuit depth of 5 n − 3 and requiring n 2 − 1 gates. For the QAOA, our method outperforms SWAP networks, which are currently the most efficient implementation of the QAOA on a linear architecture. We further demonstrate the potential to balance qubit count against circuit depth by implementing the QAOA on twice the number of qubits using bilinear connectivity, which approximately halves the circuit depth.

arXiv:2408.10907•Physical Review A•Sep 9, 2025•4 citations

Architecture-aware Unitary Synthesis

Frans Perkkola, Arianne Meijer-van de Griend, Jukka K. Nurminen

We present a novel architecture-aware transpilation method for exact general unitary gate synthesis on superconducting quantum hardware. Our approach is tightly integrated with the optimized block-ZXZ decomposition, exploiting its recursive structure to make hardware-aware decisions at each level of the recursion rather than treating transpilation as an independent post-processing step. The method introduces three key techniques: a greedy qubit mapping strategy that minimizes pairwise distances between physical qubits, an adaptive Gray code selection combined with qubit swapping that optimizes the construction of uniformly controlled Rz gates for the target topology, and a heuristic for reducing CNOT gates by exploiting the structure of long-range CNOT ladders. We benchmark our method against TKet, Qiskit, and Pennylane on the 20-qubit IQM Garnet (square lattice) and the 156-qubit IBM Marrakesh (heavy-hex) architectures with qubit counts ranging from 3 to 11. Our method achieves CNOT count reductions of up to 36 percent on the IQM Garnet and up to 34 percent on the IBM Marrakesh compared to the best competing transpiler, while simultaneously achieving transpilation speedups of up to 553x. Furthermore, our method is the only one capable of transpiling circuits beyond 10 qubits within a 30-minute time limit across both architectures.

quant-pharXiv:2604.23777•Apr 28, 2026•0 citations

Shallower CNOT Circuits on Realistic Quantum Hardware

Timothée Goubault de Brugière, Simon Martiel

We focus on the depth optimization of CNOT circuits on hardware with limited connectivity. We adapt the algorithm from Kutin et al. that implements any n -qubit CNOT circuit in depth at most 5n on a Linear Nearest Neighbor architecture. Our proposal is a block version of Kutin et al.’s algorithm that is scalable with the number of interactions available in the hardware: the more interactions we have, the less the depth. We derive better theoretical upper bounds and provide a simple implementation of the algorithm. Overall, we achieve better depth complexity for CNOT circuits on some realistic quantum hardware like a grid or a ladder. For instance, the execution of an n -qubit CNOT circuit on a grid can be done in depth 4n+8 .

arXiv:2303.07302•ACM Transactions on Quantum Computing•Nov 5, 2024•2 citations

Towards Optimal Topology Aware Quantum Circuit Synthesis

Marc G. Davis, Ethan Smith, Ana Tudor +3 more

We present an algorithm for compiling arbitrary unitaries into a sequence of gates native to a quantum processor. As CNOT gates are error-prone for the foreseeable Noisy-Intermediate-Scale Quantum devices era, our A* inspired algorithm minimizes their count while accounting for connectivity. We discuss the formulation of synthesis as a search problem as well as an algorithm to find solutions. For a workload of circuits with complexity appropriate for the NISQ era, we produce solutions well within the best upper bounds published in literature and match or exceed hand tuned implementations, as well as other existing synthesis alternatives. In particular, when comparing against state-of-the-art available synthesis packages we show 2.4× average (up to 5.3×) reduction in CNOT count. We also show how to re-target the algorithm for a different chip topology and native gate set while obtaining similar quality results. We believe that tools like ours can facilitate algorithmic exploration and guide gate set discovery for quantum processor designers, as well as being useful for optimization in the quantum compilation tool-chain.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•88 citations
We propose a versatile method for implementing quantum algorithms that simultaneously minimizes gate count and circuit depth. Central to our approach are Parity Twine chains-CNOT-based building blocks tailored to hardware connectivity. This technique surpasses existing state-of-the-art methods in executing key quantum algorithms, including the Quantum Fourier Transform and the Quantum Approximate Optimization Algorithm, across various quantum hardware architectures such as linear chains, square grids, hexagonal lattices, ladders, and fully connected systems.
We present a general method for the implementation of quantum algorithms that optimizes both gate count and circuit depth. Our approach introduces connectivity-adapted CNOT-based building blocks called Parity Twine chains. It outperforms all known state-of-the art methods for implementing prominent quantum algorithms such as the quantum Fourier transform or the Quantum Approximate Optimization Algorithm across a wide range of quantum hardware, including linear, square-grid, hexagonal, ladder and all-to-all connected devices. We show that even moderate increments in connectivity can yield significant efficiency improvements and reach the proven optimum for specific cases. Furthermore, we demonstrate a practical performance advantage of this approach for a wide range of compilation problems and quantum hardware.
We present an efficient implementation of the Parity Architecture for neutral-atom quantum processors. We adapt Parity Twine Networks (PTNs) to different atom layouts, native entangling gates, and atom-shuttling capabilities. This provides a general framework for hardware-aware optimization of gate count, circuit depth, and atom transport for quantum circuits encoding arbitrary interaction graphs in a common basis. Specifically, we develop PTN constructions based on different native entangling-gate realizations, namely CZ, CZSWAP, and iSWAP, providing flexibility to accommodate different hardware capabilities on both static and mobile neutral-atom platforms. Using the quantum Fourier transform (QFT) as a representative example, we demonstrate substantial reductions in two-qubit gate count, atom transport, and circuit depth. These resource savings translate into an estimated circuit fidelity three orders of magnitude higher than competing compilation strategies for a 30-qubit QFT. We further extend the construction to the recently introduced optimistic QFT and discuss the broader applicability of PTNs to other quantum algorithms on neutral-atom platforms.
We present a formalism based on tracking the flow of parity quantum information to implement algorithms on devices with limited connectivity without qubit overhead, SWAP operations, or shuttling. Instead, we leverage the fact that entangling gates not only manipulate quantum states but can also be exploited to transport quantum information. We demonstrate the effectiveness of this method by applying it to the quantum Fourier transform (QFT) and the quantum approximate optimization algorithm (QAOA) with n qubits. This improves upon all state-of-the-art implementations of the QFT on a linear nearest-neighbor architecture, resulting in a total circuit depth of 5 n − 3 and requiring n 2 − 1 gates. For the QAOA, our method outperforms SWAP networks, which are currently the most efficient implementation of the QAOA on a linear architecture. We further demonstrate the potential to balance qubit count against circuit depth by implementing the QAOA on twice the number of qubits using bilinear connectivity, which approximately halves the circuit depth.
We present a novel architecture-aware transpilation method for exact general unitary gate synthesis on superconducting quantum hardware. Our approach is tightly integrated with the optimized block-ZXZ decomposition, exploiting its recursive structure to make hardware-aware decisions at each level of the recursion rather than treating transpilation as an independent post-processing step. The method introduces three key techniques: a greedy qubit mapping strategy that minimizes pairwise distances between physical qubits, an adaptive Gray code selection combined with qubit swapping that optimizes the construction of uniformly controlled Rz gates for the target topology, and a heuristic for reducing CNOT gates by exploiting the structure of long-range CNOT ladders. We benchmark our method against TKet, Qiskit, and Pennylane on the 20-qubit IQM Garnet (square lattice) and the 156-qubit IBM Marrakesh (heavy-hex) architectures with qubit counts ranging from 3 to 11. Our method achieves CNOT count reductions of up to 36 percent on the IQM Garnet and up to 34 percent on the IBM Marrakesh compared to the best competing transpiler, while simultaneously achieving transpilation speedups of up to 553x. Furthermore, our method is the only one capable of transpiling circuits beyond 10 qubits within a 30-minute time limit across both architectures.
We focus on the depth optimization of CNOT circuits on hardware with limited connectivity. We adapt the algorithm from Kutin et al. that implements any n -qubit CNOT circuit in depth at most 5n on a Linear Nearest Neighbor architecture. Our proposal is a block version of Kutin et al.’s algorithm that is scalable with the number of interactions available in the hardware: the more interactions we have, the less the depth. We derive better theoretical upper bounds and provide a simple implementation of the algorithm. Overall, we achieve better depth complexity for CNOT circuits on some realistic quantum hardware like a grid or a ladder. For instance, the execution of an n -qubit CNOT circuit on a grid can be done in depth 4n+8 .
We present an algorithm for compiling arbitrary unitaries into a sequence of gates native to a quantum processor. As CNOT gates are error-prone for the foreseeable Noisy-Intermediate-Scale Quantum devices era, our A* inspired algorithm minimizes their count while accounting for connectivity. We discuss the formulation of synthesis as a search problem as well as an algorithm to find solutions. For a workload of circuits with complexity appropriate for the NISQ era, we produce solutions well within the best upper bounds published in literature and match or exceed hand tuned implementations, as well as other existing synthesis alternatives. In particular, when comparing against state-of-the-art available synthesis packages we show 2.4× average (up to 5.3×) reduction in CNOT count. We also show how to re-target the algorithm for a different chip topology and native gate set while obtaining similar quality results. We believe that tools like ours can facilitate algorithmic exploration and guide gate set discovery for quantum processor designers, as well as being useful for optimization in the quantum compilation tool-chain.