Abstract
We propose a novel deterministic method for preparing arbitrary quantumstates. When our protocol is compiled into CNOT and arbitrary single-qubitgates, it prepares an $N$-dimensional state in depth $O(\log(N))$ and spacetimeallocation (a metric that accounts for the fact that oftentimes some ancillaqubits need not be active for the entire circuit) $O(N)$, which are bothoptimal. When compiled into the $\{\mathrm{H,S,T,CNOT}\}$ gate set, we showthat it requires asymptotically fewer quantum resources than previous methods.Specifically, it prepares an arbitrary state up to error $\epsilon$ withoptimal depth of $O(\log(N) + \log (1/\epsilon))$ and spacetime allocation$O(N\log(\log(N)/\epsilon))$, improving over $O(\log(N)\log(\log(N)/\epsilon))$ and $O(N\log(N/\epsilon))$, respectively. We illustrate how thereduced spacetime allocation of our protocol enables rapid preparation of manydisjoint states with only constant-factor ancilla overhead -- $O(N)$ ancillaqubits are reused efficiently to prepare a product state of $w$ $N$-dimensionalstates in depth $O(w + \log(N))$ rather than $O(w\log(N))$, achievingeffectively constant depth per state. We highlight several applications wherethis ability would be useful, including quantum machine learning, Hamiltoniansimulation, and solving linear systems of equations. We provide quantum circuitdescriptions of our protocol, detailed pseudocode, and gate-levelimplementation examples using Braket.