Connectivity-aware Synthesis of Quantum Algorithms

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. {\color{blue} 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.