Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits

Abstract

As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of $|i\rangle |0^n\rangle \to |i\rangle |\psi_i\rangle $forall$i\in \{0,1\}^k$forthegiven$n$-qubit states $|{\psi }_i⟩$. In this paper, we construct a quantum circuit for implementing CQSP, with depth $O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$ and size $O\left(2^{n+k}\right)$ for any given number $m$ of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are \optimal for any integer parameters $m,k\ge 0$ and $n\ge 1$.When$k=0$, the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation $|0^n⟩|0^m⟩\to |\psi ⟩|0^m⟩$. This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to $\Theta (n+2^n/(n+m))$ and its size complexity to $\Theta (2^n)$ for any $m$. Another fundamental problem, unitary synthesis, asks to implement a general $n$-qubit unitary by a quantum circuit. Previous work shows a lower bound of $\Omega (n+4^n/(n+m))$ and an upper bound of $O(n{2}^n)$ for $m=\Omega (2^n/n)$ ancillary qubits. In this paper, we quadratically shrink this gap by presenting a quantum circuit of the depth of $O\left(n{2}^{n/2}+\frac{n^{1/2}{2}^{3n/2}}{m^{1/2}}\right)$.