首次系统性探索：量子比特连接性限制对量子电路复杂性的影响

摘要 

在量子比特连接性限制的情况下，给定任意多个辅助量子比特，本工作为量子态制备和酉矩阵实现这两个基本问题设计了（近似）最优量子电路，并首次系统地探索了量子比特连接性限制对量子电路复杂性的影响。相关论文已发表在期刊IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems上。

01

背景介绍

在过去十年里，量子比特数量和寿命都实现了显著增长，尤其是近两年，量子比特数量的发展更为迅速。然而，当在实际量子设备上执行特定量子电路时，双量子比特门的实现常受到量子比特连接性的限制。在某些主流的量子比特实现方案（例如超导量子比特）中，双量子比特门仅能作用在特定的量子比特对上。尽管量子比特连接性限制对量子电路的实现产生了负面影响，但其影响程度目前尚未得到充分的系统研究。
量子比特连接性限制可以用一个连通图  来表示，其中顶点集  表示量子比特集合，边集  表示如果  ，则可在量子比特  上直接作用一个双量子比特门。用来表示量子比特连接性限制的连通图被称作限制图。量子比特连接性限制的种类繁多，如一些早期芯片的一维链图、谷歌Sycamore等芯片的二维网格图、IBM芯片的砖墙图。图1为两种常见的量子比特连接性限制实例：一维链限制和二维网格限制。

图1. 量子比特连接性限制实例：一维链限制和二维网格限制。‍

为了研究量子比特连接性限制对量子电路的影响，我们需要引入电路复杂性的度量。量子电路复杂性具有三种常见的度量：电路大小、电路深度和量子比特数。其中，电路大小对应“量子电路中量子门的个数”；电路深度对应“执行量子电路的并行运行时间”；量子比特数对应“量子电路的空间成本”。值得一提的是，量子电路深度（时间）和辅助量子比特数（空间）之间往往是此消彼长的。因此，为了压缩量子电路深度（时间），需要利用空间换取时间。不同的量子比特连接性限制，将会对量子电路复杂性产生不同程度的影响。而对其进行系统性的研究，将有助于设计出不同连通图限制下的高效量子电路，以减小量子电路大小和深度，从而提高量子算法在实际设备上的运行效果。

02

研究问题

本文主要研究量子电路中的两个基本问题——量子态制备和酉矩阵实现——在量子比特连接性限制下的量子电路复杂度。在量子机器学习算法和哈密尔顿量模拟量子算法中，量子态制备（Quantum State Preparation, QSP）是一个重要且核心的过程，且上述算法的量子加速往往依赖于量子态的快速制备。量子态制备问题是指，对任意给定的  维的复向量  和任意  (  )个辅助量子比特，设计量子电路来制备复向量  所对应的   -量子比特量子态  。另一个更普遍的问题是任意酉矩阵实现（General Unitary Synthesis, GUS），即给定任意大小为  的酉矩阵  和任意  (   )个辅助量子比特, 设计量子电路  满足对于任意  ,    。由于量子算法可以用酉矩阵形式表示，因此任意酉矩阵的高效量子电路实现即任意量子算法的高效实现。

在无量子比特连接性限制的情况下，上述两个问题的量子电路复杂度已经得到广泛的研究[1-3]。而在有量子比特链接性限制的情况下，其电路复杂度还未得到系统性研究。在不同的量子比特连接性限制情况下，本文在量子态制备问题和任意酉矩阵的最优时间-空间（电路深度-辅助量子比特数）权衡上进行探索，并研究量子比特连接性限制对其电路复杂度的影响。
03

主要结论

本文研究了量子比特连接性限制对量子电路大小和深度两个方面的影响。
首先，本文研究了连接性限制对量子电路大小的影响。在任意连接性限制下，本文构造了量子态制备以及酉矩阵实现下最优大小的量子电路。令人惊讶的是，量子比特连接性限制并没有增加上述两种问题所需的电路大小的阶。
其次，本文研究了连接性限制对量子电路深度的影响。相较于电路大小，连接性限制对量子电路深度的影响则更加复杂。在一维链、  -维网格、完全   -叉树、扩展图等几种不同的常见连接性限制情况下，本文构造了最优或近似最优电路深度的量子态制备和酉矩阵实现的量子电路。本文证明，量子比特连接性限制并没有增加几乎所有量子态制备和酉矩阵操作所需的电路深度的阶，除非辅助量子比特数是指数量级。然而，与无限制的情况相比，量子比特连接性限制确实阻碍了电路实现时的时间-空间权衡：它使得利用大量辅助量子比特来实现较小深度的量子电路变得更加困难。对于在量子态制备和酉矩阵实现中，量子电路深度的上下界，如下表1和2所示。

同时，本文也研究了各类实际存在的连接性限制对量子电路复杂度的影响。研究表明，有一些限制图的度量对量子电路深度产生了负面影响，如：图的直径、顶点的度、图扩展以及最大匹配的大小等。

表1.在辅助量子比特和不同图限制下-量子比特量子态制备的电路深度。所有的限制图包含  个顶点。-网格表示大小为  的  维网格，其中  。当  或者  时，  维网格分别为一维链和二维网格。完全  叉树表示每个非叶子节点都有  个子节点的树。当  或者  时，完全叉树分别为二叉树和星图。

表2.在辅助量子比特和不同图限制下-量子比特酉矩阵实现的电路深度。所有的限制图包含  个顶点。-网格表示大小为  的  维网格，其中  。当  或者  时，  维网格分别为一维链和二维网格。完全  叉树表示每个非叶子节点都有  个子节点的树。当  或者  时，完全叉树分别为二叉树和星图。

相关论文：Pei Yuan, Jonathan Allcock and Shengyu Zhang, "Does Qubit Connectivity Impact Quantum Circuit Complexity?" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 43, no. 2, pp. 520-533, Feb. 2024.论文地址：https://ieeexplore.ieee.org/document/10239109
参考文献[1] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan and Shengyu Zhang, "Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 42, no. 10, pp. 3301-3314, doi: 10.1109/TCAD.2023.3244885.[2] Pei Yuan, and Shengyu Zhang. "Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits." Quantum 7 (2023): 956.[3] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. "Quantum state preparation with optimal circuit depth: Implementations and applications." Physical Review Letters 129.23 (2022): 230504.