Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis

The Quantum State Preparation problem aims to prepare an n-qubit quantum state $|\psi_v\rangle=\sum_{k=0}^{2^n-1}v_k|k\rangle$ from initial state $|0\rangle^{\otimes n}$, for a given vector $v=(v_0,\ldots,v_{2^n-1})\in\mathbb{C}^{2^n}$ with $\|v\|_2=1$. The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth complexity remains open in the general case with ancillary qubits. In this paper, we study efficient constructions of quantum circuits for preparing a quantum state: Given $m=O(2^n/n^2)$ ancillary qubits, we construct a circuit to prepare $|\psi_v\rangle$ with depth $\Theta(2^n/(m+n))$, which is optimal in this regime. In particular, when $m=\Theta(2^n/n^2)$, the circuit depth is $\Theta(n^2)$, which is an exponential improvement of the previous bound of $O(2^n)$. For $m=\omega(2^n/n^2)$, we prove a lower bound of $\Omega(n)$, an exponential improvement over the previous lower bound of $\Omega(\log n)$, leaving a polynomial gap between $\Omega(n)$ and $O(n^2)$ for the depth complexity. These results also imply a tight bound of $\Theta(4^n/(m+n))$ for depth of circuits implementing a general n-qubit unitary using $m=O(2^n/n)$ ancillary qubits. This closes a gap for circuits without ancillary qubits; for circuits with sufficiently many ancillary qubits, this gives a quadratic saving from $O(4^n)$ to $\tilde\Theta(2^n)$.Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime. The results can be viewed as (optimal) time-space tradeoff bounds, which is not only theoretically interesting, but also practically relevant in the current trend that the number of qubits starts to take off, by showing a way to use a large number of qubits to compensate the short qubit lifetime.