Low-depth quantum state preparation

Abstract

A crucial subroutine in quantum computing is to load the classical data of N complex numbers into the amplitude of a superposed n=⌈log_{2}N⌉-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least O(N) constant weight operations. However, the proof assumes that only n qubits are used, whereas 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 propose quantum algorithms with O(n^{2}) circuit depth to encode any N complex numbers using only single- and two-qubit gates, and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with O(N^{2}) ancillary qubits, O(n^{2}) circuit depth, and O(n^{2}) average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits, and at most O(n) qubits are entangled. We also prove a fundamental lower bound Ω(n) for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with O(n^{2}). The algorithms are expected to have wide applications in both near-term and universal quantum computing.