本篇是物理学顶级期刊《物理评论快报》（Physical Review Letter ）发表论文 Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications 的解读。该工作分别针对一般量子态以及稀疏量子态，讨论了量子线路深度最优的制备算法。相关技术可应用于量子计算领域的众多问题。该工作由北京大学博士后张笑鸣，助理教授李彤阳、袁骁（通讯作者）合作完成。

　　论文地址：https://doi.org/10.1103/PhysRevLett.129.230504

01 问题背景

　　量子态制备是量子计算中最基础的问题之一。一方面，量子态制备的速度决定了将经典信息编码在量子计算机的最终效率，另一方面，它是许多重要量子算法的必要步骤。态制备的速度取决于对应量子线路的深度。对于一般 n 比特量子态，多项式 O(poly(n)) 的线路深度需要借助指数多辅助比特才能实现。这限制了量子算法的效率。

　　此外，稀疏量子态在量子计算中有着广泛应用，其制备所需的资源极大的低于一般量子态。近年来，稀疏量子态制备得到了许多关注，但其线路深度的理论极限仍然是一个开放性问题。

02 算法结果

　　对于一般量子态制备，本文设计了一个线路深度为 Θ(n)，辅助比特数为 O(N) 的算法，其中N=2^{n}。

　　在该工作之前，文献 [1-2] 也独立地提出了两种深度最优的制备算法。与之相比，该工作的优势主要体现在两个方面。一是稀疏的连接性。本文提出的算法所对应的比特连接结构如图1所示，每个比特仅需与另外至多4个比特连接，极大地降低了实现难度。

　　图1. 算法硬件结构示意图。每个方框对应一个量子比特，两比特量子门被限制只能作用于实线所连接的量子比特对上。(a) 结构包括一个平行二叉树。(b) 平行二叉树的其每一层与另一个垂直二叉树相连，此处以第二层为例。

　　另一方面，该方案的 Clifford+T 门分解线路深度为 O(nlog(n/ε))，对比本文之前的方案具有多项式提升。这使得该方案在容错量子计算机上的实现更为高效。

　　对于稀疏量子态，已知最优的算法线路深度为 O(log(nd))，其中 d 为目标量子态的非零元素个数。本文通过引入辅助比特，提出了一种线路深度为 O(log(nd))，比特个数为 O(ndlogd)的制备方案。

　　该方案的线路深度达到了理论极限，且对比已知最优的算法具有指数加速。此外，辅助比特个数随 n,d 皆以多项式形式增长，且接近理论极限。

03 算法应用

　　量子模拟：量子态制备是许多量子模拟算法的必要步骤。我们考虑形为 H=\sum_{p=0}^{P-1} \alpha_{p} V(p) 的哈密顿量，其中 V(p) 为 n 个单比特泡利算符的直积。基于态制备算法中相关的技术，该工作证明演化算符 e^{-i H t} 可以用线路深度为 O(log(nP)(αt+log1/ε))，比特数为 O(nP) 的量子线路进行模拟。其中，ε 为模拟精度，α=\sum_{p=0}^{P-1}\left|\alpha_{p}\right| 。

　　量子线性方程组求解：我们考虑可以被表示为 H=\sum_{p=0}^{P-1} \alpha_{p} V(p) 的可逆矩阵，以及非零元素个数为 d=O(poly(n)) 的归一化向量 b。量子线性方程组求解的目标是输出一个量子态，其振幅正比于 H^{-1} b。该工作证明算法所需的量子线路深度为 \widetilde{O}(p o l y(n P), \alpha, \kappa)，比特个数为 O(poly(n,P))。其中，κ 为 H 的条件数。特别的，当 P,d=O(1) 时，量子线路的深度与比特个数分别可以被降低为 \widetilde{O}(\log (n) \operatorname{poly}(\kappa)) 以及 O(poly(n))，对比已知最优的经典以及量子算法，都具有指数优势。

　　量子随机存储器：量子随机存储器可以被看作是量子态制备的弱化形式。其目标是实现操作 \sum_{k=0}^{2^{n}-1} \psi_{k}|k\rangle|0\rangle \rightarrow \sum_{k=0}^{2^{n}-1} \psi_{k}|k\rangle\left|D_{k}\right\rangle。基于稀疏量子态制备技术，当非零的 \left|D_{k}\right\rangle 个数为 d 时，量子随机存储器的时间、空间复杂度分别为 O(log(nd)) 以及 O(nd)。作为对比，传统的量子随机存储器的时间、空间复杂度分别为 O(n) 以及 O(2^{n})。当 d=O(polylog(n))时，对比传统方案，该工作在时间和空间复杂度上都具有指数优势。

参考文献

[1] X. Sun, G. Tian, S. Yang, P. Yuan, and S. Zhang, Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis, arXiv:2108.06150 (2021).

[2] G. Rosenthal, Query and depth upper bounds for quantum unitaries via Grover search, arXiv:2111.07992 (2021).