量子科技中心_量科网

量子并行化由于物理约束（如不可克隆定理）而面临重大挑战。摩尔和尼尔森在他们关于量子电路复杂性的开创性工作[MN01，1998年公布]中提出的猜想生动地说明了这一点：看似简单的受控酉“阶梯”形式的幺正操作需要最小深度为Ω(n)的电路。如果该猜想成立，这个下界将标志着与经典并行性的重大背离，并证明著名的NC≠P猜想的量子原生类似物。 该工作通过将所有该类电路压缩到深度O(log n)（这是可能的最佳结果）来否定地解决了摩尔-尼尔森猜想。这些并行化是精确的、无需辅助量子比特的，并且可以在poly(n)时间内计算完成。该研究团队还考虑了限制在二维连通性的电路，为此推导出了最优深度O(√n)的压缩。 更广泛地说，该研究通过引入一种量子分块预计算技术在量子并行化项目中取得进展，该技术在一定程度上类似于经典动态规划中的Arlazarov、Dinič、Kronrod和Faradžev方法[Arl+70]，通常被称为“四俄罗斯人方法”。该团队还将此技术应用于更一般的“级联”电路，例如获得了受控log(n)量子比特幺正操作的阶梯结构的多项式深度缩减。