Linear and Logarithmic Time Compositions of Quantum Many-Body Operators

We develop a generalized framework for constructing many-body-interaction operations either in linear time or in logarithmic time with a linear number of ancilla qubits. Exact gate decompositions are given for Pauli strings, many-control Toffoli gates, number- and parity-conserving interactions, unitary coupled cluster operations, and sparse matrix generators. We provide a linear time protocol that works by creating a superposition of...