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

Quantum 7, 956 (2023).

https://doi.org/10.22331/q-2023-03-20-956

As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0^nrangle to |irangle |psi_irangle $ for all $iin {0,1}^k$ for the given $n$-qubit states $|psi_irangle$. In this paper, we construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac{2^{n+k}}{n+k+m}right)$ and size $O(2^{n+k})$ 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,kge 0$ and $nge 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^nrangle|0^mrangle to |psirangle |0^mrangle$. 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(n2^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 $Oleft(n2^{n/2}+frac{n^{1/2}2^{3n/2}}{m^{1/2}}~~right)$.