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 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 d) and depth (dn) using at most O (nd 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 (n + m) + 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{ dn + n}).