Connectivity-aware Synthesis of Quantum Algorithms

Understand

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.