# Trading T-gates for dirty qubits in state preparation and unitary synthesis

Guang Hao Low  Quantum Architectures and Computation, Microsoft Research,
Washington, Redmond, USA  Vadym Kliuchnikov  Quantum Architectures and
Computation, Microsoft Research, Washington, Redmond, USA  Luke Schaeffer
Quantum Architectures and Computation, Microsoft Research, Washington,
Redmond, USA  Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

###### Abstract

Efficient synthesis of arbitrary quantum states and unitaries from a universal
fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum
computation. As large quantum algorithms feature many qubits that encode
coherent quantum information but remain idle for parts of the computation,
these should be used if it minimizes overall gate counts, especially that of
the expensive T-gates. We present a quantum algorithm for preparing any
dimension-$N$ pure quantum state specified by a list of $N$ classical numbers,
that realizes a trade-off between space and T-gates. Our scheme uses
$\mathcal{O}(\log{(N/\epsilon)})$ clean qubits and a tunable number of
$\sim(\lambda\log{(\frac{\log{N}}{\epsilon})})$ dirty qubits, to reduce the
T-gate cost to
$\mathcal{O}(\frac{N}{\lambda}+\lambda\log^{2}{\frac{N}{\epsilon}})$. This
trade-off is optimal up to logarithmic factors, proven through an
unconditional gate counting lower bound, and is, in the best case, a quadratic
improvement in $T$-count over prior ancillary-free approaches. We prove
similar statements for unitary synthesis by reduction to state preparation.

Introduction – Many quantum algorithms require coherent access to classical
data, that is, data that can be queried in superposition through a unitary
quantum operation. This property is crucial in obtaining quantum speedups for
applications such as machine learning Lloyd  _et al._ (2014), simulation of
physical systems Berry  _et al._ (2015); Low and Chuang (2017a) and solving
systems of linear equations Harrow  _et al._ (2009); Wossnig  _et al._
(2018a).

The nature of quantum-encoded classical data is itself varied. For example,
quantum data regression Wiebe  _et al._ (2012) queries a classical list of $N$
data-points $a_{x}$ through a unitary data-lookup oracle
$O|x\rangle|0\rangle=|x\rangle|a_{x}\rangle$ Aharonov and Ta-Shma (2003).
Other applications, particularly in quantum chemistry Babbush  _et al._ (2018)
instead access Hamiltonian coefficient data through a unitary
$A|0\rangle=|\psi\rangle$ that prepares these numbers as amplitudes in a
normalized quantum state, or as probabilities in a purified density matrix.
Even more generally, the central challenge is synthesizing some arbitrary
unitary $A\in\mathbb{C}^{N\times N}$ of which $k\leq N$ columns are either
partially or completely specified by a list of complex coefficients that is,
say, written on paper Wossnig  _et al._ (2018b).

Synthesis of these data-access unitaries is typically a dominant factor in the
overall algorithm cost. In any scalable approach to quantum computation, all
unitaries decompose into a universal fault-tolerant quantum gate set, such as
Clifford gates $\\{\textsc{H},\textsc{S},\textsc{Cnot}\\}$ and T gates Nielsen
and Chuang (2004). Solovay and Kitaev Nielsen and Chuang (2004) were the first
to recognize that any single-qubit unitary could be $\epsilon$-approximated
using $\mathcal{O}(\log^{c}{(1/\epsilon)})$ fault-tolerant gates for $c=3.97$,
which was later improved to $c=1$ Kliuchnikov  _et al._ (2013); Ross (2015).
By bootstrapping these results, it is well-known that a roughly equal number
of $\mathcal{O}(kN\log{(N/\epsilon)})$ Shende  _et al._ (2006) Clifford and
non-Clifford gates suffice for arbitrary dimensions. Notably, the total gate
count scaling is optimal in all parameters, following gate-counting arguments
Harrow  _et al._ (2002).

The possibility that T gates could be substantially fewer in number than the
Clifford gates, however, is not excluded by known lower bounds. It is believed
that fault-tolerant Clifford gates $\\{\textsc{H},\textsc{S},\textsc{Cnot}\\}$
will be cheap in most practical implementations of fault-tolerant quantum
computation. In contrast, the equivalent cost of each fault-tolerant non-
Clifford T gates, implemented at machine precision, is placed at a space-time
volume $\approx(225\;\textrm{logical qubits})\times(10\;\textrm{Clifford
depth})$ for realistic estimates Litinski (2018) based on $|\textsc{T}\rangle$
magic-state distillation at a physical error rate of $\approx 10^{-3}$.

State | Qubits |  T Depth |  T count
---|---|---|---
$|\psi\rangle$ Shende  _et al._ (2006) | $\lg{N}$ | $N\lg{\frac{N}{\epsilon}}$ | $N\lg{\frac{N}{\epsilon}}$
Here | $\lg{N}+\lambda\lg{\frac{1}{\epsilon^{\prime}}}$ | $\frac{N}{\lambda}+\lg^{2}\frac{N\lambda}{\epsilon}$ | $\frac{N}{\lambda}+\lambda\lg^{2}{\frac{N}{\epsilon}}$
$U$ Shende  _et al._ (2006) | $\lg{N}$ | $N^{2}\lg{\frac{N}{\epsilon}}$ | $N^{2}\lg{\frac{N}{\epsilon}}$
Here | $\lg{N}+\lambda\lg{\frac{K}{\epsilon^{\prime}}}$ | $\frac{KN}{\lambda}+K\lg^{2}\frac{N\lambda}{\epsilon}$ | $\frac{KN}{\lambda}+\lambda K\lg^{2}{\frac{N}{\epsilon}}$
$|\psi_{\textrm{gb}}\rangle$ Babbush  _et al._ (2018) | $\lg{\frac{N}{\epsilon}}$ | $N+\lg{\frac{1}{\epsilon}}$ | $N+\lg{\frac{N}{\epsilon}}$
Here | $\lg{N}+\lambda\lg{\frac{1}{\epsilon}}$ | $\frac{N}{\lambda}\lg{\lambda}+\lg{\frac{1}{\epsilon}}$ | $\frac{N}{\lambda}+\lambda\lg{\frac{N}{\epsilon}}$
Table 1:  Big-$\mathcal{O}(\cdot)$ cost of preparing an arbitrary quantum
state $|\psi\rangle$ Eq. 1 and $|\psi_{\textrm{gb}}\rangle$ Eq. 3 of dimension
$N$ with error $\epsilon$, as a function of a tunable parameter
$\lambda\in[1,\mathcal{O}(\sqrt{N})]$. Above,
$\epsilon^{\prime}=\Theta(\frac{\epsilon}{\lg{N}})$. Costs for synthesis of an
$N\times N$ unitary $U$ Eq. 2 is with respect to the number $K\leq N$ of fully
specified columns.

We present an approach to arbitrary quantum state preparation and unitary
synthesis that focuses on minimizing the T count. Unique to our approach is
the exploitation of a variable number $\mathcal{O}(\lambda\log{(1/\epsilon)})$
of ancillary qubits, in a manner not considered by prior gate-counting
arguments or algorithms. We find a $\mathcal{O}(\lambda)$ improvement in the T
count and circuit depth while keeping the Clifford count unchanged, excluding
logarithmic factors. Most surprisingly, its benefit far exceeds the naïve
approach of applying these ancillary qubits to producing $|\textsc{T}\rangle$
magic-states for any $\lambda=\mathcal{O}(\sqrt{N})$, as seen in Table 1. In
the best-case, the T count of $\tilde{\mathcal{O}}(\sqrt{N})$ is a square-root
factor smaller than prior art, such as for for preparing arbitrary pure states

$\displaystyle|\psi\rangle=\sum_{x=0}^{N-1}\frac{a_{x}}{\|\vec{a}\|_{2}}|x\rangle,\;\;\;\|\vec{a}\|_{q}=\Big{(}\sum_{j=0}^{N-1}|a_{x}|^{q}\Big{)}^{1/q},$
(1)

Moreover, we prove this approach realizes an optimal ancillary qubit and T
count trade-off up to log factors.

In particular, our approach is always advantageous as all but a logarithmic
number $\mathcal{O}(\log{(N/\epsilon)})$ of qubits, independent of $\lambda$,
may be dirty, meaning that they start in, and are returned to the same
undetermined initial state. At first glance, the full quadratic speedup is not
always desirable as any clean ancillary qubit, initialized in the $|0\rangle$
state, is a resource that may be better allocated magic-state distillation.
However, dirty qubits may not be used for magic-state distillation, and are a
resource typically abundant in many algorithms, such as quantum simulation by
a linear combination of unitaries Berry  _et al._ (2015). Even in the most
pessimistic scenario where no dirty qubits are available, a reduction in the
overall execution time of the algorithm, including the effective cost of
magic-state distillation, is possible.

We also consider applications of our approach. For instance, a similar speedup
to unitary synthesis

$\displaystyle U=\left(\sum^{K}_{k=0}|u_{k}\rangle\langle k|\right)+\cdots,$
(2)

where $K\leq N$ columns are specified, follows by a well-known reduction based
on Householder reflections. Improvements to state preparation with garbage

$\displaystyle|\psi_{\textrm{gb}}\rangle=\sum_{x=0}^{N-1}\sqrt{\frac{a_{x}}{\|\vec{a}\|_{1}}}|x\rangle|\mathrm{garbage}_{x}\rangle,$
(3)

relevant to the most advanced quantum simulation techniques Low and Chuang
(2016, 2017b); Babbush  _et al._ (2018) are also presented in Appendix A.

Underlying our T gate scaling results is an improved implementation of a data-
lookup oracle

$\displaystyle
O|x\rangle|0\rangle|0\rangle=|x\rangle|a_{x}\rangle|\mathrm{garbage}_{x}\rangle.$
(4)

Note the attached garbage state may always be uncomputed by applying $O$ in
reverse. We begin by describing our implementation of Eq. 4, which we call a
‘SelectSwap’ network. Subsequently, we apply this to the state preparation
problem using the fact that there exists classical data such that preparing
any $|\psi\rangle$ requires only $\mathcal{O}(\operatorname{polylog}(N))$
queries and additional primitive quantum gates Aaronson (2016). The reduction
of unitary synthesis to state preparation is then described. Finally, we prove
optimality of our approach through matching lower bounds, and discuss the
results.

Operation |  Qubits |  T Depth $\mathcal{O}(\cdot)$ |  T count $\leq\cdot+\mathcal{O}(\log\cdot)$
---|---|---|---
Select | $b+2\lceil\log_{2}{N}\rceil$ | $N$ | $4N$
Swap | $bN+\lceil\log_{2}{N}\rceil$ | $\log{N}$ | 8$bN$
SelSwap | $b\lambda+2\lceil\log_{2}{N}\rceil$ | $\frac{N}{\lambda}+\log{\lambda}$ | $4\lceil\frac{N}{\lambda}\rceil+8b\lambda$
Fig. 1d | $b(\lambda+1)+2\lceil\log_{2}{N}\rceil$ | $\frac{N}{\lambda}+\log{\lambda}$ | $8\lceil\frac{N}{\lambda}\rceil+32b\lambda$
Table 2: Upper bounds on cost of possible implementations of the data lookup
oracle $O$ of Eq. 4. Our results allow for a space-depth trade-off determined
by a choice of $\lambda\in[1,N]$, with a minimized T gate complexity of
${\mathcal{O}}(\sqrt{bN})$ by choosing $\lambda=\mathcal{O}(\sqrt{N/b})$. Note
that $b\lambda$ qubits of the Fig. 1d implementation may be dirty.

Data-lookup oracle by a SelectSwap network – The unitary data-lookup oracle of
Eq. 4 accepts an input number state $|x\rangle\in\mathbb{C}^{N}$ where
$x\in\\{0,1,\cdots,N-1\\}\equiv[N]$, and returns an arbitrary $b$-bit number
$a_{x}\in\\{0,1\\}^{b}$. Our approach combines a multiplexer implementation of
$O$ Childs  _et al._ (2018), called Select and a unitary swap network Swap,
with costs summarized in Table 2.

The Select operator applies some arbitrary unitary $U_{x}$ controlled by the
index state $|x\rangle$, that is

$\displaystyle\textsc{Select}=\sum_{x=0}^{N-1}|x\rangle\langle x|\otimes
U_{x}.$ (5)

Thus $O$ is realized by choosing
$U_{x}=X^{a_{x}}\equiv\otimes^{b-1}_{j=0}X^{a_{x,j}}$ Babbush  _et al._ (2018)
to either be identity or the Pauli-$X$ gate depending on the bit string
$a_{x}$. As described in Fig. 1a, the costs, excluding $\\{U_{x}\\}$, is
$\mathcal{O}(N)$ Clifford+T gates. As controlled-$X$ is Clifford too, an
additional $\mathcal{O}(bN)$ Clifford gates are applied. These
$\textsc{Cnot}s$ may be applied in logarithmic depth using an ancillary qubit
free quantum fanout discussed in Section B.1.

The unitary Swap network moves a $b$-qubit quantum register indexed by $x$ to
the $x=0$ register, controlled by the state $|x\rangle$. For any quantum
states $\bigotimes_{x=0}^{N-1}|\phi_{x}\rangle_{x}$,

$\displaystyle\textsc{Swap}\left[|x\rangle\bigotimes_{x=0}^{N-1}|\phi_{x}\rangle_{x}\right]=|x\rangle|\phi_{x}\rangle_{0}\otimes\cdots,$
(6)

where the remaining quantum states $(\cdots)$ in registers $x>0$ are
unimportant.

As illustrated in Fig. 1b, this decomposes into a network of controlled-swap
operators. As each controlled-swap operator decomposes into two Cnots and one
Toffoli, this network uses $\mathcal{O}(bN)$ Clifford+T gates. An ancillary
qubit free logarithmic-depth version of Swap is discussed in Section B.2

Our SelectSwap network illustrated in Fig. 1c is a simple hybrid of the above
two schemes. Similar to the Swap approach, we duplicate the $b$-bit register
$\lambda$ times, where $\lambda\in\\{1,\cdots,N\\}$ is an integer. For
$\lambda$ that is not a power of $2$, we compute
$|x\rangle\rightarrow|q\rangle|r\rangle$, which is the quotient
$q=x/\lfloor\lambda\rfloor$ and remainder $r=x\mod{\lambda}$. This contributes
an additive cost of $\mathcal{O}(\log{N}\log{\lambda})$ gates. Select is
controlled by $|q\rangle$ to write multiple values of $a_{x}$ simultaneously
into these duplicated registers by choosing
$U_{x}=\bigotimes^{\lambda-1}_{j=0}X^{a_{xN/\lambda+j}}$, where $x\in[\lfloor
N/\lambda\rfloor]$. Swap is then controlled $|r\rangle$ to move the desired
data entry $|a_{x}\rangle$ to the output register. As the T gate complexity of
$\mathcal{O}(\lambda b+\frac{N}{\lambda})$ is determined only by the dimension
of the Select and Swap control registers, this is minimized with value
$\mathcal{O}(\sqrt{Nb})$ at $\lambda=\mathcal{O}(\sqrt{N/b})$.

| a) |
---|---
c) |
| b) |
---|---
d) |
Figure 1: (a) Example Select operator $\sum_{x=0}^{N-1}|x\rangle\langle
x|\otimes X^{a_{x}}$ with $N=4$. The symbol $\oslash$ indicates control by a
number state. A naive decomposition of all multiply-controlled-Nots requires
$\mathcal{O}(N\log{N})$ Clifford+T gates and only one dirty qubit Barenco  _et
al._ (1995). Cancellation of adjacent gates can reduce this to only
$\mathcal{O}(N)$ Childs  _et al._ (2018); Babbush  _et al._ (2018), but by
using additional $\lceil\log_{2}N\rceil$ clean qubits. (b) Example Swap
network with $N=4$ using $\mathcal{O}(bN)$ Clifford+T. Any arbitrary state
$|\phi_{x}\rangle_{x}$ in register index $x$ is swapped to the $x=0$ position.
(c) The SelectSwap network with $N=16,\lambda=4$ that combines the above two
approaches. (d) Modification of SelectSwap network that uses
$2\lceil\log_{2}N\rceil+b$ clean qubits and $b\lambda$ dirty qubits to
implement the data-lookup oracle of Eq. 4 without garbage. We omit the Select
ancillary qubits for clarity.

Importantly, all but $b+\lceil\log_{2}N\rceil$ of the qubits may be made dirty
using a simple modification shown in Fig. 1d. Then for any computational basis
state $|\phi\rangle=\otimes_{x=0}^{\lambda-1}|\phi_{x}\rangle_{x}$, and any
input state $|x\rangle=|q\rangle|r\rangle$, let us evaluate
$|0\rangle|\phi\rangle$ at each dotted line:

$\displaystyle|0\rangle|\phi\rangle$
$\displaystyle\rightarrow|0\rangle|\phi_{x}\oplus
a_{x}\rangle_{0}\cdots\rightarrow|\phi_{x}\oplus a_{x}\rangle|\phi_{x}\oplus
a_{x}\rangle_{0}\cdots$ $\displaystyle\rightarrow|\phi_{x}\oplus
a_{x}\rangle|\phi\rangle\rightarrow|\phi_{x}\oplus
a_{x}\rangle|\phi_{x}\rangle_{0}\cdots$
$\displaystyle\rightarrow|a_{x}\rangle|\phi_{x}\rangle_{0}\cdots\rightarrow|a_{x}\rangle|\phi\rangle$
(7)

By linearity, this is true for all quantum states $|\phi\rangle$.

As the T gate complexity begins to increase with sufficiently large $\lambda$,
one may simply elect to not use excess available dirty qubits. However,
continued reduction of the T depth down to $\mathcal{O}(\log{N})$ might be a
useful property. In Appendix C we discuss an alternate construction that
achieves logarithmic T depth and preserves the quadratic T count improvement
for larger $\lambda=\Omega(\sqrt{N})$.

Arbitrary quantum state preparation – Preparation of an arbitrary dimension
$N=2^{n}$ quantum state
$|\psi\rangle=\frac{1}{\|\vec{a}\|_{2}}\sum_{x\in\\{0,1\\}^{n}}a_{x}|x\rangle$
using the data-lookup oracle $O$ of Eq. 4 is well-known in prior art. The
basic idea was introduced by Grover and Rudolph (2002), and an ancillary-free
implementation was presented in Shende  _et al._ (2006). We outline the
inductive argument of Aaronson (2016), and evaluate its cost using our
SelectSwap implementation of $O$.

For any bit-string $y\in\\{0,1\\}^{w}$ of length $w\leq n$, let the
probability that the first $w$ qubits of $|\psi\rangle$ are in state
$|y\rangle$ be
$p_{y}=\frac{1}{\|\vec{a}\|^{2}_{2}}\sum_{\mathrm{prefix}_{w}(x)=y}|a_{x}|^{2}$.
Thus a single-qubit rotation $e^{-iY\theta}|0\rangle$ by angle
$\theta=\cos^{-1}\sqrt{p_{0}}$ prepares the state
$|\psi_{1}\rangle=\sqrt{p_{0}}|0\rangle+\sqrt{p_{1}}|1\rangle$, where $p_{0}$
is the probability that the first qubit of $|\psi\rangle$ is in state
$|0\rangle$. We then recursively apply single-qubit rotations on the
$(w+1)^{\mathrm{th}}$ qubit conditioned on the first $w$ qubits being in state
$|y\rangle$. The rotation angles $\theta_{y}=\cos^{-1}{\sqrt{p_{y0}/p_{y}}}$
are chosen so that the state produced $|\psi_{w+1}\rangle$ reproduces the
correct probabilities on the first $w+1$ qubits.

These conditional rotations are implemented using a sequence of data-lookup
oracles $O_{1},\cdots,O_{n-1}$, where $O_{w}$ stores a $b$-bit approximation
of all $\theta_{y}$ where $y\in\\{0,1\\}^{w}$. At the $w^{\mathrm{th}}$
iteration,

$\displaystyle|\psi_{w}\rangle$
$\displaystyle=\sum_{y\in\\{0,1\\}^{w}}\sqrt{p_{y}}|y\rangle\underset{O_{w}}{\mapsto}\sum_{y\in\\{0,1\\}^{w}}\sqrt{p_{y}}|y\rangle|\theta_{y}\rangle$
(8)
$\displaystyle\mapsto\sum_{y\in\\{0,1\\}^{w}}\sqrt{p_{y}}|y\rangle\left(\sqrt{\frac{p_{y0}}{p_{y}}}|0\rangle+\sqrt{\frac{p_{y1}}{p_{y}}}|1\rangle\right)|\theta_{y}\rangle$
$\displaystyle\underset{O^{\dagger}_{w}}{\mapsto}\sum_{y\in\\{0,1\\}^{w+1}}\sqrt{p_{y}}|y\rangle=|\psi_{w+1}\rangle.$

Note that we omit any garbage registers as they are always uncomputed. Also,
the second line is implemented using $b$ single-qubit rotations each
controlled by a bit of $\theta_{y}$. The complex phases of the target state
$|\psi\rangle$ are applied to $|\psi_{n}\rangle$ by a final step with a data-
lookup oracle storing $\phi_{x}=\operatorname{arg}{[a_{x}/\sqrt{p_{x}}]}$.
Thus $\mathcal{O}(b\log{N})$ single-qubit rotations are applied in total.

We implement these oracles with the SelectSwap network of Fig. 1, using a
fixed value of $\lambda$ for all $O_{k}$. A straightforward sum over the T
count of Fig. 1 is $\mathcal{O}(b\lambda\log{(N)}+\frac{N}{\lambda})$, which
is then added to the total T count of $\mathcal{O}(b\log{(\frac{N}{\delta})})$
for synthesizing all single-qubit rotations each to error $\delta$ using the
phase gradient technique Gidney (2018), outlined in Appendix D. The error of
the resulting state $|\psi^{\prime}\rangle$ produced is determined by the
number of bits $b$ used to represent the rotation angles, in addition to
rotation synthesis errors $\delta$. Adding these errors leads to

$\displaystyle\||\psi^{\prime}\rangle-|\psi\rangle\|=\underbrace{\mathcal{O}(\delta)}_{\text{rotation
synthesis}}+\underbrace{\mathcal{O}(2^{-b}\log{N})}_{\text{bits of
precision}}\leq\epsilon,$

which is bounded by $\epsilon$ with the choice
$b=\Theta(\log{(\frac{\log{N}}{\epsilon})})$ and $\delta=\Theta(\epsilon)$. As
a function of $\epsilon$, the total T gate complexity is then
$\mathcal{O}(\frac{N}{\lambda}+b(\lambda
n+b))=\mathcal{O}(\frac{N}{\lambda}+\lambda\log^{2}{(\frac{N}{\epsilon})}),$
and is plotted in Fig. 2.

Figure 2: T gate count dependence on number of dirty qubits exploited for
approximating an arbitrary quantum state of dimension $N=10^{\\{2,4,6,8\\}}$
to error $10^{-3}$ using our algorithm (dots) in comparison with the standard
ancillary-free approach (dashed) Shende  _et al._ (2006). Note that at this
error, $b\geq 17$ qubits are required to represent each coefficient in binary.
Moreover, one may always use fewer than the maximum number of available dirty
qubits.

Unitary synthesis by state preparation – The ability to prepare arbitrary
quantum states enables synthesis of arbitrary unitaries
$U\in\mathbb{C}^{N\times N}$. Given the matrix elements
$\\{|u_{k}\rangle\;|\;k\in[K]\\}$ for the first $K$ columns of $U$, the
isometry synthesis problem is to find a quantum circuit that implements a
unitary $V$ that approximates $U$ in the first $K$ columns to error
$\|U-V\|_{2,K}=\max_{x<K}\left\|(U-V)|x\rangle\right\|\leq\epsilon$.

We use the Householder reflections decomposition Householder (1958) to find a
$V$ that is a product of $K$ reflections $\mathbb{I}-2|v_{k}\rangle\\!\langle
v_{k}|$ and a diagonal gate
$\mathrm{diag}(e^{i\phi^{\prime}_{1}},\ldots,e^{i\phi^{\prime}_{K}},1,\ldots,1)$,
for some set of quantum states $|v_{k}\rangle$. Note that this representation
is not unique. The diagonal gate can be eliminated by using one ancillary
qubit as discussed in Kliuchnikov (2013). There, it suffices to implement the
unitary $W=|0\rangle\\!\langle 1|\otimes U+|1\rangle\\!\langle 0|\otimes
U^{\dagger}$, which is equal to the product of reflections
$\mathbb{I}-2|w_{k}\rangle\\!\langle w_{k}|$ where
$|w_{k}\rangle=(|1\rangle\otimes|k\rangle-|0\rangle\otimes|u_{k}\rangle)/\sqrt{2}$
for $k\in[K]$.

Given a state preparation unitary $A_{k}|0\rangle=|u_{k}\rangle$, one can
prepare state $|w_{k}\rangle$ starting from $|0\rangle\otimes|e_{1}\rangle$.
Apply Hadamard to the first qubit, then a sequence of CNOT gates to prepare
$|1\rangle\otimes|k\rangle+|0\rangle\otimes|0\rangle$, and finally apply
controlled-$A_{k}$ negatively controlled on the first qubit. Note that when
this method is applied to the synthesis of sparse isometries, the states being
synthesized are again sparse. Moreover, the cost of converting a state into a
reflection doubles the number of non-Clifford gates. Thus the number of T
gates used to synthesize an isometry is twice that for all the
Controlled-$A_{k}$ operations, and scales like
$\mathcal{O}\left(K\left(\frac{N}{\lambda}+\lambda\log^{2}{(\frac{N}{\epsilon})}\right)\right)$.

Lower bound – We prove the optimality of our construction through a circuit
counting argument. The most general circuit on $q$ qubits that uses $\Gamma$
T-gates has the canonical form Gosset  _et al._ (2014)
$C\cdot\prod^{\Gamma}_{j=1}e^{-i\pi P_{j}/8},$where each $P_{j}$ is one of
$4^{q}$ possible Pauli operators, and $C$ is one of $2^{\mathcal{O}(q^{2})}$
possible Clifford operators. Thus the number of unique quantum circuits is at
most

$\displaystyle\text{Unique quantum
circuits}=\mathcal{O}(4^{q\Gamma+\mathcal{O}(q^{2})}).$ (9)

A lower bound on the qubit and T-gate complexity of the data-lookup oracle of
Eq. 4 is obtained by counting the number of unique Boolean functions
$f:[N]\rightarrow\\{0,1\\}^{b}$. As there $2^{bN}$ such functions, we compare
with Eq. 9. This leads to a lower bound on the space-T-gate product

$\displaystyle q\Gamma=\Omega(bN-q^{2}).$ (10)

As the SelectSwap complexity in Fig. 1 is
$q\Gamma=\mathcal{O}(\lambda^{2}b^{2}+bN+\log{(N)}(1/\lambda+\lambda b))$,
this is optimal up to logarithmic factors so long as the number of T-gates
dominates the qubit count like $\lambda=o(\sqrt{N/b})$, which is the case in
most quantum circuits of interest.

A similar lower bound on state preparation is obtained by counting the number
of dimension-$N$ quantum states that a distinguishable with error $\epsilon$.
Without loss of generality, we only count quantum states
$|\psi\rangle\in\mathbb{R}^{N}$ with real coefficients. These states live on
the surface a unit-ball $\mathbb{B}_{N}$ of dimension $N$, with area
$\operatorname{Area}[\mathbb{B}_{N}]=\frac{2\pi^{N/2}}{(N/2-1)!}$. Let us now
fix a state $|\psi\rangle$. Then the states $|\chi\rangle$ that satisfy
$\||\psi\rangle-|\chi\rangle\|\leq\epsilon$ live inside a $\epsilon$-ball
$\mathbb{B}_{N-1}$ with volume
$\mathcal{O}(\operatorname{Vol}[\mathbb{B}_{N-1}]\epsilon^{N-1})=\mathcal{O}(\frac{\pi^{N/2}}{(N/2)!}\epsilon^{N-1})$
Mora and Briegel (2005). Thus there are at least
$\Omega(\frac{\operatorname{Area}[\mathbb{B}_{N}]}{\operatorname{Vol}[\mathbb{B}_{N-1}]\epsilon^{N-1}})=\Omega(\sqrt{N}\epsilon^{-N+1})$
quantum states. Once again by comparing with Eq. 9, we obtain a $T$-gate lower
bound of

$\displaystyle q\Gamma=\Omega(N\log{(1/\epsilon)}-q^{2}).$ (11)

This also matches the cost of our approach in Eq. 9 up to logarithmic factors,
so long as $\lambda=o(\sqrt{N/\log{(1/\epsilon)}})$. The total number of
isometries within at least distance $\epsilon$ from each other can also be
estimated using Lemma 4.3 on Page 14 in Knill (1995), and is roughly
$\Omega((1/\epsilon)^{KN})$. An analogous argument can be made for state
preparation with garbage by considering by considering the unit simplex
instead of the unit ball.

Let us now establish a lower bound on state preparation that holds when
measurements and arbitrary number of ancillae are used. For the purpose of the
lower bound we also allow the use of post-selected measurements of multiple-
qubit Pauli observables. Every preparation of an $n$-qubit state by Clifford+T
circuit with ancillae and post-selected Pauli measurements can be rewritten
Beverland  _et al._ (2018) as the following sequence of operations: 1)
initialization of $\Gamma$ qubits into T state
$|0\rangle+e^{i\pi/4}|1\rangle$; 2) post-selected measurement of $\Gamma-n$
commuting Pauli observables; 3) application of a Clifford unitary on $\Gamma$
qubits. After the three steps first $\Gamma-n$ qubits are in a zero state and
last $n$ qubits are in the state being prepared. Let us count the number of
distinct states that can be prepared by the steps described above. For the
step two, there are at most $2\cdot 4^{\Gamma}$ ways of choosing first Pauli
observable and at most $4^{\Gamma}$ ways of choosing each of the remaining
$\Gamma-n-1$ observables because each of them needs to commute with the first
observable. Therefore, on step two we have at most $2\cdot
4^{\Gamma(\Gamma-n)}$ choices of Pauli observables. For the step three, two
distinct Clifford unitaries can lead to preparing the same state and counting
total number of Clifford unitaries on $\Gamma$ qubits leads to an
overestimate. The prepared $|\psi\rangle$ state is completely described by
$4^{n}$ numbers $\alpha_{P}=\operatorname{Tr}(P|\psi\rangle\langle\psi|)$
where $P$ goes over all $n$-qubit Pauli matrices $\\{I,X,Y,Z\\}^{\otimes n}$.
Let us count how many distinct $4^{n}$ dimensional vectors of $\alpha_{P}$ we
can get on the step three by applying different Clifford unitaries $C$. Let
$\rho^{\prime}$ be a density matrix describing a state of all qubits after
step two, then
$\alpha_{P}=\operatorname{Tr}(C\rho^{\prime}C^{\dagger}(I_{\Gamma-n}\otimes
P))$ which is equal to
$\operatorname{Tr}(\rho^{\prime}C^{\dagger}(I_{\Gamma-n}\otimes P)C)$. We see
that the vector of $\alpha_{P}$ is uniquely defined by action of $C$ on $2n$
Pauli operators $Z_{\Gamma-n+k}$, $X_{\Gamma-n+k}$ for $k$ from $1$ to $n$.
There are at most $2\cdot 4^{2\Gamma n}$ ways of choosing the action of $C$ on
the listed Pauli operators. Therefore we can prepare at most $4\cdot
4^{\Gamma(\Gamma+n)}$ distinct states. This leads to the lower bound on the
number of required T gates $\Omega\left(\sqrt{N\log
N\log(1/\epsilon)}\right)$.

Conclusion – We have shown that arbitrary quantum states with $N$
coefficients, or unitaries with $KN$ values specified by classical data may be
synthesized with a T gate complexity that is an optimal
$\tilde{\mathcal{O}}(\sqrt{N})$ reduction over prior art. As these subroutines
are ubiquitous in many quantum algorithms we this result to be of widely
applicable. Moreover, we expect our approach to be practical due to its almost
exclusive usage of dirty qubits, which are typically abundant in larger
quantum algorithms. Though our results are asymptotically optimal, constant
factor and logarithmic improvements in costs could still be possible. For
instance, our approach can be modified to use only $\mathcal{O}(1)$ additional
clean qubits, but this increases the T count by a logarithmic factor. As more
limited trade-offs between T gates and ancillary qubits are observed in other
quantum circuits, such as for addition Gidney (2018) or And, a major open
question highly relevant to implementation in nearer-term quantum computers,
is whether such a property could be generic for many other quantum circuits
and algorithms.

Acknowledgements – We thank Nicolas Delfosse, Jeongwan Haah, Robin Kothari,
Jessica Lemieux, Martin Roetteler, and Matthias Troyer for insightful
discussions.

## References

  * Lloyd  _et al._ (2014) S. Lloyd, M. Mohseni, and P. Rebentrost, Nat Phys 10, 631 (2014).
  * Berry  _et al._ (2015) D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Phys. Rev. Lett. 114, 090502 (2015).
  * Low and Chuang (2017a) G. H. Low and I. L. Chuang, Phys. Rev. Lett. 118, 010501 (2017a).
  * Harrow  _et al._ (2009) A. W. Harrow, A. Hassidim, and S. Lloyd, Phys. Rev. Lett. 103, 150502 (2009).
  * Wossnig  _et al._ (2018a) L. Wossnig, Z. Zhao, and A. Prakash, Phys. Rev. Lett. 120, 050502 (2018a).
  * Wiebe  _et al._ (2012) N. Wiebe, D. Braun, and S. Lloyd, Phys. Rev. Lett. 109, 050505 (2012).
  * Aharonov and Ta-Shma (2003) D. Aharonov and A. Ta-Shma, in  _Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing_, STOC ’03 (ACM, New York, NY, USA, 2003) pp. 20–29.
  * Babbush  _et al._ (2018) R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Phys. Rev. X 8, 041015 (2018).
  * Wossnig  _et al._ (2018b) L. Wossnig, Z. Zhao, and A. Prakash, Phys. Rev. Lett. 120, 050502 (2018b).
  * Nielsen and Chuang (2004) M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ , 1st ed. (Cambridge University Press, 2004).
  * Kliuchnikov  _et al._ (2013) V. Kliuchnikov, D. Maslov, and M. Mosca, Phys. Rev. Lett. 110, 190502 (2013).
  * Ross (2015) N. J. Ross, Quantum Info. Comput. 15, 932 (2015).
  * Shende  _et al._ (2006) V. V. Shende, S. S. Bullock, and I. L. Markov, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst 25, 1000 (2006).
  * Harrow  _et al._ (2002) A. W. Harrow, B. Recht, and I. L. Chuang, J. Math. Phys. 43, 4445 (2002).
  * Litinski (2018) D. Litinski, arXiv preprint arXiv:1808.02892 (2018).
  * Low and Chuang (2016) G. H. Low and I. L. Chuang, arXiv preprint arXiv:1610.06546 (2016).
  * Low and Chuang (2017b) G. H. Low and I. L. Chuang, arXiv preprint arXiv:1707.05391 (2017b).
  * Aaronson (2016) S. Aaronson, in  _Lecture Notes for the 28th McGill Invitational Workshop on Computational Complexity, Holetown, Barbados. With guest lectures by A. Bouland and L. Schaeffer._ (2016).
  * Childs  _et al._ (2018) A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, Proc. Natl. Acad. Sci. U.S.A 115, 9456 (2018).
  * Barenco  _et al._ (1995) A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Phys. Rev. A 52, 3457 (1995).
  * Grover and Rudolph (2002) L. Grover and T. Rudolph, arXiv preprint quant-ph/0208112 (2002).
  * Gidney (2018) C. Gidney, Quantum 2, 74 (2018).
  * Householder (1958) A. S. Householder, J. ACM 5, 339 (1958).
  * Kliuchnikov (2013) V. Kliuchnikov, arXiv preprint arXiv:1306.3200 (2013).
  * Gosset  _et al._ (2014) D. Gosset, V. Kliuchnikov, M. Mosca, and V. Russo, Quantum Info. Comput. 14, 1261 (2014).
  * Mora and Briegel (2005) C. E. Mora and H. J. Briegel, Phys. Rev. Lett. 95, 200503 (2005).
  * Knill (1995) E. Knill, arXiv preprint quant-ph/9508006 (1995).
  * Beverland  _et al._ (2018) M. E. Beverland, E. T. Campbell, M. Howard, and V. Kliuchnikov, (In preparation) (2018).
  * Cuccaro  _et al._ (2004) S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, arXiv preprint quant-ph/0410184 (2004).
  * Häner  _et al._ (2017) T. Häner, M. Roetteler, and K. M. Svore, Quantum Info. Comput. 17 (2017).

##  Appendix A Purified density matrix preparation

In some applications, particular in quantum simulation based on a linear
combination of unitaries or qubitization Berry  _et al._ (2015); Low and
Chuang (2016), it suffices to prepare the density matrix
$\rho=\sum_{x=0}^{N-1}\frac{|a_{x}|}{\|\vec{a}\|_{1}}|x\rangle\langle x|$
through a quantum state
$|\psi\rangle=\sum_{x=0}^{N-1}\sqrt{\frac{a_{x}}{\|\vec{a}\|_{1}}}|x\rangle|\mathrm{garbage}_{x}\rangle$
of Eq. 3 where the number state $|x\rangle$ is entangled with some garbage
that depends only on $x$. By allowing garbage, it was shown by Babbush  _et
al._ (2018) that strictly linear T gate complexity in $N$ is achievable, using
a Select data-lookup oracle corresponding to the $\lambda=1$ case of Table 2.
We outline the original idea, then generalize the procedure using the
SelectSwap network, which enables sublinear T gate complexity and better error
scaling than the garbage-free approach. As density matrices have positive
diagonals, we only consider the case of positive $a_{x}\geq 0$.

The original approach is based on a simple observation. By comparing a $b$-bit
number state $|a\rangle$ together with a uniform superposition state
$|u_{2^{b}}\rangle=\frac{1}{\sqrt{2^{b}}}\sum_{j=0}^{2^{b}-1}|j\rangle$ over
$2^{b}$ elements, $|a\rangle$ may be mapped to

$\displaystyle|a\rangle\mapsto|a\rangle\Big{(}\sqrt{\frac{a}{2^{b}}}|0\rangle|u_{a}\rangle+\sqrt{\frac{2^{b}-a}{2^{b}}}|1\rangle|u_{\geq
a}\rangle\Big{)},$ (12)

where we denote a uniform superposition after the first $a$ elements by
$|u_{\geq a}\rangle=\sum_{j=a}^{2^{b}-1}\frac{|j\rangle}{\sqrt{2^{b}-a}}$.
This may be implemented using quantum addition Cuccaro  _et al._ (2004), which
costs $\mathcal{O}(b)$ Clifford+T gates with depth $\mathcal{O}(b)$.

This observation is converted to state-preparation in four steps. First, the
normalized coefficients $a_{x}\frac{N2^{b}}{\|a\|_{1}}\approx a_{x}^{\prime}$
are rounded to nearest integer values such that
$\|\vec{a}^{\prime}\|_{1}=N2^{b}$. Second, the data-lookup oracle that writes
two numbers $a_{x}^{\prime\prime}\in[2^{b}]$ and $f(x)\in[N]$ such that
$a^{\prime}_{x}=a^{\prime\prime}_{x}+\sum_{\mathrm{y}\in\\{f^{-1}(x)\\}}(2^{b}-a^{\prime\prime}_{y})$.
Thus

$\displaystyle
O|x\rangle|0\rangle|0\rangle=|x\rangle|a^{\prime\prime}_{x}\rangle|f(x)\rangle,$
(13)

where we have omitted the irrelevant garbage state. Third, the oracle $O$ is
applied to a uniform superposition over $|x\rangle$, and the comparator trick
of Eq. 12 is applied. This produces the state

$\displaystyle\sum_{x=0}^{N-1}\frac{|x\rangle}{\sqrt{N}}|a^{\prime\prime}_{x}\rangle|f(x)\rangle\left(\sqrt{\frac{a^{\prime\prime}_{x}}{2^{b}}}|0\rangle|u_{a^{\prime\prime}_{x}}\rangle+\cdots|1\rangle|u_{\geq{a^{\prime\prime}_{x}}}\rangle\right).$

Finally, $|f(x)\rangle$ is swapped with $|x\rangle$, controlled on the
$|1\rangle$ state. This leads to a state
$|\psi\rangle=\sum_{x=0}^{N-1}\sqrt{\frac{a^{\prime}_{x}}{\|\vec{a}^{\prime}\|_{1}}}|x\rangle|\mathrm{garbage}_{x}\rangle$.
After tracing out the garbage register, the resulting density matrix
$\rho^{\prime}$ approximates the desired state $\rho$ with trace distance

$\displaystyle\|\rho^{\prime}-\rho\|_{1}=\mathcal{O}(2^{-b})\leq\epsilon.$
(14)

The T gate complexity is then the cost of the data-lookup oracle of Eq. 13
plus $\mathcal{O}(b)$ for the comparator of Eq. 12, plus
$\mathcal{O}(\log{N})$ for the controlled swap with $|f(x)\rangle$. By
implementing this data-lookup oracle with the SelectSwap network, one
immediately obtains the stated T gate complexity of
$\mathcal{O}(\lambda(b+\log{N})+\frac{N}{\lambda})=\mathcal{O}(\lambda\log{(N/\epsilon)}+\frac{N}{\lambda})$,
where we choose $b=\mathcal{O}(\log{(1/\epsilon)})$.

##  Appendix B Data-lookup oracle implementation details

In this section, we present additional details on the implementation of the
data-lookup oracle. In particular, we discuss a multi-target Cnot
implementation in logarithmic depth without ancillary qubits in Section B.1,
and a swap network Swap with similar properties in Section B.2. Also evaluated
is the T count and Clifford depth of these implementations up to constant
factors. We define the Clifford depth, to be the number of layers of two-qubit
Clifford gates that cannot be executed in parallel, assuming all-to-all qubit
connectivity. We also assume that each T magic-state injection circuit has a
Clifford depth of $1$.

###  B.1 Quantum fanout in logarithmic depth without ancillary qubits

In this section, we construct a controlled-NOT gate that targets $n$ qubits,
that is,

$\displaystyle\textsc{Cnot}_{n}=|0\rangle\langle
0|\otimes\mathbb{I}+|1\rangle\langle 1|\otimes X^{\otimes n}.$ (15)

The most straightforward approach applies $n$ NOT gates in sequence, each
controlled by the same qubit. A slight modification results in logarithmic
depth as shown in Table 3.

Given any number of $n$ qubits in states $|x_{j}\rangle$ for
$j=0,1,\cdots,n-1$, one may use a ladder of $n-1$ controlled-NOT gates to
realize the transformation

$\displaystyle|x_{0}\rangle|x_{1}\rangle|x_{2}\rangle\cdots|x_{n-1}\rangle$
(16) $\displaystyle\rightarrow$ $\displaystyle|x_{0}\rangle|x_{0}\oplus
x_{1}\rangle|x_{2}\rangle\cdots|x_{n-1}\rangle$ $\displaystyle\rightarrow$
$\displaystyle|x_{0}\rangle|x_{0}\oplus x_{1}\rangle|x_{0}\oplus x_{1}\oplus
x_{2}\rangle\cdots|x_{n-1}\rangle$ $\displaystyle\rightarrow$
$\displaystyle|x_{0}\rangle|x_{0}\oplus x_{1}\rangle|x_{0}\oplus x_{1}\oplus
x_{2}\rangle\cdots|\oplus_{j=0}^{{n-1}}x_{j}\rangle.$

Let us call this unitary operation $\textsc{Ladder}_{n}$.

We now introduce a control qubit $|z\rangle$. One implementation of
$\textsc{Cnot}_{n}$ is then obtained by applying
$\textsc{Ladder}^{\dagger}_{n}$, followed by a NOT on $|x_{0}\rangle$
controlled by $|z\rangle$, and finally followed by $\textsc{Ladder}_{n}$. This
has a Clifford depth of $2n-1$ as depicted below for the example $n=4$.

By distributing the controls and targets above in a tree-structure as depicted
below for the example $n=4$, the Clifford depth of $\textsc{Cnot}_{n}$ may be
reduced to $2\lceil\log_{2}{(n)}\rceil+1$.

As the control qubit $|z\rangle$ is only used once in the above circuit, a
further reduction in depth is possible by repeatedly using it to apply
additional multi-target Cnot gates in each time-slice. Let us denote by
$g(d)=2^{(d-1)/2}$ the maximum number of qubits targeted by the above circuit
in a depth of $d$. Then the total number of qubits $n(d)$ targeted with this
additional reduction satisfies the recurrence

$\displaystyle n(1)$ $\displaystyle=g(1),\quad n(2)=n(1)+g(1),\quad$ (17)
$\displaystyle\vdots$ $\displaystyle n(d)$ $\displaystyle=n(d-1)+g(2\lceil
d/2\rceil-1)$ $\displaystyle=\begin{cases}(3\cdot
2^{(d-1)/2}-2),&d\;\text{odd},\\\ 2(2^{d/2}-1),&d\;\text{even}.\end{cases}$
$\displaystyle\geq 2(2^{d/2}-1)$

Let us denote by $\text{D}[\textsc{Cnot}_{n}]$ the depth of this
implementation of $\textsc{Cnot}_{n}$, which satisfies

$\displaystyle\text{D}(\textsc{Cnot}_{n})\leq\left\lceil
2\log_{2}\left(\frac{n+2}{2}\right)\right\rceil.$ (18)

Approach | Clifford Depth $(d)$ | Clifford Count |  Volume $=(n+1)d$
---|---|---|---
Linear | $n$ | $n$ | $(n+1)d$
Logarithmic | $2\lceil\log_{2}{(n)}\rceil+1$ | $2n-1$ | $(n+1)d$
Eq. 17 | $\leq 2\lceil\log_{2}{(n/2+1)}\rceil$ | $\leq 2n-1$ | $(n+1)d$
Table 3: Different implementations of a controlled-NOT gate Eq. 15 that
targets $n$ qubits.

###  B.2 Implementations of a Swap network

In this section, we detail various implementations of the unitary swap network
Swap that moves an $b$-qubit quantum register indexed by
$x\in\\{0,\cdots,N-1\\}$ to the position of the $x=0$ register, controlled by
an index state $|x\rangle$. More precisely, for any set of quantum states
$\bigotimes_{x=0}^{N-1}|\phi_{x}\rangle_{x}$ in the $b$-qubit register indexed
by $x$,

$\displaystyle\textsc{Swap}\left[|x\rangle\bigotimes_{x=0}^{N-1}|\phi_{x}\rangle_{x}\right]=|x\rangle|\phi_{x}\rangle_{0}\cdots,$
(19)

where the final quantum states in registers indexed by $x>0$ are unimportant.
Let us express the index ${x}\equiv x_{0}x_{1}\cdots$ in binary, where $x_{0}$
is the smallest bit. Then it suffices to perform swaps between all pairs of
registers indexed by $\\{(i,i+2^{j})\;|\;i\in 2^{j+1}\mathbb{N}_{0}\\}$,
controlled by the $j^{\textrm{th}}$ qubit $|x_{j}\rangle$ of the index state
$|x\rangle$, in the order of $j=0,1,\cdots,\lceil\log_{2}{N}\rceil$.

Each controlled pair-wise swap may be understood as a circuit
$\textsc{Swap}_{n}$ that swaps two $n$-qubit quantum registers in any state
$|\psi\rangle,|\phi\rangle\in\mathbb{C}^{2^{n}}$, controlled by a single qubit
$|z\rangle\in\mathbb{C}^{2}$. That is,

$\displaystyle\textsc{Swap}_{n}|z\rangle|\psi\rangle|\phi\rangle=\begin{cases}|z\rangle|\psi\rangle|\phi\rangle,&z=0,\\\
|z\rangle|\phi\rangle|\psi\rangle,&z=1.\end{cases}$ (20)

The overall cost of Swap is then the sum of costs of $\textsc{Swap}_{n}$ for
$n=\lfloor\frac{N-1}{2^{j+1}}+\frac{1}{2}\rfloor$.

We now consider different implementations considered realize trade-offs
between Toffoli-gate count, circuit depth, and ancillary qubit usage, as
summarized in Table 4.

Approach | Clifford Depth $(d_{c})$ | T count | T depth $(d_{t})$ | Volume $=(2n+1)(d_{c}+d_{t})$
---|---|---|---|---
Linear | $4n+4$ | $7n$ | $4$ | $8n^{2}+\mathcal{O}(n)$
Logarithmic | $4\text{D}[\textsc{Cnot}_{\lceil n/2\rceil}]+2$ | $14n$ | $8$ | $\leq 8n(\left\lceil 2\log_{2}\left(\frac{n+2}{2}\right)\right\rceil+2.5)+\mathcal{O}(\log{n})$
Phase incorrect | $\text{D}[\textsc{Cnot}_{n}]+4$ | $4n$ | $4$ | $\leq 2n(\left\lceil 2\log_{2}\left(\frac{n+2}{2}\right)\right\rceil+8)+\mathcal{O}(\log{n})$
Table 4: Different implementations of a controlled-swap between two $n$-qubit
registers. The depth $\text{D}[\textsc{Cnot}_{n}]\leq\left\lceil
2\log_{2}\left(\frac{n+2}{2}\right)\right\rceil$ is from Eq. 18.

####  B.2.1 $\textsc{Swap}_{n}$ in linear depth without ancillary qubits

It is simple to construct $\textsc{Swap}_{n}$ with depth $\mathcal{O}(n)$
without any ancillary qubits. As the circuit that swaps two qubits is
constructed from three Cnot gates as follows,

a controlled-swap below is obtained by replacing the middle Cnot with a
Toffoli gate.

A circuit that implements Eq. 20, a swap between $n$ pairs of qubits, is then
the above repeated $n$ times in sequence, each controlled by the same qubit as
follows.

####  B.2.2 $\textsc{Swap}_{n}$ in logarithmic depth without ancillary qubits

Constructing $\textsc{Swap}_{n}$ with depth $\mathcal{O}(\log{n})$ without any
ancillary qubits requires a little more thought. Let us consider a more
general problem. Suppose we have an arbitrary unitary operator $V$ that is
self-inverse, meaning $V^{2}=\mathbb{I}$ – one may verify that the two-qubit
swap satisfies this property. Our goal is to implement a multi-target
controlled-$V$ gate on $n$ registers

$\displaystyle|0\rangle\langle 0|\otimes\mathbb{I}+|1\rangle\langle 1|\otimes
V^{\otimes n}.$ (21)

To begin, consider the following circuit identity, which is motivated by the
‘toggling‘ trick in Häner  _et al._ (2017).

Observe the the bottom qubit may be dirty – its state does not affect the
computation, and remains unchanged at the end of it.

Thus a multi-target controlled-$V$ on $n$ registers may be constructed by
applying $n$ singly-controlled $V$ gates in parallel before and after a single
multiply-controlled not gate, using a total of $n$ extra dirty qubits as
follows.

As the additional qubits may be dirty, this is easily modified to use no
ancillary qubits at all. Let us apply the multi-target $V$ on $\lceil
n/2\rceil$ registers, using any $\lfloor n/2\rfloor$ qubits from the other
registers as dirty qubits. When $n$ is odd, the topmost $V$ may be controlled
directly by the $|z\rangle$ qubit. We then apply the same circuit on the
remaining registers by using qubits in the initial targets as control qubits.
In total, this uses at most $2n$ controlled-$V$ gates and two multiply-
controlled not gates on $\lceil n/2\rceil$ qubits, each with cost given by
Table 3.

####  B.2.3 T-gate decomposition

Each controlled-swap may be decomposed into Clifford+T gates using standard
techniques. For instance, the standard synthesis of each Toffoli uses $7$
$T$-gates Shende  _et al._ (2006), as seen below.

Thus one might expect that $\textsc{Swap}_{n}$ in logarithmic depth requires
$14N$ $T$-gates. However, simple cancellations using the above decomposition
reduces this to $10N$ $T$-gates.

A further reduction to just $4N$ $T$-gates is possible if we allow the output
state to be correct up to a phase factor. The decomposition by Barenco  _et
al._ (1995) below, using the gate $G=S^{\dagger}\cdot H\cdot T\cdot H\cdot S$,
approximates the Toffoli gate up to a minus sign on one of the matrix
elements.

Thus a controlled-swap is obtained by a simple modification as follows.

Using this approximate controlled-swap, a version of $\textsc{Swap}_{n}$ that
is correct up to a $\pm 1$ phase may be obtained by replacing the middle Cnot
with $\textsc{Cnot}_{n}$, which may be implemented with logarithmic depth. As
this incorrect phase may be absorbed into the garbage state of the data-lookup
oracle, we may apply this phase-incorrect swap operation without loss of
generality.

##  Appendix C Indicator Function Construction

There is an alternative construction based on implementing an _indicator
function_. That is, the function

$e^{(n)}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{N},$

where $N=2^{n}$, which maps a string $x\in\\{0,1\\}^{n}$ to an exponentially
long encoding which is $1$ at position $x$ and zeros everywhere else.

We observe that $e^{(n)}$ can be implemented with the following parameters.

######  Theorem 1.

For $n\geq 1$, let $U_{n}$ be the unitary for the $n$th indicator function,
$e^{(n)}$. That is, the circuit mapping

$|x\rangle|y\rangle\mapsto|x\rangle|e^{(n)}(x)\oplus y\rangle$

for all $x\in\\{0,1\\}^{n}$ and $y\in\\{0,1\\}^{N}$. There is a circuit
computing $U_{n}$ in depth $O(\log^{2}N)$ with $O(N)$ T gates without _any_
ancillary qubits.

###### Proof.

When $n=1,2$ there are trivial circuits without ancillary qubits. For $n>2$,
let us suppose we have arbitrarily many clean ancillary qubits. We divide the
input bits $x$ into two halves, $x_{hi}$ and $x_{lo}$, then recursively
compute $e^{(n/2)}(x_{hi})$ and $e^{(n/2)}(x_{lo})$ in
$O(2^{n/2})=O(\sqrt{N})$ clean ancillary qubits each.

Each output of $e^{(n)}(x)$ is the AND of a bit in $e^{(n/2)}(x_{lo})$ and a
bit in $e^{(n/2)}(x_{hi})$. Each bit is used $O(\sqrt{N})$ times, so we can
finish XORing $e^{(n)}(x)$ into $y$ with an array of Toffoli gates of
$O(\sqrt{N})$. Alternatively, we can make $O(\sqrt{N})$ copies of each vector
and do all the Toffoli gates simultaneously.

Now suppose the ancillary qubits are dirty. Dirty qubits cannot store a qubit
in the same way as clean qubits; since the initial state of the qubit is
arbitrary, the information is encoded in the _change_ in state rather than the
actual state. To implement a Cnot controlled on a dirty qubit, for instance,
we apply the Cnot first, flip or not flip the qubit, then apply another Cnot.
If there was no change, the two gates cancel, otherwise exactly one fires.

Recall that the Toffoli gate has an implementation up to a faulty sign (which
we can tolerate) as three Cnot interleaved with $G$ or $G^{{\dagger}}$. As
described above, we can implement each Cnot with a pair of Cnots and, more
importantly, a recursive call to the subroutine which populates that qubit,
i.e., an indicator function. Actually, we use the previously described circuit
for $\textsc{Cnot}_{O(\sqrt{N})}$ instead of many individual Cnot gates for
each Toffoli involving that bit.

The depth cost for $\textsc{Cnot}_{O(\sqrt{N})}$ is $O(\log(\sqrt{N}))=O(n)$.
Additionally, to compute $U_{n}$ we need 4 recursive calls to $U_{n/2}$. The
depth satisfies the recurrence $D(n)=4D(n/2)+O(n)$, so
$D(n)=O(n^{2})=O(\log^{2}N)$.

Finally, suppose we apply the array of Toffoli gates in _two_ layers instead
of just one simultaneous layer. Since we are only applying Toffolis to half of
the $|y\rangle$ register at any time, the other half can be used as dirty
ancillary qubits. Asymptotically, this is much more than the $O(\sqrt{N})$
dirty qubits we need to compute $U_{n/2}$. Hence, we can implement $U_{n}$
without any additional qubits. ∎

It is wasteful to compute all of $e^{(n)}(x)$ in ancillary qubits, but it can
be used to compute an arbitrary function. Better is to divide the input into
two pieces, similar to how we compute the indicator function.

######  Theorem 2.

Suppose $f\colon\\{0,1\\}^{n}\to\\{0,1\\}^{b}$ is an arbitrary function, and
let $U$ be the unitary mapping

$|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle,$

for all $x\in\\{0,1\\}^{n}$ and $y\in\\{0,1\\}^{b}$.

There is a circuit for $U$ of depth $O(\log^{2}N+\log b)$, using $O(bN)$ dirty
ancillary qubits and $O(\sqrt{N})$ $T$ gates. Alternatively, there is a
circuit for $U$ using $O(\sqrt{bN})$ T gates and only $O(\lambda\sqrt{bN})$
dirty ancillary qubits, but with depth $O(\sqrt{bN}/\lambda+\log^{2}N)$, for
any $1\leq\lambda\leq\sqrt{bN}$.

###### Proof.

Divide the input into $n-k$ and $k$ bit pieces, where $k$ is to be determined
later. Let $\hat{f}\colon\\{0,1\\}^{n-k}\to\\{0,1\\}^{b\times 2^{k}}$ be

$\hat{f}(x_{hi})=\big{(}f(x_{hi}x_{lo})\big{)}_{x_{lo}\in\\{0,1\\}^{k}},$

the function which outputs the function for all possible values of the low
order bits, given the high order bits.

Suppose, for the moment, that we have as many clean ancillary qubits as we
want. We can naïvely compute $\hat{f}(x_{hi})$ by constructing
$e^{(n-k)}(x_{hi})$, making $b\cdot 2^{k}$ copies, and computing the parity of
some subset of bits of $e^{(n-k)}(x_{hi})$ for each output bit of
$\hat{f}(x_{hi})$. Constructing $e^{(n-k)}(x_{hi})$ requires $O(2^{n-k})$
ancillary qubits, $O(2^{n-k})$ T gates and $O((n-k)^{2})$ depth. The rest is
done with $\textsc{Cnot}_{b\cdot 2^{k}}$ gates to make copies and
$\textsc{Cnot}_{O(2^{n-k})}$ gates conjugated by Hadamards to compute
parities. This uses many ancillary qubits–$O(2^{n-k})$ for the original vector
times $O(b2^{k})$ copies is $O(bN)$ qubits.

Since the layers of Cnot gates compute (in the output bits) a linear function
of the inputs, it is not difficult to adapt for dirty ancillary qubits. Just
apply the linear function, flip the dirty ancilla qubits that are set to $1$,
then apply the linear function again, appealing to the identity $T(x\oplus
y)\oplus T(y)=T(x)$ for a linear function. Thus, whatever state $|y\rangle$
was in the dirty qubits, we still manage to compute $T(x)$.

We have shown how to compute $\hat{f}(x_{hi})$ and XOR it into dirty ancillary
qubits. We also know how to compute $e^{k}(x_{lo})$ and XOR $b$ copies of it
into dirty ancillary qubits. Think of $\hat{f}(x_{hi})$ as a $b\times 2^{k}$
matrix, then all that remains is to return the correct column of
$\hat{f}(x_{hi})$. If we also think of $e^{k}(x_{lo})$ as a length $2^{k}$
column vector, then we are computing a matrix/vector product. The simplest way
to do this is to make $b$ copies of $e^{k}(x_{lo})$ and execute $b$
vector/vector products in parallel, at a cost of $O(2^{k})$ Toffoli gates for
each one.

To compute the Toffoli gates on dirty ancillary qubits, we decompose them into
Cnot gates and single qubit gates. The layers of Cnot gates are linear, so it
is possible to compute each such layer with dirty ancilla qubits.

Computing $\hat{f}(x_{hi})$ uses $O(bN)$ ancillary qubits, $O(2^{n-k})$ T
gates, and has depth $O((n-k)^{2}+k+\log b)$. The rest of the circuit has
$O(b2^{k})$ ancillas to store $\hat{f}(x_{hi})$ and/or copies of
$e^{k}(x_{lo})$, and uses $O(b2^{k})$ T gates in depth $O(k^{2}+\log b)$.
Since the T gate count is $O(2^{n-k}+b2^{k})$, we set $k$ such that
$2^{k}\approx\sqrt{N/b}$, and it becomes $O(\sqrt{bN})$.

It is possible to trade off depth and number of ancillary qubits. We only need
$O(2^{n-k})$ qubits to store $e^{(n-k})(x_{hi})$ in the computation of
$\hat{f}(x_{hi})$, if we are willing to compute parities for each of the
$b2^{k}$ output bits of $\hat{f}(x_{hi})$ one at a time, in depth $O(b2^{k})$.
More generally, we can use $O(\lambda 2^{n-k})$ ancillary qubits for any
integer $\lambda\in[1,b2^{k}]$ and use depth $O(b2^{k}/\lambda)$. For the
optimal T count we use the same setting of $k$, giving
$O(\sqrt{bN}/\lambda+\log^{2}N)$ depth with $O(\lambda\sqrt{bN})$ ancillary
qubits and $O(\sqrt{bN})$ T gates.

∎

##  Appendix D Pure-state preparation implementation details

The approach by Shende, Bullock, and Markov Shende  _et al._ (2006)
synthesizes a unitary $A$ that prepares a pure state
$A|0\rangle=\sum_{x=0}^{N}\frac{a_{x}}{\|\vec{a}\|_{2}}|x\rangle=|\psi\rangle$
with arbitrary coefficients in $N=2^{n}$ dimensions. The underlying circuit,
illustrated below for the example of $N=8$ for positive coefficients,

is built from $j\in[n]$ multiply-controlled arbitrary single qubit rotations,
$U_{j}$ where

$\displaystyle U_{j}=\sum_{x=0}^{2^{j}-1}|x\rangle\\!\langle x|\otimes
e^{i2\pi\theta_{j,x}Z},$ (22)

for some set of rotation angles $\theta_{j,x}$. Note that it suffices to
consider $Z$-phase rotations as rotations about the $X,Y$ Pauli operators are
equivalent up to a single-qubit Clifford similarity transformation. Each
multiplexor is applied twice – once to create a pure state with the right
probabilities $|a_{x}|^{2}$, and once to apply the correct phase
$e^{i\arg{[a_{x}]}}$. Below we describe how $U_{j}$ may be implemented using
the data-lookup oracle of Eq. 4

$\displaystyle
O|x\rangle|0\rangle|0\rangle=|x\rangle|a_{x}\rangle|\mathrm{garbage}_{x}\rangle,$
(23)

and evaluate the overall error and cost of state preparation.

###  D.1 Multiply-controlled phase gate from data lookup oracles

Consider a multiply-$n$-controlled arbitrary single qubit rotation

$\displaystyle U=\sum_{x=0}^{2^{n}-1}|x\rangle\\!\langle x|\otimes
e^{i2\pi\theta_{x}Z},$ (24)

where each rotation angle $\theta_{x}\in[0,1)$. Given a number state
$|x\rangle$ and an arbitrary single-qubit state $|z\rangle$, this unitary
performs a controlled-rotation

$\displaystyle U|x\rangle|z\rangle=|x\rangle e^{i2\pi\theta_{x}Z}|z\rangle.$
(25)

Each rotation angle has a binary expansion

$\displaystyle\theta_{x}=\sum_{k=0}^{\infty}\frac{a_{x,i}}{2^{k+1}}.$ (26)

By truncating to the above to $b$-bits of precision, we obtain an integer
approximation $a_{x}$ of $\theta_{x}$ where

$\displaystyle
a_{x}=2^{b}\sum_{k=0}^{b-1}\frac{a_{x,k}}{2^{k+1}},\quad\left|\frac{a_{x}}{2^{b}}-\theta_{x}\right|<\frac{1}{2^{b}}.$
(27)

Let us encode these values of $a_{x}$ into the data-lookup oracle, and express
its T cost as the function $f(n,b)$. Its output is then

$\displaystyle O|x\rangle|0\rangle^{\otimes
b}|0\rangle=|x\rangle\left[\bigotimes_{k=0}^{b-1}|a_{x,k}\rangle\right]|\mathrm{garbage}_{x}\rangle,$
(28)

where we explicitly represent the number state $|a_{x}\rangle$ in terms of its
component qubits.

####  D.1.1 Approach using arbitrary single-qubit synthesis

One possible approximation, call it $U^{\prime}$, of $U$ in Eq. 24 applies the
single-qubit rotation $e^{i\pi Z/2^{k}}$ to the target state $|z\rangle$,
controlled by the state $|a_{x,k}\rangle$. The garbage register is then
uncomputed by running $O$ in reverse. Explicitly, this circuit realizes the
transformation

$\displaystyle|x\rangle|0\rangle^{\otimes b}|0\rangle|z\rangle$ (29)
$\displaystyle\rightarrow$
$\displaystyle|x\rangle\left[\bigotimes_{k=0}^{b-1}|a_{x,k}\rangle\right]|\mathrm{garbage}_{x}\rangle|z\rangle$
$\displaystyle\rightarrow$
$\displaystyle|x\rangle\left[\bigotimes_{k=0}^{b-1}|a_{x,k}\rangle\right]|\mathrm{garbage}_{x}\rangle
e^{i\pi\sum^{b-1}_{k=0}a_{x,k}Z/2^{k}}|z\rangle$ $\displaystyle=$
$\displaystyle|x\rangle|a_{x}\rangle|\mathrm{garbage}_{x}\rangle e^{i2\pi
a_{x}/2^{b}Z}|z\rangle$ $\displaystyle\rightarrow$
$\displaystyle|x\rangle|0\rangle^{\otimes b}|0\rangle e^{i2\pi
a_{x}/2^{b}Z}|z\rangle.$

Now, each controlled-arbitrary phase rotation decomposes into $2$ arbitrary
single-qubit rotations, and CNot gates – Note that a decomposition into $1$
arbitrary single-qubit rotation is possible if we modify the above for the
range $\theta_{x}\in(-1/2,1/2)$, but the explanation is slightly more
complicated. As any arbitrary single-qubit rotation is approximated to error
$\epsilon$ using $\mathcal{O}(\log{(1/\epsilon)})$ T gates Kliuchnikov  _et
al._ (2013), we may use a triangle inequality to bound the error to

$\displaystyle\|U-U^{\prime}\|$
$\displaystyle\leq\left\|\sum_{x=0}^{2^{n}-1}|x\rangle\\!\langle
x|\otimes(e^{i2\pi\theta_{x}Z}-e^{i2\pi a_{x}/2^{b}Z})\right\|+2b\epsilon$
$\displaystyle\leq\max_{|y|<1/2^{b}}\left|(e^{i2\pi y}-1)\right|+2b\epsilon$
$\displaystyle<\frac{2\pi}{2^{b}}+2b\epsilon.$

Thus for any target error $\|U-U^{\prime}\|=\delta$, we may solve for the
$b,\epsilon$ parameters and bound the number of T gates required to

$\displaystyle f(n,b)+\mathcal{O}(\log^{2}{(1/\delta)}),\quad
b=\mathcal{O}(\log{(1/\delta)}).$ (30)

####  D.1.2 Approach using phase gradients

A more efficient approach Gidney (2018) uses a Fourier state as a resource

$\displaystyle\mathcal{F}=\frac{1}{\sqrt{2^{b}}}\sum_{k=0}^{2^{b}-1}e^{-2\pi
ik/2^{b}}|k\rangle.$ (31)

combined with a reversible adder

$\displaystyle\textsc{Add}|x\rangle|y\rangle$
$\displaystyle=|x\rangle|{y+x}\mod{2^{b}}\rangle$ (32)

Observe that

$\displaystyle\textsc{Add}|x\rangle|\mathcal{F}\rangle=e^{2\pi
ix/2^{b}}|x\rangle|\mathcal{F}\rangle.$ (33)

Thus the controlled adder, known to cost $\mathcal{O}(b)$ T gates,

$\displaystyle\textsc{Cadd}=\textsc{Add}\otimes|0\rangle\langle
0|+\textsc{Add}\otimes|1\rangle\langle 1|$ (34)

realizes the controlled-phase rotation

$\displaystyle\textsc{Cadd}|x\rangle|\mathcal{F}\rangle|z\rangle=|x\rangle|\mathcal{F}\rangle
e^{2\pi ix/2^{b}Z}|z\rangle.$ (35)

Thus another possible approximation, call it $U^{\prime\prime}$, uses this
adder, controlled by the target state $|z\rangle$, to the registers containing
the desired phase rotation $|a_{x}\rangle$, and the Fourier state. This
realizes the same transformation in Eq. 29, using the circuit depicted below.

Assuming that the Fourier state is prepared perfectly, this approximates $U$
with error

$\displaystyle\|U-U^{\prime\prime}\|$
$\displaystyle\leq\left\|\sum_{x=0}^{2^{n}-1}|x\rangle\\!\langle
x|\otimes(e^{i2\pi\theta_{x}Z}-e^{i2\pi a_{x}/2^{b}Z})\right\|$
$\displaystyle\leq\max_{|y|<1/2^{b}}\left|(e^{i2\pi
y}-1)\right|<\frac{2\pi}{2^{b}}.$

The state preparation unitary $A^{\prime\prime}$ applies $n$ such
approximations $U_{j}^{\prime\prime}$ to the multiply-controlled rotations
$U_{j}$, leading to an overall error bounded by

$\displaystyle\left\|\prod_{j=0}^{n-1}U_{j}-\prod_{j=0}^{n-1}U_{j}^{\prime\prime}\right\|\leq\sum_{j=0}^{n-1}\|U_{j}-U_{j}^{\prime\prime}\|<\frac{2n\pi}{2^{b}}.$

Note that the cost of approximating the Fourier state to error $\epsilon$ has
a T cost of $\mathcal{O}(b\log{(1/\epsilon)})$. This imperfect Fourier state
$|\mathcal{F}^{\prime}\rangle$ contributes a one-time error of $\epsilon$,
following the inequality

$\displaystyle\|W(|\mathcal{F}^{\prime}\rangle\otimes\mathbb{I})-(W|\mathcal{F}\rangle\otimes\mathbb{I}\|\leq\||\mathcal{F}^{\prime}\rangle-|\mathcal{F}\rangle\|\leq\epsilon,$
(36)

for any arbitrary unitary operator $W$. Thus $A^{\prime\prime}$ prepares the
state
$|\psi^{\prime\prime}\rangle=A^{\prime\prime}|0\rangle|\mathcal{F}^{\prime}\rangle$,
which approximates $|\psi\rangle$ with error

$\displaystyle\delta=\||\psi^{\prime\prime}\rangle-|\psi\rangle|\mathcal{F}\rangle\|\leq\frac{2\pi
n}{2^{b}}+\epsilon.$

The total error $\delta$ may be controlled by choosing
$b=\Theta(\log{(\frac{n}{\delta})})$ and $\epsilon=\Theta(\delta)$.

The total T cost of arbitrary state preparation is then then the sum of costs
of the data-lookup oracles
$f(j,b)=\mathcal{O}(\frac{2^{j}}{\lambda}+b\lambda)$, adders, and the Fourier
state:

$\displaystyle\textsc{T}\;\text{cost}=$
$\displaystyle\left(\sum_{j=0}^{n-1}f(j,b)+\mathcal{O}(b)\right)+\mathcal{O}(b\log{(1/\epsilon)})$
(37)
$\displaystyle=\mathcal{O}(2^{n}/\lambda+nb\lambda+nb+b\log{(1/\epsilon)})$
$\displaystyle=\mathcal{O}\left(\frac{N}{\lambda}+b(\lambda n+b)\right)$
$\displaystyle=\mathcal{O}\left(\frac{N}{\lambda}+\lambda\log^{2}{\left(\frac{N}{\delta}\right)}\right).$