Nearly Optimal Circuit Size for Sparse Quantum State Preparation

Abstract

Quantum state preparation is a fundamental and significant subroutine in quantum computing. In this paper, we conduct a systematic investigation on the circuit size (the total count of elementary gates in the circuit) for sparse quantum state preparation. A quantum state is said to be $d$-sparse if it has only $d$ non-zero amplitudes. For the task of preparing an $n$-qubit $d$-sparse quantum state, we obtain the following results: \textbf{Without ancillary qubits:} Any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(\frac{nd}{\log n}+n)$ without using ancillary qubits, which improves the previous best results. It is asymptotically optimal when $d=\mathrm{poly}(n)$, and this optimality holds for a broader scope under some reasonable assumptions. \textbf{With limited ancillary qubits:} (i) Based on the first result, we prove for the first time a trade-off between the number of ancillary qubits and the circuit size: any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(\frac{nd}{\log (n+m)}+n)$ using $m$ ancillary qubits for any $m\in O(\frac{nd}{\log nd}+n)$. (ii) We establish a matching lower bound $\Omega (\frac{nd}{\log (n+m)}+n)$ under some reasonable assumptions, and obtain a slightly weaker lower bound $\Omega (\frac{nd}{\log (n+m)+\log d}+n)$ without any assumptions. \textbf{With unlimited ancillary qubits:} Given arbitrary amount of ancillary qubits available, the circuit size for preparing $n$-qubit $d$-sparse quantum states is $\Theta (\frac{nd}{\log nd}+n)$.