Shortest Path in Pauli Forest - An Algorithm for Decomposing Pauli Exponentials to Quantum Circuits

Decomposing Pauli exponentials efficiently to quantum circuits has been the subject of intense research in recent years. Pauli exponentials are an essential component of many different quantum algorithms. Due to the error-prone nature of current and near term quantum devices, it is crucial that quantum circuits are as compact as possible. Several different types of algorithms have been developed to decompose Pauli exponentials into as short circuits as possible. We propose a novel algorithm for architecture-aware synthesis of Pauli exponentials that also determines the initial qubit placement on the device. We call this the Shortest Path in Pauli Forest algorithm. The results show an improved CNOT count and runtime for both random Pauli exponentials and molecular ansätze.