Low-depth Quantum State Preparation

A crucial subroutine in quantum computing is to load the classical data of $N$ complex numbers into the amplitude of a superposed $n=\lceil \log_2N\rceil$-qubit state. It has been proven that any algorithm universally implements this subroutine would need at least $\mathcal O(N)$ constant weight operations. However, the proof assumes that the operations only act on the $n$ qubits and the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We proposed quantum algorithms with $\mathcal O((\log_2 N)^2)$ circuit depth to encode an arbitrary $N$-bit classical data using only single-, two-qubit gates and local measurements with ancillary qubits. Different variances are proposed with different space and time complexities. In particular, we present a scheme with the number of ancillary qubits $\mathcal O(N^2)$, the circuit depth $\mathcal O((\log_2 N)^2)$, and the average runtime $\mathcal O((\log_2 N)^2)$, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on constant number of qubits and we only need to maintain entanglement of at most $\mathcal O(\log_2 N)$ qubits. The algorithms are expected to have wide applications in both near-term and universal quantum computing.