  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 in particular 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
exponentially many different possible operator strings and then uses dynamical
decoupling methodology to undo all the unwanted terms. A logarithmic time
protocol overcomes the speed limit of the first by using ancilla registers to
condition evolution to the support of the desired many-body interaction before
using parallel chaining operations to expand the string length. The two
techniques improve substantially on current strategies (reductions in time and
space can range from linear to exponential), are applicable to different
physical interaction mechanisms such as CNOT, $XX$, and $XX+YY$, and generalize
to a wide range of many-body operators.
