Linear and logarithmic time compositions of quantum many-body operators

Understand

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.