\section{Introduction}
Generating multi-body entanglement is the hallmark of most quantum information technologies.  Such technologies promise to harness entanglement across multiple quantum registers to enable potentially significant improvements in speed or precision compared to their classical counterparts. Yet much of the difficulty in the control of quantum systems lies in the constraint that entanglement naturally arises on a local scale while scaling improvements occur as a result of wave functions spread over much larger spaces. 

Quantum circuits generating entanglement across $n$ qubits in linear or sub-linear time (circuit depth) in $n$ have been the subject of many studies, with direct use as subroutines in quantum algorithms for factoring \cite{cleve2000fast, shor}, simulation
\cite{lloyd0,harrow2009quantum,aag1,barends1,aag2,aag3,troyer,ryan1,wiebe2011simulating,jarrod1,pl,borzu,ryan2}, unstructured search \cite{molmer2011efficient, page}, error-correction \cite{crow2016improved}, and solutions to systems of differential equations \cite{harrow2009quantum,berry,aharonov2003adiabatic,wiebe2011simulating}.  Much progress has been made for constructing many-body operations, with the most success coming from either finding architectures where commuting two-qubit interactions could be executed simultaneously on overlapping Hilbert spaces, or via cases where a particular many-body gate with known or suspected sublinear implementation can be used to synthesize other many-body circuits.  The former has been used for so-called \emph{collective} Pauli operations on qubits in ion chains \cite{molmer,blatt2000quantum,monz201114}, while the workhorse for the latter has been the \emph{fanout} operation\cite{moore2001parallel,fenner2005bounds}, which has successfully lead to $O(\log(n))$ depth quantum circuits for various flavours of quantum adders \cite{takahashi2008fast,gossett1998quantum,svore}, with related arithmetic operations \cite{van2005fast,cleve2000fast}.  

Other many-body interactions have also been synthesized to mixed success.  The ubiquitous many-control CNOT has found general linear-depth implementations, though with a relatively large prefactor \cite{maslov1,barenco1,maslov}.  Another commonly used gate is defined in terms of the rotation between two arbitrary multi-qubit states, for use in sparse matrix generation \cite{aharonov2003adiabatic,wiebe2011simulating,berry2014exponential,harrow2009quantum}, or, equivalently, pairwise inversion of opposing spins in Unitary Coupled Cluster (UCC) theory \cite{bartlett1,bartlett2,jonathan,kutzelnigg,hoffmann}.  Here, suggested implementations have typically involved (based on intended application) either a linear ancilla memory operated on with multi-control rotations \cite{aharonov2003adiabatic,wiebe2011simulating}, or Trotter decomposition of the dynamics into (exponentially many) Pauli-string factors but with no ancillas.

In this work, we provide a generic formalism for how to directly compose a wide class of such many-body entangling operations (generated each by an equivalent Hermitian many-body operator $\bar H$)  via two-(or few-)local interactions, and for which the above discussed protocols and algorithms form important examples of its application.  We aim to minimize two standard figures of merit of the generic circuit, namely its \textit{depth}, defined as the number of layers of gates acting simultaneously on disjoint sets of qubits, and its \textit{width}, defined as the total number of qubits acted on by the circuit \cite{bera}. We find a width-optimized general algorithm, which we label the \textit{decoupling protocol}, to compose $\bar H$ with zero or constant memory overhead and depth limited to linear $n$ scaling. Moreover, we demonstrate a depth-optimized algorithm for simulating $\bar H$, the \textit{selection protocol}, which has logarithmic depth and requires at most linear memory overhead. We demonstrate the formalism towards a linear to exponential speed-up of the aforementioned examples, given in our notation by equivalent Hamiltonians
\begin{align*}
\bar H=\begin{cases}
& \prod_{i=1}^nX_i \ \quad\text{(n-qubit Pauli strings)}\\
&(\prod_{i=1}^n P_i)X_{n+1} \ \text{(n-controlled X gate)}\\
&\prod_{i=1}^{n/2}(\sigma^+_{2i-1}\sigma^-_{2i}+h.c.) \ \text{(number/parity consv.)}\\
&(\prod_{i=1}^n\sigma_i^+)+h.c.\  \text{(UCC-type operators,}\\
&\qquad \qquad\qquad\qquad\ \text{sparse matrix generators)},
\end{cases}
\end{align*}
where $X_i$,$Y_i$ and $Z_i$ are Pauli operators acting on qubit $i$, $\sigma_j^\pm=(X_j\mp iY_j)/2$ and projector $P_i={\ket{1}}\bra{1}_i$. The unitary circuit generated by the many-body composed dynamics can then be written succinctly via the notation
\begin{align}
[\bar H]^\alpha\equiv\exp(-i\alpha\bar H), 
\end{align}
with $\alpha$ the rotation angle. 


In order to identify the type of Hamiltonians we can compose, we first introduce notation and conventions. For simplicity, we disregard local unitary transformations between operators of the same rank. Let $\mathcal H=\mathcal H_1\otimes\mathcal H_2\otimes \dots \otimes \mathcal H_n$ denote a separable Hilbert space. Then $R_i=\mathds 1^{\otimes(i-1)}\otimes R\otimes \mathds 1^{\otimes(n-i)}$, where $\mathds 1_j$ denotes the identity on $\mathcal H_j$ and $R$ ($\neq \mathds 1$) is a $2\times 2$-Hermitian matrix for qubits (or $d\times d$ for qudits). 
We use the convention $\text{rank}(R_i)\equiv\text{rank}(R)$, thereby ignoring contributions from identities $\bigotimes_{\jmath\neq i}\mathds 1_j$ on other sub-Hilbert spaces.  
We can write a higher-rank $R_i$ as the tensor sum
$R=V(S\oplus{S^\perp})V^\dagger$, where $V$ is any local unitary transformation 
 (i.e.~$S^\perp$ lies in the kernel of $S$). 
It is by chaining together the lower-rank $S_i$ factors that we will be able to construct our many-body dynamics $\bar H$. 



\section{Decoupling protocol} Our main tool is a unitary (two- or few-body) operator $U_{j-1,j}$ which will be used to iteratively increase in length a string of Hermitian operators $S_1S_2\cdots S_j$ acting on the system. However recall that generally $S_j$ will not be full rank, and so $U_{j-1,j}$ will invariably have to also act outside the support of $S$. Thus, our protocol will have to execute the desired system dynamics (given by $\bar H$) while leaving the rest of the Hilbert space (namely the kernels of $S_j$) intact.
A condition to using the protocol is that a $U_{i,j}$ can be found  such that
\begin{align}
U_{i,j}^\dag R_iU_{i,j}=S_iR_j+S_i^\perp+S_iR_j^\perp,  \label{u}
\end{align}
thereby incrementing the length of a string of non-identity Hermitian operators by one when acting on $R_i$. Then, successively applying Eq.~(\ref{u}), one can show that the following sum of operator strings of increasing string length can be composed 
\begin{align}
\hat H =& \left(\prod_{j=n}^1U_{j,j+1}^\dag\right)R_1\left(\prod_{j=1}^nU_{j,j+1}\right)\nonumber\\
=&\left(\prod_{i=1}^nS_i\right)R_{n+1}+\sum_{m=1}^n\left(\prod_{i=1}^{m-1}S_i\right)\left(S_{m}R_{m+1}^\perp+S_m^\perp\right)\nonumber\\
\equiv&\bar H+\Sigma_{\text{res}}, \label{h} 
\end{align}
as shown in Fig. \ref{fig:0b}, where $\bar H=(\prod_{i=1}^nS_i)R_{n+1}$. Therefore, composing $\bar H$ from two-body operators $U_{i,j}$ usually creates unwanted remainder terms $\Sigma_{\text{res}}$. However, the remainder terms commute with $\bar H$, while also acting as the identity on the support of  $R_{n+1}$.  Thus, we can find a one-body unitary transformation $M_{n+1}$ such that it imparts an opposite phase to $R_{n+1}$ (and thus $\bar H$), but does not  change $\Sigma_{\text{res}}$ \cite{mikecomment}. The requisite dynamics can then be recovered using the decoupling sequence (cf.~Fig.~\ref{fig:0a})
\begin{align}
[\bar H]^{2\alpha}=\left[ \hat H\right]^\alpha M_{n+1}^\dag \left[\hat H\right]^{-\alpha} M_{n+1}\label{dd}.
\end{align}
Here, to construct an effective Hamiltonian $\bar{H}$ of string-length $n+1$, a total of $4n$ unitary operators $U_{i,j}$ are needed. Note that if $R$ is full rank, Eq.~(\ref{u}) reduces to $U_{i,j}^\dag R_iU_{i,j}=R_iR_	j$ and only half as many operators are used, since decoupling is not required. 

\begin{figure}[h!]
	\includegraphics[width=.46\textwidth]{circuit1_7.eps}
	\caption{Generating the unitary dynamics $[\hat H]^\alpha=[\bar H+\Sigma_{\text{res}}]^\alpha$ of Eq.~(\ref{h}) using one single-body and $2n$ $U_{j-1,j}$ operators. \label{fig:0b}}
\end{figure}
\begin{figure}[h!]
	\includegraphics[width=.4\textwidth]{circuit1_6.eps}
	\caption{Gate sequence for realizing the decoupling protocol given in Eq. (\ref{dd}) using $4n$ $U_{j-1,j}$ operators.\label{fig:0a}}
\end{figure}

\section{Selection Protocol}
We now present a composition scheme that can further decrease the required circuit depth for $n$-body operators from a $\mathcal{O}(n)$ to a $\mathcal{O}(\text{log}(n))$ scaling, at the cost of $n-1$ ancillas (cf. Figs. \ref{fig:1} and \ref{fig:2}).  Without loss of generality we set $n=2^m$ where $m\in\mathds{N}$ and introduce two sets of qubit indices, namely register qubits $q_{\text{reg}}=\{1,2,...,n+1\}$ containing the qubits of the desired string and ancilla qubits $q_{\text{anc}}=\{n+2,2,...,2n\}$, where the latter are all initialized to the $\ket{0}$ state. 

Moreover, we introduce Toffoli-type unitary operators $C_{i,j}X_{k}$, whereby a NOT is applied to qubit $k$ conditioned on the state of qubits $i,j$ which can either be register or ancilla qubits. The operation can be written mathematically as e.g.~$C_{i,j}X_{k}=[S_iS_jX_k]^{\pi/2}$. For $i,j\in q_{\text{reg}}$, $C_{i,j}$ essentially conditions on being in the support of both $S_i$ and $S_j$. If $i,j\in q_{\text{anc}}$, the operation is a standard Toffoli (or simply letting projector $S_i=\ket{1}\bra{1}_i$). Note that if $n$ is not a power of $2$, some $C_{i,j}X_k$ operations can have both register and ancilla qubits as controls.
We define as in Fig.~\ref{fig:1} compound operations
\begin{align}
C_{\text{tot}}\equiv&\prod_{k=1}^{\log n}\left(\prod_{l=n-2^{k}+1}^{n-2^{k-1}}C_{2l+1,2l}X_{n+l+1}\right),\\
U_{\text{tot}}\equiv&\prod^{1}_{k=\log n}\left(\prod_{l=1}^{n/2^{k}}U_{l 2^{k}+1,(l-\frac{1}{2}) 2^{k}+1} \right)U_{1,n+1}.\label{ctot}.
\end{align}
For the boundary case $\text{rank}(S)=1$, we set $U_{\text{tot}}=\mathds{1}$, while if $S$ full rank then $C_{\text{tot}}=\mathds{1}$.
All the operations in the brackets can be run parallel.
The full selection protocol is given by the sequence
\begin{align}
[\bar H]^\alpha
U_{\text{tot}}^\dag C_{\text{tot}}^\dag\left(C[R_{1}]^\alpha\right)C_{\text{tot}} U_{\text{tot}}, \label{vc}
\end{align}
see Fig. \ref{fig:2}. The middle operator is defined as $C[R_{1}]^\alpha=[R_{1}]^\alpha$ if S full rank, and $[\ket{1}\bra{1}_{2n}R_{1}]^\alpha$ otherwise. The result of the sequence is that the many-body rotation is applied only on states that are supported by $R_{1}S_2 \cdots S_n$, while identity is applied otherwise.  The selection protocol improves on generic parallelization algorithms by quadratically reducing the space requirements \cite{moore2001parallel}.

The following sections demonstrate how to apply the \textit{decoupling} and \textit{selection protocols} to well-known existing problems, to either take advantage of specific two-body interaction mechanisms, or to reduce the time and gate complexity of known implementations. Further details of the derivations are given in Appendix B.
\begin{figure}
	\includegraphics[width=.48\textwidth]{f3v2.eps}
	\caption{Gate sequence to compose an operator string of length $n=9$, to run in $O(\log n)$ depth. Here, we assume that $1<\text{rank}(S_i)<\text{rank}(S_i+S_i^\perp)$ for $i>1$. Small empty circles are conditioning operators (projectors) on the support of $S$ while solid circles are conventional Toffoli gates.  The connected $U$ are the entangling operations from Eq. (\ref{u}). Since $R_1\equiv S_1$ is only applied on the support of $S_2...S_9$, $\hat H$ (which is created by the $U_{i,j}$ tree structure) is also only applied on the support of $\bar H$. \label{fig:1}}
\end{figure}
\begin{figure}
	\includegraphics[width=.4\textwidth]{circuit1_3.eps}
	\caption{Generalized version of Fig. (\ref{fig:1}), where all register (resp. ancillary) qubits $\mathbf q_{\text{reg}}$ and $\mathbf q_{\text{anc}}$ are compounded to one circuit line. All operations that can be run in parallel are synthesized to one box, with the number above it indicating how many non-commutative time steps are necessary for each box. For $n=2^m$, a string of length $n+1$ is composed in $\mathcal{O}(\text{log}(n))$ depth. \label{fig:2}}
\end{figure}


\section{Pauli strings}
Well known formulas exist for forming strings of Pauli operators in linear time (e.g. \cite{nielsen,mezzacapo}), which we first reproduce using our formalism. Since Pauli operators are full rank, $\hat H=S_1 S_2 \cdots S_j=\bar H$ and there is no need for decoupling. The optimal form of $U_{i,j}$ will depend on the architecture and its natural interaction. A standard entangling operation is  via $U_{i,j}=\text{CNOT}_{ij}$ gates \cite{nielsen}, which applied as in Fig.~\ref{fig:0b} produce a many-body operator \eqref{h} with $S_i=X_i$. However this interaction is neither natural for superconducting nor trapped ion qubits. A native  gate for ion-trap designs is the M\o{}lmer-S\o{}rensen gate (MSG), where commuting $U_{i,j}=[X_iX_j]^{\tfrac{\pi}{4}}$ \cite{molmer,molmerII} interactions can be applied simultaneously to all pairs of ions in the chain. We present a third composition with the same gate count as the CNOT and MSG circuits, designed for architectures with exchange gate interactions, $G_{i,j}=\frac{1}{2}(X_iX_j+Y_iY_j)$. This is the fastest perfect entangler for most circuit-QED quantum processors \cite{goerz, siewert}, as well as for quantum dot spins coupled by a cavity \cite{imamoglo} and nuclear spins interacting via a two-dimensional electron gas \cite{mozyrsky}. Here, $U_{i,j}=[G_{i,j}]^{-\tfrac{\pi}{2}}$ is an iSWAP gate. Using Eq. (\ref{u}) and $U_{i,j}^\dag Y_iU_{i,j}=Z_iX_i$ allows us to construct a Pauli-string of length $n$ using $2(n-1)$ iSWAPs. Since the Pauli operators are full rank, one can drastically reduce the depth of the circuit from $\mathcal{O}(n)$ to $\mathcal{O}(\text{log}(n))$ by using Eq.~\eqref{vc}, with $\prod_{i=1}^{n}S_i=U_{\text{tot}}^\dag R_1 U_{\text{tot}}$, without needing any ancillary qubits.

Note further that instead of increasing the length of the string using  $U_{i,j}$, one can also use the inverse operation to remove a qubit from the string, e.g.~to form a disconnected string from a nearest neighbour architecture.

\section{Number- and parity-conserving strings}
We now turn to generating many-body operators that act conditionally only within the fixed excitation-number subspace. These are natural fit for a two-body, exchange gate interaction, $G^+_{i,j}=\sigma_i^+\sigma_j^-+\sigma_i^-\sigma_j^+$, which has the same symmetry, noting also its rank is smaller than $\dim(\mathcal H_i\otimes \mathcal H_j)$. Defining $F^-_{i,j}=-i(\sigma_i^+\sigma_j^--\sigma_i^-\sigma_j^+)$, we desire strings of $R_{i,j}\in\{G_{i,j},F_{i,j}\}$. We choose $U_{i,k,l}=[Z_iG_{k,l}]^{\tfrac{\pi}{4}}$ as the (now three-qubit) entangling operation, giving $U_{i,k,l}^\dag G_{i,j}U_{i,k,l}=F_{i,j}G_{k,l}+G_{i,j}P_{\text{ker}\{G_{k,l}\}}$, where $R_{k,l}^\perp=\tfrac{1}{2}(\mathds 1+Z_kZ_l)$. Following the steps in Eq.~\eqref{h}, one obtains 
\begin{align}
\hat H=&\prod_{i=1}^{n/2}R_{2i-1,2i}+\sum_{i=1}^{n/2-1}\left(\prod_{j=1}^iR_{2j-1,2j}\right)R_{2i+1,2i+2}^\perp.
\end{align}
a many-body Hamiltonian that collectively excites and de-excites $n$ qubits in a number-conserving way.  By choosing $M_n=[Z_n]^{\tfrac{\pi}{2}}$ one can apply the decoupling sequence \eqref{dd} to pick out one particular number-conserving string  
\begin{align}
[\bar H]^\alpha = \left[\prod_{i=1}^{n/2}R_{2i-1,2i}\right]^\alpha.
\end{align}
More generally, one may desire an entangler that conserves parity, without conserving number\cite{pl}.  This can be achieved by applying local operations ($X_i$) to transform operators in the string from $G_{i,j}$ to $\sigma_i^+\sigma_j^++\sigma_i^-\sigma_j^-$.  As we detail in Appendix B, the whole sequence takes $2n-4$ $U_{i,j,k}$ gates, or equivalently $6n-10$ iSWAPs. Half as many are required if $\hat H$ is used instead. Alternatively, the many-body dynamics can be generated with the selection protocol at the cost of $n-1$ ancillas. For this, we can reuse $U_{i,j,k}=C_{i,j}X_k$ for $i,j\in q_{\text{reg}}$. This total sequence uses a total of $2n-4$ entanglers $U_{i,k,l}$ and $n+4$ Toffolis in a circuit depth of $4\log(n)+3$.



\section{Multi-control CNOT gates}
$C_{1,...,n}X_{n+1}$ gates have widespread use in quantum and reversible computation, including for circuit distillation \cite{maslov2007techniques}, unstructured search \cite{molmer2011efficient}, factorization \cite{cleve2000fast}, error-correction \cite{crow2016improved}, and linear equations system solvers \cite{aharonov2003adiabatic}.
For our constructions, let $U_{i,j,k}=[P_iX_jP_k]^{\tfrac{\pi}{2}}$  (a Toffoli gate with a relative phase \cite{maslov}, though a regular Toffoli can also be used) act on three qubits, recalling that $P_i= \ket{1}\bra{1}_i$. The chaining operation is given by $U_{i,j,k}Z_iZ_jU_{i,j,k}^\dag=-P_iZ_jZ_k+P_i^\perp Z_j$, with $P_i^\perp = \ket{0}\bra{0}_i$. Repeated application of the chaining operation on $R_{1,2}=Z_1Z_2$ following Eq.~\eqref{h} (see Appendix B) gives 
\begin{align}
\hat H_
=&(-1)^n\prod_{i=1}^{n}P_iZ_{n+1}Z_{n+2}-\sum_{j=1}^n(-1)^{j}\prod_{k=1}^{j-1}P_kP_j^\perp Z_{j+1}.\label{Htoffoli}
\end{align}
Choosing $M=[X]^{\tfrac{\pi}{2}}$, one can use the decoupling protocol \eqref{dd} to obtain a multi-qubit-controlled rotation around an arbitrary angle.
For a phaseless multi-control CNOT gate, one can compose instead the sequence 
\begin{align}%
	C_{1,...,n}Z_{n+2}=[\hat H_{n}]^{\pi/2}M_{n+1}^\dag [\hat H_{n-1}]^{-\pi/2}M_{n+1},
	\end{align}
using $4n-2$ Toffolis, or equivalently $16n-8$ CNOT gates. This cuts  in half the size and depth of the longstanding construction proposed by \cite{barenco1,maslov1,maslov}.

A more drastic reduction results from the selection protocol, where $S_i=P_i$ and thus $\text{rank(S)}=1$. Eq.~(\ref{vc}) simplifies to
\begin{align}
C_{2,...,n+1}X_{1}=C_{\text{tot}}^\dag(C_{n+1}X_{1})C_{\text{tot}},
\end{align} 
resulting in an $n$-control CNOT gate using $2(n-1)$ Toffoli gates and $2\log (n)$ depth (cf. Fig. \ref{fig:2}). This gives exponential parallelization compared to the $O(n)$ ancilla solution found in \cite{maslov}. 


\section{Unitary coupled cluster}
Another many-body operator which is frequently used (e.g. in quantum chemistry algorithms for computing energy landscapes), is an operator which transfers population between electronic orbitals (encoded in the qubits) while maintaining electron number and spin. More generally, when the operator couples arbitrary many-qubit states, it corresponds to a sparse matrix off-diagonal element \cite{aharonov2003adiabatic}. It takes the form
\begin{align}
\text{UCC}(m,n)\equiv\prod_{i=1}^m\sigma_i^+\prod_{j=m+1}^{m+n}\sigma_j^-+h.c.\label{mn}
\end{align} 
We have seen in the section on Pauli strings how to construct $R=\prod_{i=1}^{m+n}X_i$ using $2(m+n-1)$ entanglers. Since $\prod_{i=1}^{n+m}X_i$ contains all $2^{m+n}$ combinations of products of $\sigma^+$ and $\sigma^-$, we use $U=[(\prod_{i=1}^mP_i)(\prod_{j=m+1}^nP_j^\perp)X_{n+m+1}]^{\tfrac{\pi}{2}}$, which we know how to construct from the previous section on multi-control CNOTs, computing $\hat H=U^\dag RU$ to get 
\begin{align}
	\hat H=&\prod_{i=1}^{m+n}X_i-\left(\prod_{i=1}^m\sigma_i^+\prod_{j=m+1}^{m+n}\sigma_j^-+h.c.\right)\nonumber\\&+i\left(\prod_{i=1}^m\sigma_i^+\prod_{j=m+1}^{m+n}\sigma_j^--h.c.\right)X_{m+n+1}.
	\end{align}
By setting $M=[Z_{m+n+1}]^{\tfrac{\pi}{2}}$ we can apply the decoupling protocol to construct the unitary dynamics of the $\text{UCC}(m,n)$ operator in a circuit with $m+n+1$ qubits ($q_{m+n+1}$ is an ancillary qubit) using $4(m+n-1)$ iSWAPs and $4(m+n)$ (relative phase) Toffolis,
\begin{align}
	[\bar H]^{2\alpha}=[\hat H]^{\alpha}M^\dag [\hat H]^{-\alpha}M=[\text{UCC}(m,n)]^{2\alpha}.
	\end{align}
Conventional factorization of the $\text{UCC}(m,n)$ terms into Pauli strings scales exponentially as $\mathcal O(2^{m+n-1})$ in the number of two-qubit gates cost
whereas only $36(m+n) + \mathcal O(1)$ iSWAPs are required when using our decoupling protocol. Even further decrease in composition time is once again achieved if the Pauli string and multi-CNOT gates are produced using the selection protocol, down to a depth of $O(\log n)$.



\section{Architectural considerations}  
Clearly any time and space complexity advantages will be subject to limitations set by architecture.  The presence of $O(n)$ ancillas (needed for the selection protocol) is actually fairly easy to include, as most architectures have ancillary electronic, motional or photon bus degrees of freedom. Despite much worse lifetimes typically found in these states, the (linear) tradeoff in error rate is more than made up by an exponential speedup in time and justifies their use for many-body gates, in particular when memory operations are expensive.  Note previous generic $O(\log(n))$ circuit constructions require $O(n^2)$ space \cite{moore2001parallel}, which may make implementation impractical. The adjacency graph of bodies that couple to each other in the architecture will also greatly impact composition time.  For many-body operators spanning much of the graph, the spanning tree depth will determine how many steps it will take to link distant qubits in the collective many-body operator (intermediary unneeded qubits can be removed in the subsequent step). Thus, we expect the circuit depth will scale as $O(\log(n))$ when the depth of the spanning tree is $O(\log(n))$, as in \cite{brennen2003quantum,meter2006architectural, kimble2008quantum, hall2015study,van2006distributed,beigi2011graph,thaker2006quantum}, and $O(\sqrt[d]{n})$ scaling for $d$-dimensional, nearest-neighbour architectures being expected \cite{choi2011effect,choi2012theta,michael}.  




\section{Conclusions} We have developed two protocols, the decoupling and selection compositions, to generate many-body operators in $O(n)$ time for zero or constant memory overhead, and $O(\log(n))$ time for $O(n)$ ancillas, respectively.  The former enhances previous constant-overhead approaches, with improvement ranging for prominent examples  from linear (factor of 2 for multi-control CNOTs) to exponential (UCC). Our construction to bring down further the runtime to $O(\log(n))$ depth also improves quadratically on the space requirements of previous generic methods.  Our approach is generated directly from Hamiltonian dynamics, allowing straightforward incorporation of different coupling mechanisms and architectures.

\acknowledgements{ This work was supported by the European union through ScaleQIT and by US ARL-CDQI program through cooperative agreement W911NF-15-2-0061. The authors wish to thank Pierre-Luc Dallaire-Demers, Nathan Wiebe and Ryan Babbush for helpful discussions.}

