SWAP-less Implementation of Quantum Algorithms

Abstract

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 $5n-3$ and requiring $n^2-1$ CNOT 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 bi-linear connectivity, which approximately halves the circuit depth.

10 pages, 5 figures

References in corpus (28)

• Quantum Computing in the NISQ era and beyond
• Improved Simulation of Stabilizer Circuits
• Logical quantum processor based on reconfigurable atom arrays
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum computing with neutral atoms
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• A Race Track Trapped-Ion Quantum Processor
• A universal gate for fixed-frequency qubits via a tunable bus
• Blueprint for a microwave trapped-ion quantum computer
• Low Depth Quantum Simulation of Electronic Structure
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Noisy intermediate-scale quantum computers
• Quantum circuit optimizations for NISQ architectures
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Phase Gadget Synthesis for Shallow Circuits
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Impact of qubit connectivity on quantum algorithm performance
• Parity Quantum Optimization: Compiler
• Architecture aware compilation of quantum circuits via lazy synthesis
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Parity Quantum Computing as YZ-Plane Measurement-Based Quantum Computing
• Hardware-Efficient Quantum Random Access Memory Design with a Native Gate Set on Superconducting Platforms
• Flexible constraint compilation in the parity architecture
• Constant Depth Code Deformations in the Parity Architecture
• The Parity Flow Formalism: Tracking Quantum Information Throughout Computation

Cited by in corpus (2)

• The Parity Flow Formalism: Tracking Quantum Information Throughout Computation
• Congestion-free routing on quantum chips