Circuit Complexity of 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 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 n-qubit d-sparse quantum states, we obtain the following results: (a) We propose the first approach that uses $o(dn)$ elementary gates without using ancillary qubits. Specifically, it is proven that any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(dn/log n + n) without using ancillary qubits. This is asymptotically optimal when $d = poly(n)$, and this optimality extends to a broader scope under some reasonable assumptions. (b) We show that any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(dn/log d) and depth Θ(log dn) using at most O(ndlog d ) ancillary qubits, which not only reduces the circuit size compared to the one without ancillary qubits when d = ω(poly(n)), but also achieves the same asymptotically optimal depth while utilizing fewer ancillary qubits and applying fewer quantum gates compared to the result given in [PRL, 129, 230504(2022)]. (ii) We establish the lower bound Ω(dn/log(n + m) + log d + n) on the circuit size with m ancillary qubits available. we also obtain a slightly stronger lower bound under reasonable assumptions. (c) We prove that with arbitrary amount of ancillary qubits available, the circuit size for preparing n-qubit d-sparse quantum states is Θ(dn/log dn + n).