SWAP-less implementation of quantum algorithms

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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"> <a:mi>n</a:mi> </a:math> 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 <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"> <b:mrow> <b:mn>5</b:mn> <b:mi>n</b:mi> <b:mo>−</b:mo> <b:mn>3</b:mn> </b:mrow> </b:math> and requiring <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"> <c:mrow> <c:msup> <c:mi>n</c:mi> <c:mn>2</c:mn> </c:msup> <c:mo>−</c:mo> <c:mn>1</c:mn> </c:mrow> </c:math> 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.