Space-time tradeoff for sparse quantum state preparation

Abstract

In this work, we investigate the trade-off between the circuit depth and the number of ancillary qubits for preparing sparse quantum states. We prove that any $n$-qubit $d$-spare quantum state (i.e., it has only $d$ non-zero amplitudes) can be prepared by a quantum circuit with depth $O\left(\frac{nd\log m}{m\log m/n}+\log nd\right)$ using $m\ge 6n$ ancillary qubits, which achieves the current best trade-off between depth and ancilla number. In particular, when $m=\Theta (\frac{nd}{\log d})$, our result recovers the optimal circuit depth $\Theta (\log nd)$ given in \hyperlink{cite.zhang2022quantum}{[Phys. Rev. Lett., 129, 230504(2022)]}, but using significantly fewer gates and ancillary qubits.