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

Abstract

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 {the} initial state $|0\rangle^{\otimes n}$, for a given unit vector $v=(v_0,v_1,v_2,\ldots,v_{2^n-1})^T\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 when ancillary qubits are available. In this talk, we study quantum circuits when there are $m$ ancillary qubits available. We construct, for any $m$, circuits that can prepare $|\psi_v\rangle$ in depth $\tilde O\big(\frac{2^n}{m+n}+n\big)$ and size $O(2^n)$, achieving the optimal value for both measures simultaneously. These results also imply a depth complexity of $\Theta\big(\frac{4^n}{m+n}\big)$ for quantum circuits implementing a general $n$-qubit unitary for any $m \le O(2^n/n)$ number of ancillary qubits. This resolves the depth complexity for circuits without ancillary qubits. And for circuits with exponentially many ancillary qubits, our result quadratically improves the currently best upper bound of {$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 parameter regime. The results can be viewed as (optimal) time-space trade-off 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.

Speaker Intro

田国敬，中科院计算所副研究员，CCF量子计算专业组委员，CCF理论计算机专委委员。2017年博士毕业于北京邮电大学，毕业论文被评为中国通信学会优秀博士学位论文（全国共10篇）。主要研究方向有：量子算法设计、量子电路优化、量子非局域性、量子模拟等，目前已在TCAD、PRR、QST、PRA等相关领域国际期刊及会议上发表论文二十多篇。主持多项北京市自然科学基金和国家自然科学基金项目，并获得博新计划资助（全国计算机专业共16人）。