Toward optimal circuit size for sparse quantum state preparation

Compared to general quantum states, the sparse states arise more frequently in the field of quantum computation. In this work we consider the preparation for $n$-qubit sparse quantum states with $s$ nonzero amplitudes and propose two algorithms. The first algorithm uses $O(ns/{log}_{2}n+n)$ gates, improving upon previous methods by $O({log}_{2}n)$. Moreover, the classical runtime of this algorithm is optimal. We further establish a matching lower bound for any algorithm that is not amplitude aware and employs at most $poly(n)$ ancillary qubits. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path. An application is encoding the input data into a state with specified Hamming weight $k$ in quantum machine learning, for which our algorithm constructs a circuit of size $O(\left(\genfrac{}{}{0pt}{}{n}{k}\right){log}_{2}n)$. This surpasses previous results by $O(k/{log}_{2}n)$ and is close to the lower bound $O(\left(\genfrac{}{}{0pt}{}{n}{k}\right))$. The classical runtime is also nearly optimal. Both algorithms shrink the existing gap theoretically and provide increasing advantages numerically.