Nearly Optimal Circuit Size for Sparse Quantum State Preparation

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: $\mathbf{\text{Without}}\mathbf{\text{ancillary}}\mathbf{\text{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{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)$, and this optimality holds for a broader scope under some reasonable assumptions. $\mathbf{\text{With}}\mathbf{\text{limited}}\mathbf{\text{ancillary}}\mathbf{\text{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 $\mathrm{\Omega }(\frac{nd}{\log (n+m)}+n)$ under some reasonable assumptions, and obtain a slightly weaker lower bound $\mathrm{\Omega }(\frac{nd}{\log (n+m)+\log d}+n)$ without any assumptions. $\mathbf{\text{With}}\mathbf{\text{unlimited}}\mathbf{\text{ancillary}}\mathbf{\text{qubits:}}$ Given arbitrary amount of ancillary qubits available, the circuit size for preparing $n$-qubit $d$-sparse quantum states is $\mathrm{\Theta }(\frac{nd}{\log nd}+n)$.