Low-depth parallelization of k-local gates and applications

Practical use of near-term quantum computers requires taking their limited connectivity into account when realizing quantum circuits. We address this embedding problem for families of quantum circuits defined by a hypergraph where each hyperedge corresponds to a potential gate. We show that any set of k-local gates on n logical qubits can be ordered and parallelized in O(n^k-1) depth using a linear arrangement of n physical qubits. The construction is completely general and achieves optimal scaling in the worst case. We demonstrate benefits of this construction for i) sets of mutually commuting gates, as encountered in the Quantum Alternating Operator Ansatz circuits of the generalized QAOA algorithm, and ii) sets of gates that do not commute but for which compilation efficiency is the dominant criterion in their ordering. We find polynomial speedups in cost with number of spin-orbitals and electrons for Trotterized time-evolution of fermionic Hamiltonians under the Jordan-Wigner transformation.