摘要:利用量子态的叠加性和纠缠, 量子计算为显著地加速经典算法, 例如大数分解、求解线性方程组、量子多体系统模拟等问题, 提供了可能. 随着量子计算机硬件的快速发展, 探索量子计算超越经典计算极限方向的研究受到了越来越多的重视. 针对一类特定的问题, 现有的量子设备已经展现出超越经典计算机的能力. 但由于一些量子算法(诸如大数分解等问题)需要依赖于一个通用的大规模的容错的量子计算机, 考虑到现阶段的量子设备的量子比特数十分有限, 且容易与环境发生退相干, 近期的研究主要集中在探索基于含噪声的中等规模量子设备以及浅层量子线路的量子优越性. 一些采样问题被作为演示量子优越性的候选项提出. 本文介绍和总结了几个可以在现阶段的量子设备上实现的量子优越性问题, 并就其中两个备受关注的量子优越性问题—随机量子线路模拟和玻色采样及其衍生的采样问题的理论和实验进展、经典模拟算法等展开讨论. 随着上述两类量子优越性问题在超导和光学量子平台的实现, 我们预期当前和近期的量子设备将解决更多问题, 从而实现更一般的量子优势.
关键词: 量子优越性/
随机量子线路/
玻色采样/
经典模拟

English Abstract

全文HTML

--> --> -->

一些重要的诸如Shor算法的例子预示了量子计算机相较于经典计算机具有更强的能力^[1,2]. 但这些一般量子算法的实现需要具有数千逻辑量子比特或数百万物理量子比特的通用量子计算机^[3,4]. 而目前最先进的量子设备远不能达到运行这些算法的要求. 除了量子比特的数量远远不够外, 目前的量子设备还存在着两个关键的不足: 1)单个量子门的误差; 2)量子设备与环境的退相干作用. 为了有效地阐释量子计算机和经典计算机相比的优势所在, Harrow 和 Montaro^[5]形式化地定义了量子优越性问题需要满足的4个条件(以及一个可选的条件): 1) 一个具有良好定义的计算问题; 2) 一个可以求解该问题的适用于当前量子设备的量子算法; 3) 任何经典模拟器需要超大规模的时间和空间; 4) 复杂性理论的假设支持. 除以上4个条件外, 另一个可选的条件为: 存在一个可以有效区分量子算法和经典竞争者使用有限资源的输出结果的方法. 近些年来, 一些采样问题被作为量子优越性的候选项提出.
广义的采样问题是指得到特定分布的一个样本. 于是可以由多次独立采样的结果得出样本背后分布的性质. 在量子采样问题中, 在指定测量基矢下, 经过一个量子过程后得到的最终的量子态可以被视为基矢的特定分布, 因此, 对该量子态的一次测量就对应一次采样. 本文讨论的具有量子优越性的采样问题包括随机线路的采样问题^[6,7]、瞬时量子多项式线路的采样问题^[8]、玻色采样^[9]及其衍生出的问题^[10-13], 以及含有一个干净的量子比特的高混合的确定性量子计算(DQC1)^[14-16]. 理论上, 这些采样问题在基于一定复杂性假设下都是经典求解困难的.
随机线路采样　随机量子线路是指: 一类构造为单量子比特门层和双量子比特门层交替出现的量子线路, 其中单量子比特门层中的比特门具有一定的随机性, 但单比特和多比特门的排放位置固定的一种线路簇, 而一次采样则对应于对一个容易制备的量子初态(通常是全$ 0 $态), 经过随机线路后在计算基下进行一次测量, 即采样. 在随机线路采样这一量子优越性问题的进程中, Boixo等^[6]提出了一个特定网格结构的量子随机线路采样问题, 并估计当量子设备在有接近50个量子比特时, 经典计算机即无法有效模拟该电路, 从而预计50个量子比特的量子超导处理器即可以实现量子霸权. 因为当下的量子计算机的噪音和退相干作用, 该文献也论述了如何去验证量子设备采样的可靠性. 随后, Arute等^[7]实现了53个量子比特—悬铃木处理器的20层随机量子线路, 并在其上展示了量子优越性的采样实验. 悬铃木处理器可以在200 s的时间内以0.2%的保真度采样百万量级次一个量子电路. 中国科学技术大学潘建伟团队^[17]实现了66个量子比特的超导设备—祖冲之2.0, 当66个量子比特全部运行时, 可达到单比特门的误差平均值为0.14%, 两比特门的误差平均值为0.76%, 读取误差的平均值为4.77%. 为了验证该设备的有效性, 他们在其上执行了56个量子比特, 20层的随机线路采样实验. 最近, 该团队又在祖冲之2.0的基础上升级了祖冲之2.1超导量子芯片, 把平均读出保真度从95.48%提高到97.74%, 并在祖冲之2.1上实现了60个量子比特24层随机线路的采样实验^[18].
对于随机线路采样问题, 是否存在有效的经典模拟器也受到了广泛研究. 针对Boixo等^[6]提出的随机线路的特定结构, Iboldsymbol团队^[19]利用张量网络的方法, 在Iboldsymbol的超算上计算出了$ 7\times 7 $量子比特、深度为27层的随机线路的所有振幅, 以及$ 7\times 8 $量子比特、深度为22层的部分振幅. 之后, Google团队^[20]利用冯诺依曼路径的方法, 在Google云平台上实现了$ 7\times 8 $量子比特、深度为30层的$ 2\times 10^5 $个振幅的计算. 与此同时, 阿里团队^[21]提出, 他们可以利用一个分布式经典模拟算法, 在阿里云平台上实现$ 8\times 8 $量子比特、深度为40层的一个振幅的计算, 以及$9\times 9 \times 40,\; $$ 10 \times 10 \times 35,\; 11 \times 11 \times 31,\; 12 \times 12 \times 27$的一个振幅的计算(这里$ l_1\times l_2 \times d $表示$ l_1\times l_2 $的量子比特上的深度为$ d $的电路). Li等^[22]通过将张量网络和“隐分解”的方法相结合, 在太湖之光上实现了$ 7\times 7 $量子比特、深度为39层的全振幅的计算, 以及深度为56层的一个振幅的计算. 本源量子团队^[23] 估算他们可以在16天内针对该类型电路实现72比特, 22层的一次采样. Chen等^[24]在神威上进行模拟, 可运行一维链上的1000量子比特以及二维 125 × 8量子比特 42层一个振幅的计算, 72量子比特32层(2D-Bristlecone)的随机量子线路的一次采样. 阿里团队之后又在文献[25]中提出他们可以对Bristlecone-70结构(70量子比特) 1 + 32 + 1 深度的随机线路, 通过阿里云平台在0.43 s内求出任意振幅(以及70量子比特1 + 36 + 1/1 + 40 + 1深度采样时间5.6/580.7 s). 这里需要注意的是全振幅的模拟可以用来生产若干次采样的样本, 另一方面, 一次采样也可以利用蒙特卡罗等方法通过计算少量次振幅进行估计.
针对Arute等^[7]提出的53量子比特的量子计算机, Iboldsymbol团队^[26]在2019年针对该问题设计了经典模拟采样算法, 并通过小的样例估计出在Summit超算上可在少于2.55天的时间内得到20层的采样, 以及6.45天内得到36层的采样. 之后阿里团队^[27]在2020年针对该电路采样问题, 进行经典模拟, 并在阿里云上进行测试, 可在少于20天的时间内实现该问题的模拟(42层, 保真度0.2%). 近期文献[28]通过一种张量网络方法可以只用60 GPU在5天内模拟(20层, 保真度73.9%).
瞬时量子多项式线路的采样　和随机线路采样类似, 瞬时量子多项式线路的采样也是针对一种特定结构的量子线路的采样, 与随机线路不同的是, 瞬时多项式线路除了第一层和最后一层外, 中间层都是由对易的对角门构成, 因为是对易的, 所以中间的所有门可以通过任意的时间次序执行, 这也解释了这里的“瞬时”的含义. Shepherd和Bremner^[8]介绍了一个量子优越性问题—瞬时量子多项式(instantaneous quantum polynomial time, IQP)协议. IQP协议是一个受限的, 非通用的量子计算模型. 该协议可以被视为是一个两体的经典通信信道. Alice设计了一个经典不可解的问题, 并拥有一个可用来验证结果的正确性的隐变量. Bob用Alice的输入执行IQP线路(一个多项式深度的电路). 最终, Alice通过结合协议运行的时间以及收到结果的正确性来论述量子霸权. Bremner等^[29]证明了IQP线路的计算即使以41%的乘法性近似也是经典模拟困难的. 之后Bremner等^[30]进一步证明了在基于一些额外的复杂性假设下, 该问题的加法性近似也是经典模拟困难的. IQP协议后来被推广到量子计算的连续变量(continuous variable, CV)模型中^[31,32].
玻色采样　玻色采样(boson sampling, BS)是建立在光学系统上的一个量子过程. 标准的BS是在线性光学网络的输入端的前$ n $个模中每个注入一个光子, 该线性光学网络的元器件的组件系数具有一定的随机性, 并在输出端对光子数进行采样. Aaronson和Arkhipov^[9]在2011年提出了将BS作为量子优越性的一个候选项问题. BS的原型^[9]需要用到一个线性光学网络装置. 因为该原型需要制备很多个高品质的单光子, 实验上实现该过程也很困难. 后来Lund等^[10]在此基础上提出了散射玻色采样(scattershot boson sampling, SBS), 该模型解决了初始模型单光子制备比较困难的问题, 但却需要一个额外的装置及测量过程来确定输入的光子模式. 之后SBS模型被进一步进行了改良^[11], 即高斯玻色采样(Gaussian boson sampling, GBS). GBS之后被推广为振动玻色采样^[33], 该模型是在BS的启发下对分子谱的研究. GBS利用单模压缩态(single-mode squeezed states, SMSS)作为输入, 且不需要通过额外的装置和测量来确定输入态. 需要强调的是, 虽然GBS是为了降低标准玻色采样和SBS实验的困难性提出的, 但目前仍然缺少严格的复杂性证据证明该过程是经典计算难的. 然而, 有充分的理由相信该问题的确是经典计算困难的, 因为Hafnian问题(GBS的输出概率和矩阵的一个函数Hafnian相关)可以作为积和式的推广代入玻色采样中, 即可得到GBS. 除此之外, GBS有很多应用, 比如求解图上的一些理论问题^[34-37]、近似优化问题^[38]、分子对接问题^[39]、点处理问题^[40]等. 考虑到GBS模型输出端收集每个模中的光子数的困难性, Quesada等^[41] 提出了带阈值的GBS模型, 该模型和GBS模型的区别是在接收端只是探测有无光子, 并不对光子数进行计数, 他们在文章中也论证了该模型的计算困难性. 最后, 上海交通大学的金贤敏团队^[13]近期也提出了时间戳玻色采样.
玻色采样及其衍生问题在实验上也取得了显著的进展^[42-51]. 特别地, Wang等^[51]最近实现了在60个模中注入20个光子的干涉仪. Bentivega等^[52]实现了第一个SBS实验, 其中6个不同的光子对整合到光子电路中. Zhong等^[49]实现了第一个GBS实验, 其中以很高的采样率实现了5个光子的GBS. Su等^[48]通过使用光子数分析探测器, 可以将高斯态转变为非高斯态, 并给出了使用GBS设备实现的非高斯态的制备. 值得关注的是, 近期潘建伟团队^[53]实现了一个100个模的线性光学网络—九章, 并在其上执行了带阈值的高斯玻色采样实验, 实验成功地在67个模中观测到光子.
玻色采样及其衍生问题的经典模拟在近些年也取得了一定进展. Neville等^[54]通过Metropolis独立采样方法, 可以得到玻色采样的一次近似采样, 他们可以在普通笔记本上实现30个光子的一次近似采样, 在超算上可以实现50个光子的一次近似采样. 并通过和其他采样算法(包括暴力采样、拒绝采样方法)作比较, 来证明该近似采样算法的正确性. Clifford和Clifford^[55]给出了一个$ \theta\left( {n2^n} \right) $时间、多项式空间的一个精确采样算法, 其中$ n $是光子数. Wu等^[56]提出了一个$O\left( {m \sinh^2 r} \right) + $$ O\left( { \mathrm{poly}(n)2^{8 n/3}} \right)$ 时间、多项式空间的GBS模拟采样算法, 其中$ m $是模数, $ n $是光子数, $ r $是压缩参数. 当有指数规模的计算空间时, 可以进一步将时间复杂性提升到$ O\left( {m \sinh^2 r} \right) + O\left( { \mathrm{poly}(n) 2^{2 n}} \right) $. 可以在华为昆仑服务器上实现20个光子的采样, 并通过模拟预测可在神威超算上实现30个光子的采样. Quesada等^[41]针对带阈值的GBS模型给出了一个$ O(mn2^n) $时间复杂性的一个经典模拟算法, 并在文献[57]中对GBS进行了经典模拟, 他们的算法可以在56个CPU的云上进行20个光子的精确采样.
量子随机线路采样作为量子霸权的候选项之一, 近几年来备受关注. 这一方向的超导量子设备在不断地更新, 经典无法超越量子的趋势也越来越显著. Iboldsymbol更是计划在2023年实现1000量子比特的量子计算机. 相信在未来的某一天, 当量子随机线路的规模和精度各自达到某个阈值时, 人们将无法再找到可以在几个小时内甚至几年内在经典计算机上进行有效模拟的算法. 而在玻色采样及其衍生物实验中, 近期潘建伟团队^[53]在基于光学器件搭建的实验平台上实现的高斯玻色采样至今仍无经典计算机可以有效模拟, 也充分显示了量子优越性的里程碑进展.
本文组织如下, 第2节介绍3种量子优越性相关的采样问题. 由于IQP电路的采样受到的关注较少, 在第3节和第4节介绍实验进展和经典模拟进展时, 只讨论了量子随机线路采样和玻色采样的进展. 第5节总结和讨论量子优越性的现状和未来.

本节主要介绍量子随机线路的采样、IQP电路采样和玻色采样问题需要处理的具体任务.
2

-->

2.1.量子随机线路采样

3 -->

2.1.1.方案介绍

在量子计算机上, 采样就是对随机线路进行测量. 而经典计算机上则对应的是计算输出的希尔伯特空间上的概率分布上的一次采样. 随机线路的采样在经典计算机上进行模拟被认为是困难的(没有多项式时间的经典算法能够做到)^[58]. 而对量子计算机本身, 要实现大规模高深度的计算也对硬件的容错率提出了很高的要求. 因此量子电路的结构设计需要考虑到超导硬件的设计, 以及支持的简单门操作类型. 下面介绍两个特定结构的随机线路的模型.
Boixo等^[6]提出的随机线路模型如下:
? 执行一层H门.
? 重复$ d $轮下面两步操作.
??1)交替地执行一次图1中的CNOT门, 这里一个黑点代表一个量子比特, 两个黑点之间的连线表示这两个量子比特有门作用.
图 1 随机线路的CNOT门的8种不同的摆放方式^[6]. 其中第0层全部摆放H门, 电路中每8层循环一次(重复图中1—8层), 空白节点处随机放置$ {\boldsymbol I}, {\boldsymbol T}, {\boldsymbol X}^{1/2}, {\boldsymbol Y}^{1/2} $门, 两比特门为CZ门
Figure1. Eight different layouts of the CNOT gate in the random circuit, where all of qubits are performed H gate in the $ 0 $-th layer, and cycle once every 8 layers in the circuit (repeat 1–8 layers of this graph), the blank vertices are laid out $ {\boldsymbol I}, {\boldsymbol T}, {\boldsymbol X}^{1/2}, {\boldsymbol Y}^{1/2} $ randomly, and the two-qubit gates are all CZ gates^[6].

2)在每个量子比特上, 随机地作用一个集合$ \left\{ {{{\boldsymbol{I}}}, {{\boldsymbol{X}}}^{1/2}, {{\boldsymbol{Y}}}^{1/2}, {{\boldsymbol{T}}}} \right\} $中的门.
这里$ {{\boldsymbol{X}}}, {{\boldsymbol{Y}}} $依次为Pauli-$ X $门和Pauli-$ Y $门. 令$ {{\boldsymbol{A}}}^{t}: = {\rm e}^{-{\rm i}t {{\boldsymbol{A}}}/2} $. 根据该定义可得图1中$ {{\boldsymbol{X}}}^{1/2} $和$ {{\boldsymbol{Y}}}^{1/2} $门的定义.
随机线路采样是从这样的一个随机线路中进行一次采样(在电路结束时对电路在计算基下进行测量). 如果想要体现量子的性质, 这里深度$ d $需要满足一定要求. 理想的量子随机线路采样的输出分布的概率值满足Potor-Thomas分布, Boixo等^[6]通过模拟实验展示了在深度超过20层时, 量子电路输出的概率值跟Portor-Thomas分布逐渐开始靠近.
Google团队在2019年提出了一个更大规模的网格结构, 门的摆放更复杂的量子随机线路模型—悬铃木量子计算机, 并且在量子设备上进行了测试, 可以在几秒内实现53个量子比特, 20层两比特门的随机线路保真度至少为0.2%的采样, 该随机线路结构如图2所示^[7].
图 2 悬铃木处理器随机线路架构^[7]. 其中第0层全部摆放H门, 电路每层迭代重复模式ABCDCDBA, 两个模式中间由一层随机放置的单比特门$ {\boldsymbol X}^{1/2},\; {\boldsymbol Y}^{1/2},\;{\boldsymbol W}^{1/2} $构成, 两比特门为控制相位门和部分$ i $SWAP门的乘积(部分$ i $SWAP门后跟随一个控制相位门构成)
Figure2. Random circuit architecture for Sycamore processor, where all of qubits are performed H gates in the $ 0 $-th layer, the layer of the circuit iterates and repeats the pattern ABCDCDBA, a layer of random single-qubit gates are performed between two modes, which constructed by $ {\boldsymbol X}^{1/2},\;{\boldsymbol Y}^{1/2},\; {\boldsymbol W}^{1/2} $, the two-qubit gate is the multiplication of the partial-iSWAP gate and control-phase gate (constructed by partial-iSWAP gate followed by a control-phase gate)^[7].

因此, 在Google提出的随机量子线路采样问题框架中^[6,7], 随机量子线路$ {{\boldsymbol{U}}} $是由一系列电路层组成的, 每层电路在一组单比特和双比特门中按照一定的限制随机地选取一系列门, 电路层的深度为$ d $时, 产生的分布为$p_{\boldsymbol {U}}(x) = |\left\langle {x|\psi_d} \right\rangle |^2$, 其中$ x $是计算基下的比特串.
随后, 中国科学技术大学潘建伟团队^[17]实现了一个规模更大的66量子比特的超导设备—祖冲之2.0处理器. 该处理器的结构也是网格状结构, 研究团队在其上实现了56个量子比特, 20层的随机量子线路采样实验. 在祖冲之2.0基础上升级的祖冲之2.1的平均读出保真度由95.4%提升到了97.74%, 潘建伟团队在祖冲之2.1上实现了60量子比特24层深度的随机量子线路^[18].
3 -->

2.1.2.随机线路采样的基准

Boixo等^[6]通过交叉熵差别(cross entropy difference)论述了他们提出的网格上的量子线路采样的正确性. 他们展示了当电路可模拟时, 其交叉熵可以被高效地通过测量估计出. 当经典计算机无法有效模拟时, 可以通过将电路划分为若干子部分分别进行模拟来对交叉熵进行估计, 从而对输出结果的正确性进行测试. 接下来简述一下量子优越性的基准—交叉熵的定义.
首先, 令$ \left| {\psi} \right\rangle = {\boldsymbol{U}}\left| {0} \right\rangle $为一个给定的随机线路$ {\boldsymbol{U}}\in \mathbb{C}^{2^n \times 2^n} $的输出态. 考察样本集合${\boldsymbol{S}}= \{ x_1, \;\cdots, $$ x_m \}$, 其中$ x_i $是一个长度为$ n $的二进制串, 通过对$ \left| {\psi} \right\rangle $的每个量子比特在计算基下进行一次测量得到. 令$ p_{A}(x|{\boldsymbol{U}}) $表示满足由算法A构造出的分布中样本$ x\in \{0, 1\}^n $出现的概率, 其中算法A构造的分布是对$ {\boldsymbol{U}}\left| {0} \right\rangle $在计算基下展开的分布的模拟, $ p_{\boldsymbol{U}}(x) $表示$ x $的精确的概率值. $p_{A}(x)$和$ p_{{\boldsymbol{U}}}(x) $之间的交叉熵定义为

$ H\left( {p_{A}, p_{{\boldsymbol{U}}}} \right) \equiv - \sum\limits_{x\in \{0, 1\}^{n}} p_{A} \left( {x|{\boldsymbol{U}}} \right)\log p_{{\boldsymbol{U}}}\left( {x} \right). $

Boixo等^[6]论述了如果该$ 7\times 7 $网格的随机线路深度足够大, 则$ p_{{\boldsymbol{U}}}(x) $的分布接近Porter-Thomas分布$ N{\rm e}^{-Np} $, 这里$ N = 2^n $为态空间大小. 因此, 在对该随机线路采样的优越性进行验证时, 他们通过对实验测量结果所得的分布和Porter-Thomas分布进行比较, 判断该输出的分布是否真实有效. 实际计算该交叉熵时, 通常是通过采样得到的包含$ m $个样本的集合S来对其均值进行估计. 此外, 他们定义了一个用于衡量算法A采样正确性的量—交叉熵差别:

$ \begin{split} \Delta H\left( {p_A} \right)&\equiv H_0-H(p_A,p_{\boldsymbol U})\\ & = \sum\limits_{x } \left(\frac{1}{2^n}-p_A(x|\boldsymbol U)\right)\frac{1}{\log p_{\boldsymbol U}(x)}. \end{split} $

这里算法$ A $既可以是多项式时间或者指数时间的经典模拟算法, 也可以是量子设备实现. 如果算法$ A $输出的样本满足均匀分布, $ \Delta H\left( {p_A} \right) = 0 $, 如果算法$ A $能够真实还原出$ p_{{\boldsymbol{U}}}(x) $的理论分布, $ \Delta H \left( {p_A} \right) = 1 $. Boixo等^[6]提出通过判断交叉熵差别是否大于0来判断其量子效应. 注意到这里为了得到交叉熵差别, 需要一个强大的经典计算机来得到$ p_{{\boldsymbol{U}}}(x_j) $.
在验证悬铃木处理器输出结果的正确性中, Arute等^[7]提出利用线性交叉熵作为基准的保真度. 该线性交叉熵定义为

$ \begin{split}\mathcal{F}_{\text{XEB}}&\equiv 2^n \left\langle { P\left( {x_i} \right)} \right\rangle_i - 1\\& = 2^n \sum\limits_{x\in \left\{ {0, 1} \right\}^n} p_{A}\left( {x|{\boldsymbol{U}}} \right)p_{{\boldsymbol{U}}}(x) - 1, \end{split} $

其中$ n $是量子比特的数目, $ P(x_i) $是理想的量子电路测得$ x_i $的概率, 且这里的$ x_i $是利用算法A (算法A可以是实验观测)得到的二进制串. 如果实验没有任何误差, 对实验结果进行采样得到的平均值$ \mathcal{F}_{\text{XEB}} = 1 $. 如果实验输出的是一个均匀分布, 此时$ \mathcal{F}_{\text{XEB}} = 0 $. 对于实际的量子设备, $ \mathcal{F}_{\rm XEB} $是一个介于0—1之间的数. 这里需要注意的是, 给定一个$ x_i $, $ P(x_i) $的值只能通过经典模拟该量子线路进行计算. 因此, 由于量子优越性问题的困难性, 当线路规模足够大时, $ \mathcal{F}_{\text{XEB}} $是无法在有效的时间内计算得到的, 因此需要近似的方法对$ \mathcal{F}_{\text{XEB}} $进行估计. 比较(2)式和(3)式可知, 线性交叉熵和交叉熵差别的唯一区别是这里直接用概率替换了原来的对数项.
Arute等^[7]说明了当保真度大于32%时, (对数)交叉熵区分具有更小的标准差, 反之当保真度小于32%时, 线性交叉熵具有更小的标准差. 由于验证悬铃木处理器的保真度较小, 因此Arute等^[7]中采用的是线性交叉熵方法进行保真度的分析. Aaronson和Gunn^[59]证明了与线性交叉熵相关的一个判定量子优势的问题无经典多项式时间算法可以求解.
2 -->

2.2.IQP线路的采样

一个IQP线路是一个形式为$ \mathcal{C} = {{{\boldsymbol{H}}}}^{\otimes n} {{\boldsymbol{D}}} {{{\boldsymbol{H}}}}^{\otimes n} $的量子线路, 其中$ {{{\boldsymbol{H}}}} $是Hadamard门, $ {{\boldsymbol{D}}} $是由$ n $的多项式个对角门生成的一个对角矩阵^[60]. IQP采样问题是通过将$ \mathcal{C} $作用于初始状态$ |0\rangle^{\otimes n} $而产生的$ n $位字符串上的分布$ p $进行采样, 之后在计算基上测量每个量子比特($ p $表示初始无噪声分布). 当$ {{\boldsymbol{D}}} $是在集合: (1)$ \sqrt{CZ} $, $ {{{\boldsymbol{T}}}} $门; 或者(2)$ {{\boldsymbol{Z}}}, CZ, CCZ $中均匀选取时, IQP线路的采样问题是经典模拟困难的. 该困难性基于玻色采样问题中的复杂性假设PGC (permanent of Gaussian conjecture)问题在IQP下的对应. Fujii和Tamate^[61]使用量子容错理论表明, 在噪声很小的情况下, IQP线路的采样问题仍是计算困难的.
以上的IQP线路允许门在系统中的任何量子位之间应用. 这意味着$ {{\boldsymbol{D}}} $满足集合(1)的随机线路中可能有$ O(n^2) $个门, 满足集合(2)的随机线路可能有$ O(n^3) $个门, 其中许多是作用在非邻接量子比特上的. 从实验的角度来看, 特别是针对超导量子计算机, 这是具有挑战性的, 因为超导量子设备的量子比特的作用都是局限在近邻的. 如果想要将非邻接量子比特上的门调整到邻接量子比特上执行, 需要增加SWAP门, 但一个问题是IQP线路中不允许有SWAP门. 于是最近Bremner等^[62]提出了稀疏的IQP采样, 该稀疏的IQP采样与一个稀疏图相关, 且其采样在一定复杂性假设下仍是计算 难的. 已经被证明, 稀疏的IQP采样在有$ O(n \log n) $长度个门或者深度为$ O(\sqrt{n}\log n) $时, 在二维的格点结构下就可以证明其计算难需要的一个关键复杂性假设.
2 -->

2.3.玻色采样及其衍生问题

继Aaronson和Arkhipov^[9]提出玻色采样问题后, 为了使得该问题更容易在实验上实现, 有很多更容易在实验上实现的衍生问题相继被提出.
3 -->

2.3.1.玻色采样

原始的玻色采样问题^[9]可以描述为: $ n $个无相互作用、不可分辨的玻色子, 在单粒子希尔伯特空间维数为$ m $的Fock空间中, 从某个给定的初始状态开始, 经过确定的演化, 在末状态进行投影到占据数表象基上的测量, 每次测量获得一个$ n $玻色子态, 即称为进行了一次玻色采样. 在初始条件、演化给定的情况下, 采样结果将服从一个确定的概率分布.
以实现玻色采样实验最常用的平台—线性光学平台为例, 如图3所示, 将$ n $个单光子由波导输入一个线性光学网络中, 该网络中可能存在不同波导模式间的互相叠加、干涉等, 所以也被称作干涉仪, 并可在输出的$ m $根波导中探测到光子. 在理想情况下, 每根波导仅能携带一种模式, 输入态到输出态演化可以在占据数表象下记为
图 3 玻色采样模型^[56]. 输入是$ n $个单光子, 经过线性光学网络后, 可在输出的$ m $个模中探测光子
Figure3. Device of boson sampling^[56]. The input are $ n $ photons, and one can detect photons on the $ m $ output modes through a linear optical network.

$ \left| {s_1,\;s_2, \;s_3,\; \dots, \;s_m} \right\rangle \rightarrow \left| {t_1,\; t_2,\; \dots, \;t_m} \right\rangle, $

其中$ s_i $表示向第$ 1, \;2, \;3, \;\cdots $个模式分别输入$s_1, s_2, $$ s_3,\; \cdots$个光子(在图3的示意图中, 前$ n $个模式分别各输入了一个光子, 而后$ m-n $个光子数为$ 0 $, 这是实验实现时的一般做法), $ t_i $表示在第$ i $个输出模式中探测到$ t_i $个光子, 有$\displaystyle \sum\nolimits_{i = 1}^m s_i = \sum\nolimits_{i = 1}^m t_i = n$. 遵从量子光学的一般记号, 描述单粒子演化的酉矩阵$ {\boldsymbol{U}} $定义为

$ b_j = \sum\limits_{i = 1}^n {U}_{ij} a_i, $

其中$ b_j $, $ a_j $分别对应$ m $个输出模式/输入模式光子的湮灭算符. 由于玻色子在这个过程中无相互作用, 整个Fock空间中多体态的演化算符$ {{\boldsymbol{W}}} $(即输出态服从$ \left| {\varPsi_{\rm out} }\right\rangle = {{\boldsymbol{W}}} \left| {s_1, s_2, s_3, \dots, s_m} \right\rangle $)可以由单粒子的演化算符$ {\boldsymbol{U}} $完全确定, 故采样得到的分布也可以显式计算得到. Aaronson和Arkhipov^[9]证明了

$ \left\langle {t_1 t_2 \cdots t_m} \right| {{\boldsymbol{W}}} \left| {s_1 s_2 \cdots s_m} \right\rangle = \frac{\text{perm} ({\boldsymbol{U}}_{\rm ST})}{\sqrt{\displaystyle \prod\nolimits_i t_i ! \prod\nolimits_i s_i !}}. $

因此玻色采样结果服从的概率分布为

$ \begin{split}p(t_1, t_2, \cdots, t_m) = \;&\left|\left\langle {t_1 t_2 \cdots t_m} \right| {{\boldsymbol{W}}} \left| {s_1 s_2 \cdots s_m} \right\rangle \right|^2 \\=\;& \frac{\left|\text{perm} ({\boldsymbol{U}}_{\rm ST})\right|^2}{\displaystyle \prod\nolimits_i t_i ! \prod\nolimits_i s_i !}, \\[-15pt] \end{split}$

其中, $ {\boldsymbol{U}}_{\rm ST} $矩阵为将$ {\boldsymbol{U}} $矩阵的第$ i $列重复$ s_i $次、第$ j $行重复$ t_j $次形成的一个$ n $维矩阵, perm表示该矩阵的积和式, 对于一个一般的$ n $维方阵$ {{\boldsymbol{A}}} $, 积和式定义为

$ \operatorname{perm}({{\boldsymbol{A}}}) = \sum\limits_{\boldsymbol \sigma\in S_n}\prod_{i = 1}^n a_{i, {\boldsymbol \sigma}(i)}. $

对比行列式定义$\det({{\boldsymbol{A}}}) = \displaystyle \sum\limits _{\boldsymbol \sigma \in S_{n}}\left(\operatorname {sgn}(\boldsymbol \sigma )\prod\limits _{i = 1}^{n}a_{i, {\boldsymbol \sigma} _{i}}\right)$, 两者十分相似, 但对于积和式, 一般而言$\operatorname{perm} $$ ({\boldsymbol{AB}}) \neq \operatorname{perm}({{\boldsymbol{A}}}) \operatorname{perm}({{\boldsymbol{B}}})$, 而能在多项式时间内计算行列式的快速算法均依赖于行列式的这一性质, 故积和式的计算对于经典计算机而言将会是一个困难的问题(更严格的分析证明积和式计算属于#P-hard问题), 而显式地计算玻色采样的概率分布(6)式将包含积和式的计算, 从而, 我们期待可以借助玻色采样实现量子霸权.
应当注意, 一个能够实现玻色采样的量子计算机, 其“计算过程”即体现为多体玻色子态的制备、演化以及最终测量的过程; 另外, 高效地实现玻色采样并不意味着能够高效地计算积和式, 具体来说, 光子数/模式数的增多将使得输出端测量得到某一给定状态的概率大幅下降, 即“采样率”很低, 进而通过计数某种输出状态的频率来准确估计相应积和式的值也变得非常困难; 玻色采样过程可以看作是量子光学中Hong-Ou-Mandel实验的扩展, 从而, 类似于Hong-Ou-Mandel实验, 不同模式光子之间不可忽略的量子干涉现象导致的巨大的多体希尔伯特空间维数是实现量子霸权的先决条件, 而这对$ {\boldsymbol{U}} $矩阵的形式提出了要求, 即$ {\boldsymbol{U}} $的形式过于简单将导致该玻色采样过程成为经典计算机可以有效模拟的, 一般认为, 酉演化$ {\boldsymbol{U}} $矩阵的选择应当服从随机酉矩阵的Haar测度, 即只要$ {\boldsymbol{U}} $足够任意, 便认为其可以实现量子优越性.
3 -->

2.3.2.高斯玻色采样

玻色采样提出后, 受制于确定性单光子源制备等难点, 其实验实现一直停留在小规模展示阶段, 难以达到实现量子优越性要求的$ n\approx 50 $界限. 与此同时, 一些基于玻色采样的理论工作被相继提出, 例如容许光子损耗的玻色采样(lossy boson sampling)^[12], 输入$ n+k $个光子, 但后选择出$ n $个光子的输出态, 即容许$ k $个光子的损耗, 由于对该过程的理论分析依赖于对损耗过程的理解, 所以对其能够实现量子优越性的阈值分析仍然有待解决.
在另外一些工作中, 研究者关注于利用非确定性的、更高效、易于制备的光子源, 以扩展原始的玻色采样, 达到实现量子优越性的目标. 如 Lund等^[10]提出了后来被称为SBS的方案, 如图4所示. 使用$ m $模的线性光学网络, 将$ m $个概率型光子源分别置于其输入端, 每个光子源将产生处于双模压缩态的光子(区别于单光子源的输入态具有确定的光子数, 由于其光子数的概率分布特性, 也被称作高斯态的一种), 利用双模压缩态的特性, 可以设计光路, 在输出端后选择出$ n $光子的测量事件, 但是, 这一方案的输入输出均有$\displaystyle {n^2\choose n}$种可能, 导致了采样空间的大幅增长.
图 4 SBS的装置简介^[63]. 该模型中输入为$ 2 m $个单模压缩态, 在其进入分束器和相移子装置后产生双模压缩态, 并通过一个额外的测量装置来固定SBS的线性光学装置$ \boldsymbol{U}_m $输入的光子数
Figure4. Brief introduction of SBS device^[63]. In this model, the input are $ 2 m $ single-mode compressed states, and the two-mode compressed states are generated after entering the beam splitter and the phase-shifting sub-device. An additional measuring device is used to fix the number of input photons for the linear optical device $ \boldsymbol{U}_m $ of SBS.

Kruse等^[63]随后注意到了SBS方案的缺陷: 该方法利用了概率型的光子源, 但其后选择过程却抛弃了光子源的概率特性. 他们据此提出了GBS的方案(图5), 去掉了SBS方案中的后选择过程, 直接将单模压缩态注入干涉仪, 并在输出端进行光子数测量, 他们证明了, 输出态测量得到光子数${\boldsymbol{S}} = $$ (s_1, s_2, \cdots s_m)$的概率为
图 5 GBS的装置简介^[63]. 输入端为K个单模压缩态注入线性光学网络, 在输出端的M个模中进行光子数探测
Figure5. Brief introduction to GBS device^[63]. The input terminal is a K single-mode compressed state injected into the linear optical network, and the photon number is detected in M modes at the output terminal.

$ \Pr(\boldsymbol S) = \frac{1}{\sqrt{\text{det}({\boldsymbol \sigma})}}\frac{\text{Haf}({{{\boldsymbol{A}}}_S) }}{s_1!s_2!\cdots s_m!}, $

其中${{\boldsymbol{A}}}_S$是分别取$ {{\boldsymbol{A}}} $中$ i $行/列和第$ m+i $行/列$ s_i $次得到的矩阵, 矩阵$ {{\boldsymbol{A}}} $定义为

$ {{\boldsymbol{A}}} = \begin{pmatrix} {0{\boldsymbol{}}} & {\boldsymbol{{{\boldsymbol{I}}}}}_m\\ {\boldsymbol{{{\boldsymbol{I}}}}}_m & {0{\boldsymbol{}}} \end{pmatrix}\left[ {{{{\boldsymbol{I}}}}_{2m} - {\boldsymbol \sigma}_{\rm Q}^{-1}} \right], $

且有$ {\boldsymbol \sigma}_{\rm Q} = {\boldsymbol \sigma} + {{{\boldsymbol{I}}}}_{2 m}/2 $. 协方差矩阵$ {\boldsymbol \sigma} $只包含被观测出的模的信息${{\boldsymbol{S}}} = \begin{pmatrix} \bigoplus_{j = 1}^m \cosh r_j & \bigoplus_{j = 1}^m \sinh r_j\\[3mm] \bigoplus_{j = 1}^m \sinh r_j & \bigoplus_{j = 1}^m \cosh r_j\end{pmatrix}$和线性光学网络$ {\boldsymbol{U}}_m $的信息,

$ {\boldsymbol \sigma} = \frac{1}{2}\begin{pmatrix} {\boldsymbol{U}}_m & {0{\boldsymbol{}}}\\ {0{\boldsymbol{}}} & {\boldsymbol{U}}_m^{\ast} \end{pmatrix}{{\boldsymbol{S}}}{{\boldsymbol{S}}}^{\dagger}\begin{pmatrix} {\boldsymbol{U}}_m^{\dagger} & {0{\boldsymbol{}}}\\ {0{\boldsymbol{}}} & {\boldsymbol{U}}_m^{t} \end{pmatrix} . $

$ \text{Haf} $表示Hafnian函数, 矩阵的Hafnian函数定义为

$ \text{Haf}({{{\boldsymbol{V}}}}): = \sum\limits_{{\boldsymbol \sigma}\in \mathcal{M}_{n}}\prod_{j = 1}^{n/2}{{\boldsymbol{V}}}({\sigma}_{2j - 1}, {\sigma}_{2j}) \ , $

其中 $ \mathcal{M}_{n} $是$[n] : = \{ 1, 2, \cdots, n \}$中的所有完美匹配构成的集合, $ V(i,\, j) $ 是$ {{\boldsymbol{V}}} $的第$ (i,\, j) $个元素. 例如, 当$ n $ = 4时, $ \mathcal{M}_{4} = \{ (12)(34), (13)(24), (14)(23) \} $, 其中$ (ij) $是一个匹配对, 因此

$ \begin{split}\text{Haf}({{{\boldsymbol{V}}}}) = \;& V(1, 2)V(3, 4) + V(1, 3)V(2, 4) \\&+ V(1, 4)V(2, 3) . \end{split} $

从定义来看, Hafnian是排列不变量. 交换$ {{\boldsymbol{V}}} $中的任意两列, 以及相同标号的两行, 得到的新矩阵的Hafnian值保持不变. 由Haf的定义知, Haf可以看作是积和式的扩展, 即:

$ \operatorname{Perm}({{\boldsymbol{G}}}) = \operatorname{Haf}\left(\begin{array}{cc} 0 & {{\boldsymbol{G}}} \\ {{\boldsymbol{G}}}^{t} & 0 \end{array}\right). $

从而, 任何能够计算Hafnian的算法也一定可以以同样的复杂度解决积和式的计算问题, 这一结果, 使得高斯玻色采样一经提出, 便成为在线性光学体系实现量子优势的有效方案. 类似于积和式, 精确地计算矩阵Hafnian是$ \#{\rm P} $-hard的^[64], 这暗示着具有相同压缩参数的GBS是经典计算难的, 求解Hafnian的经典最好的算法需要时间$ O(n^3 2^{n/2}) $^[65].
更进一步地, 考虑到实验上光子探测器实现光子数分辨的难度, 即探测器很多时候只能准确判断某个模式有/无光子, 而不能判断有几个光子, 基于这点, 高斯玻色采样可以被扩展为带阈值的玻色采样, Hafnian将继续扩展为Torontonian^[41]. 带阈值的玻色采样也是最容易进行大规模实验的方案.
Quesada等 ^[41]给出了带阈值的高斯玻色采样问题输出结果${\boldsymbol{S}} = \left( {s_1, \cdots, s_m} \right)$的概率为

$ \Pr(\boldsymbol S) = \frac{\text{Tor}({{\boldsymbol{A}}}_{S})}{\sqrt{\det({\boldsymbol \sigma})}}, $

其中$ \boldsymbol \sigma $是协方差矩阵, $ {{\boldsymbol{A}}}_S $是取$ {{\boldsymbol{A}}} $中与$\boldsymbol S$相关的行和对应的列得到的矩阵, Tor函数定义为

$ \text{Tor}({{\boldsymbol{A}}}) = \sum\limits_{z\in P([N])} (-1)^{|z|}\frac{1}{\sqrt{\det\left( {{{{\boldsymbol{I}}}}- {{\boldsymbol{A}}}_{(z)}} \right)}}, $

其中${\boldsymbol P}([{\boldsymbol n}])$是集合$[{\boldsymbol n}] = \{1, \cdots, n\}$的一个指数集合(包含所有子集合的集合), 是矩阵$ {{\boldsymbol{A}}} \in \mathbb{C}^{2^n\times 2^n} $的Torontonian函数.

近几年来, 随机线路的采样和玻色采样及其衍生的采样问题在实验上均已取得了显著的进展. 下面简要介绍一下量子随机线路和玻色采样的近期实验设计方案.
2

-->

3.1.量子随机线路采样的实验进展

2019年, Google团队首次在Sycamore 超导量子平台上实现了量子优越性^[7]. Sycamore量子芯片上有 53 个可用的量子比特, 86 个耦合器, 量子比特和耦合器都用transmon构成, 利用微波激发量子比特, 通过磁通调节耦合, 通过连接的谐振器读出量子态. Sycamore的平均单比特错误率达到了0.15%, 同时激发时也只略微高出一点, 控制在0.16%; 双比特平均错误率为0.36%, 同时激发时为0.62%; 单独读出错误率为3.1%, 同时读出错误率为3.8%. 通过简单地把门操作和读出操作的保真度相乘, 可以估计系统的保真度. 在该实验中, 最大的随机量子线路有53个量子比特, 1113个单比特门, 430个两比特门, 对每个量子比特进行一次测量, 通过相乘的简单模型估计系统的保真度可达到0.2%. 交叉熵$ \mathcal{F}_{\text{XEB}} $的不确定度为${1}/{\sqrt{N_{\rm s}}}$, 需要百万量级次抽样($N_{\rm s}$)来从实验上测定交叉熵.
交叉熵的测定需要对由超导随机量子线路抽样产生的百万量级的比特串中的每一个给出理想分布下对应的概率幅, 这个概率幅通过模拟随机量子线路得到, 但当随机量子线路的规模过大、纠缠程度太高时, 模拟随机量子线路在事实上是不可行的, 此时达到量子优越性区域. 为了表征量子优越性区域的超导量子电路的保真度, Google团队在电路设计中采用了3种、两类线路. 线路按照连接的完整度分为3种: 全量子线路、删减量子线路、分割量子线路. 其中全量子线路是2.1节中描述的完整线路; 分割量子线路中量子电路被切分为两块, 两块之间没有相互作用的量子比特; 类似分割量子线路, 删减量子线路也对全量子线路里的双比特门进行了一些删减, 使得线路成为相对独立的两块, 但是仅仅删减了分割处的部分两比特量子门, 所以两块量子线路并不是完全独立的. 3种不同完整度的量子线路的示意图如图6(a)左下角插图所示. 按照两比特门的纠缠程度分为两类线路, 其中双比特门排列为EFGHEFGH的线路中双比特门之间纠缠程度较小, 更容易模拟, 称为简单量子线路; 而双比特门排列为ABCDCDBA的线路更难模拟, 称为复杂量子线路. 简单量子线路和复杂量子线路的示意图分别如图6(a)右上角和图6(b)左上角插图.
图 6 量子优越性证明的实验结果^[7]　(a)在经典可验证区, 简单全量子线路的保真度与简单删减量子线路、简单分割量子线路、简单乘积模型的保真度符合得很好, 每个数据点是多个随机量子线路采样的平均值; (b)在量子优越区, 通过更简单的线路和简单乘积模型来估计复杂全量子线路的保真度. 红色时间标志表示经典模拟复杂全量子线路的验证任务需要的时间, 灰色时间标志表示经典模拟相应的采样任务需要的时间
Figure6. Experimental results of the proof of quantum advantage^[7]: (a) In the classical verifiable region, the fidelity of simple full quantum circuit accords well with that of simple truncated quantum circuit, simple split quantum circuit and simple product model. Each data point is the average of multiple random quantum circuit samples. (b) In the quantum advantage region, the fidelity of complex full quantum circuits is estimated by using simpler circuits and simple product models. The red time label represents the time required for the verification task of the classical simulation complex full quantum circuit, and the grey time label represents the time required for the corresponding sampling task of the classical simulation.

Goolge团队在实验中对量子线路层数为$ m = $ 14的简单全量子线路、简单删减量子线路、简单分割量子线路进行了采样和模拟, 如图6(a)所示. 在经典可验证区域内, 全量子线路保真度与相应的分割量子线路、删减量子线路、简单乘积预测的保真度符合得很好, 所以在达到量子优越性的大规模复杂线路区域内, 可以通过相应的分割量子线路、删减量子线路和简单乘积预测复杂大规模线路的保证度. 在量子优越性区域内, 53量子比特的大规模ABCDCDAB复杂量子线路的保真度随着线路层数的加深而降低. 实验中最大的量子线路层数达到20层, 在10个相同规模的随机量子线路上进行了$ 30\times10^6 $次采样, 用删减量子线路估计的保真度达到$ \mathcal{F}_{\text{XEB}} = (2.24\pm0.21)\times10^{-3} $. 以5西格玛的置信度可以断言在Sycamore量子计算机上此类规模线路的平均置信度大于0.1%. 实验结果如图6(b)所示.
估计经典计算机模拟需要消耗的计算资源时有两种估计, 一种是对验证任务的计算资源的估计, 一种是对采样任务的计算资源的估计. 如果实验中对超导随机量子线路进行了$ 10^6 $次采样, 估计的保真度为0.1%, 验证任务需要用经典计算机计算出全部的$ 10^6 $次采样得到的比特串对应的概率幅, 而采样任务只需要计算$ 10^6 \times $ 0.1%个比特串对应的概率幅, 因为对于采样任务而言, 大部分平庸的采样可以用均匀分布的背底表示. 对于53个量子比特的20层的复杂全量子线路, 在Sycamore上采样一百万次用了200 s, 预计在一百万核的经典计算机上通过Schr?dinger-Feynman算法进行模拟以产生相同保真度的采样结果需要10000年, 而验证任务则需要几百万年^[7].
Sycamore量子计算机对量子优越性的展示使得近期量子算法井喷式发展, 与此同时, 更高效的经典模拟算法也被提出来, 使得量子优越性显得不那么明显. 2021年6月, 中国科学技术大学潘建伟团队延续Google团队的工作, 制造出了量子比特数更多、门控精确度更高的祖冲之量子计算机—祖冲之2.0^[17]. 与Sycamore类似, 祖冲之量子计算机也是使用transmon作为量子比特; 与Sycamore相比, 祖冲之量子计算机的量子比特数提高到66个, 单比特门的精度提高到99.86%, 两比特门的精度提高到99.41%, 读出精度提高到95.48%. 该团队^[17]在祖冲之量子计算机上进行了最大规模为56量子比特、20层量子线路的复杂全量子线路随机量子线路采样, 采样一百万个比特串耗时230 s, 而实际实验中在1.2 h内进行了$ 1.9\times10^7 $次采样, 通过与Sycamore相同的估计方式估计出的祖冲之量子计算机在该规模下的保真度为$(6.62\pm0.72)\times $$ 10^{-4}$, 在9个西格玛的置信度下断言保真度不为0. 用Schr?dinger-Feynman算法模拟祖冲之量子计算机实现的最大规模采样任务需要$ 5.76\times10^{17} $核时, 而用相同算法模拟在Sycamore上实现的最大规模采样任务只需要$ 8.90\times10^{13} $核时; 用更高效的张量网络模拟方法, 模拟Sycamore最大任务需要15.9天, 而模拟祖冲之最大任务需要8.2年. 取决于使用的经典计算算法, 祖冲之量子计算机实现的最大规模采样任务对应的经典计算资源大概是Sycamore实现的最大规模采样任务对应的经典计算资源消耗2—3个数量级.
2021年9月, 潘建伟团队又在祖冲之2.0的基础上升级到了祖冲之2.1. 祖冲之2.1相对于祖冲之2.0的主要提升是将平均读出精度从95.48%提升到了97.74%, 因此可以在祖冲之2.1上实现更大规模的、量子比特数为60、线路深度为24层的随机量子线路. 这一采样任务在经典计算机上实现的复杂度比Sycamore实现的最难的采样任务高6个数量级, 比祖冲之2.0上实现的最难的采样任务高3个数量级^[18].
量子计算机和经典算法都在发展, 要从实验上验证量子优越性不是一个一蹴而就的事情, 需要不断地提高量子计算机的规模和精确度, 得益于量子计算机计算空间上随量子比特数的指数增长, 经典计算机很难模拟更大规模的量子线路.
2 -->

3.2.玻色采样的实验进展

无论是理想玻色采样还是高斯玻色采样, 其装置都主要由3部分构成: 光子源、干涉仪以及最终的光子探测装置, 而不同的玻色采样在实验装置上的区别仅体现为光子源不同. 潘建伟团队^[53]在理想玻色采样、容许损耗的玻色采样、高斯玻色采样方面均完成了有代表性的实验工作, 下面以他们的方案为例进行介绍.
图 7为理想玻色采样的实现方案, 其光子源使用了一个很高质量的InAs/GaAs量子点单光子源, 可以76 MHz的频率稳定产生单光子. 量子点可以看作是微纳加工制备的一个电子二能级体系, 利用其和谐振微腔的耦合, 光子的自发辐射得到增强, 最终可以实现由外加的脉冲激光光场将体系激发到高能级, 确定性地辐射出单光子, 故也称作on-demand单光子源.
图 7 九章GBS 实验示意图^[53]
Figure7. Illustration of the Jiuzhang GBS experiment^[53].

这些光子通过波导、反射镜与分束器构成的网络, 其中的Pockels Cell在外加电场的作用下可以受控地使光子偏振方向发生旋转, 而分束器将不同偏振的光子分离到不同的路径上, 如此实现了将单个光子源发出的全同光子分为20个一组, 每组同时输入一个$ m = 60 $的干涉仪中, 干涉仪等价于一个非常紧凑的由反射镜和分束器组成的网络, 输出端接入60个独立的超导单光子探测器 (光子探测器为工作在超导态-正常态相变临界点的超导体, 利用相变点附近很小的电磁场变化可以带来很大电阻改变的这一特性, 实现对单光子事件的探测). 事实上, 该实验中在输出端探测到的最多光子数事件为14光子事件, 每小时能收集到约6次这样的采样. 于是, 该装置自然地能够完成对较少光子数的理想玻色采样与较多光子时的容许损耗采样.
大规模高斯玻色采样的实验实现, 即“九章”实验装置, 其干涉仪和探测器部分与前述理想玻色采样装置一致, 而光子源部分, “九章”采用泵浦激光作用于25块非线性晶体PPKTP, 生成25个双模压缩态, 等效于50个单模压缩态, 输入进$ m = 100 $的干涉仪中, 输出端可以测量到的事件平均包含47个光子, 至多记录到76个光子的符合计数.

尽管量子优越性问题是经典计算难的, 但由于目前量子设备的规模和误差等的约束, 经典模拟仍然是非常有必要的一个方向. 一方面, 经典计算机可以给出一个量子设备暂时不能达到的阈值, 另一方面, 经典计算机的模拟也可以用来验证量子设备的可靠性.
2

-->

4.1.随机线路的经典模拟

Google展示量子优越性的实验是在53可用量子比特的量子计算机上进行的最大规模为53量子比特、20层深度的随机量子线路采样, 在200 s内可进行一百万次采样, 采样分布的保真度达到了0.2%, 他们估计这一任务在目前最先进的超级计算机Summit上需要10000年才能完成^[7]. 但这一估算是基于Google团队提出的算法, 有没有更好的经典算法能够把模拟的时间减少到可实现的范围内, 对量子优越性成不成立提出了挑战. 同时, 高效的经典算法本身也可以用于量子模拟, 加速量子模拟器.
模拟量子电路主要有两种方法. 第一种方法存放整个量子态$ \left| {\psi} \right\rangle $并且进行演化, 这种方法被称为Schr?dinger方法^[7], 这种方法的优点是计算复杂度和电路深度$ d $是线性关系, 所以对比特数很少的电路非常有效, 但是它的空间复杂度随着量子比特数是呈指数增长的, 对量子比特数多的电路, 内存会成为一个瓶颈. 目前为止, 用这种方法在超算上实现的最大量子比特数电路的模拟是49个量子比特^[22]. Iboldsymbol提出了一种利用硬盘来进行存储的基于张量网络方法的方案, 以模拟49量子比特27层深度电路的全振幅, 以及56量子比特深度为22层的电路的部分振幅^[19]. 为解决对内存需求过大的问题, Google使用了Schr?dinger-Feynman方法, 这个方法把电路切成两块, 用费曼路径积分把两块连起来, 每一块分别用Schr?dinger方法进行计算, 但是这样势必会增加算法的时间复杂度, 正是基于这个方法才给出了在Summit上需要10000年时间的估计.
第二种方法基于张量网络, 只计算一个比特串或者一小部分比特串的振幅, 量子电路可以被表示为张量网络, 通过张量网络的缩并来计算一个特定比特串的振幅. 可以通过张量网络对应线图的最优树分解来找到张量网络的最佳缩并顺序, 一般而言, 找到图的最佳树分解是一个NP难的问题, 所以经常会用启发式算法来找. 虽然该方法得到的树分解不是最佳, 但也足够好的树分解. 张量网络方法的空间复杂度取决于缩并过程中出现的最大张量的阶数, 而最大张量的阶数与量子电路对应的线图的树宽呈指数关系^[66]. 当电路深度比较浅的时候, 树宽很小, 即使对量子比特数目很大的电路, 张量网络方法也是非常有效的算法. 但是张量网络的计算复杂度经常与电路深度成指数关系. 也可以通过图分解算法等进行针对特定电路的高度优化来寻找张量网络的好的缩并顺序^[67], 这样可以对Sycamore量子线路模拟在Google团队的估计上加速10000倍. 基于这项工作, 对缩并树的主干进行优化之后, 对于20层电路深度的Sycamore电路, 阿里巴巴在和Summit相当的超级计算机上实验, 可以在20天内完成Google团队估计需要10000年的算法^[27]. 最近的一篇基于张量网络的固定一部分比特串的工作, 针对20层深度的Sycamote量子电路, 5天内在60个GPU的小集群上计算出两百万个比特串的振幅^[28].
Li等^[22]在张量网络的基础上通过分析量子随机线路的结构, 开发CZ门的对角性质, 提出了一个新的技术—隐分解, 对于$ 7\times 7 $量子比特的随机线路, 该方法可以多分解额外的7个CZ门且不需要额外的空间, 因此可以将Iboldsymbol提出的通过张量网络的slicing技术求解全振幅经典模拟方法^[19]中的被模拟电路的深度增加8层(如图1中的8种排列模式).
2 -->

4.2.玻色采样的经典模拟

由于玻色采样(及其衍生问题)求一个样本的概率的最大代价在于求解其中的积和式(Hafinan函数、Torontonian函数), 因此对于玻色采样的经典模拟工作主要包括计算一个振幅和进行一次采样. 由于玻色采样的振幅可以显式地写出, 因此求一个振幅相对随机线路采样而言较为容易.
对于采用超级计算机进行单个矩阵积和式/Hafnian/Torontonian的计算, Wu等^[68]在天河二号上比较了两个目前最高效的积和式算法—Ryser算法和BB/FG算法的运行效率, 两者计算单个积和式的复杂度均为$ O(n 2^n) $. 得到单个$ n = 50 $矩阵积和式计算需要天河二号约$ 100\; {\rm{min}} $的结论. 潘建伟团队^[69]通过在神威太湖之光超算上对矩阵的Torontonian函数进行求解对高斯玻色采样的经典计算耗时进行估算.
对于一个样本的采样问题, Clifford和Clifford通过条件概率的思想大大降低了进行一次采样的时间(和计算全振幅相比)^[55]. 具体来讲, 由于玻色采样其概率空间的特殊性, 可以将一个$ n $维的概率分布每一维单独采样, 并计算下一维的条件概率, 即将(7)式的概率分布转化为“第$ k $个光子在第$ r_k $个出口被探测到”, 并将其概率分布表示为

$\begin{split}&p(r_1, r_2, \cdots, r_n)\\= \;&p(r_1) p(r_2|r_1) \cdots p(r_n|r_1, r_2, \cdots, r_{n-1}),\end{split}$

如此, 可以依次对$ n $个光子出口位置进行采样, 通过化简该条件概率函数, 并对以上$ n $个条件概率依次进行采样, 就可以实现经典计算机对玻色采样问题的一次采样的模拟. 注意到这里

$ p(r_k|r_1, \cdots, r_{k-1}) = \frac{p(r_1, \cdots, r_{k})}{r_1, \cdots, r_{k-1}}, $

因此只需要求得所有的边缘概率分布函数, 就可以依次采样得到$r_1, r_2, \cdots, r_n$.
对于玻色采样, 基于以上条件采样的方法及对边缘概率函数的优化方法, Clifford和Clifford^[55]证明了进行一次采样的时间可以和计算常数个积和式的时间相等. 同时, Neville等^[54]通过Metropolis 独立采样方法, 可以得到玻色采样的一次近似采样, 他们可以在普通笔记本上实现30个光子的采样, 在超算上实现50个光子的近似采样. 但对于高斯玻色采样和带阈值的高斯玻色采样, 目前还没有结论证明其采样复杂性可以降低到求解常数个Hafnian函数或是Torontonian函数. 但目前较好的后两者采样算法^{[41,56,57,70]}都是利用了第二种方法中条件概率的思想去降低求解的代价.

近几年来, 量子计算机的规模和精度都得到了极大的提升, 目前世界上最先进的量子计算机已经达到了50—100个量子比特^[17,18,53], 单个门的误差也降低到了0.2%左右^[7,49]. 无论是学术界还是工业界, 对量子计算的热情都急速增长. 未来量子计算的发展, 很大程度上依赖于量子计算机硬件性能的提升与量子算法在物理化学生物等领域的实际应用的探索. 本文所梳理的对采样问题的量子优越性的研究, 旨在找出一些量子计算机相较于经典计算机具有计算能力优势的问题. 尽管当前的采样实验在一定范围内可以被经典模拟, 但随着实验上规模的逐渐增大和设备精度的不断提升, 经典模拟将变得越来越困难. 采样问题的量子优越性研究一方面验证了可控量子系统相较于经典计算更强的操作能力, 另一方面也为下一步解决经典困难问题提供了基础. 随着经典计算机的性能提升与算法的发展, 经典计算机的算力也在提升, 所以如果希望量子计算机能够永远战胜经典计算机, 就必须制备出大型稳定的通用量子计算机, 并且需要对错误具有一定的鲁棒性.
另一方面, 量子系统也在不断增大, 量子实验结果的正确性验证也越来难. 潘建伟团队实现的基于带阈值的高斯玻色采样实验^[53]和随机线路采样实验^[17]在近期内仍未找到可以有效模拟和验证的经典模拟算法. 如何有效验证中等规模量子计算是目前的一个重要研究方向.
与此同时, 找到第一个有足够实际应用价值的超越经典计算机性能的问题, 是整个量子计算领域的重中之重. 由于量子计算机的性能随着规模的增大而指数增长, 以及量子计算机独特的叠加、纠缠等特性, 量子计算机和经典计算机的结合将成为早期应用中最有可能出现的方案. QPU与CPU, GPU, TPU等处理器的结合, 形成高效的异构体系, 并以云平台提供算力, 正在成为工业界积极探索的方向.
值得注意的是, 近期Google团队在Sycamore量子计算机上进行了一系列应用探索. 在优化问题中, 利用量子近似优化算法, 在23个物理量子比特上演示了Sherrington–Kirkpatrick模型和最大割问题的量子版本算法^[71]. 量子化学方面, 结合量子变分算法计算了氢链的结合能与二氮烯分子异构化反应的能量跃迁, 计算中最多用到了12个量子比特, 其中6个原子与8个原子的氢链的计算在引入错误抑制方案后, 达到了化学精度^[72]. 另外, 在量子模拟方面, 用16个量子比特模拟了一维Fermi-Hubbard模型的时间演化, 观察到了自旋-电荷分离现象^[73]. 然而遗憾的是, 量子计算机上演示的以上实际应用问题并未真正体现出量子计算机相较于经典计算机的优势.
在机器学习领域, 近期也有一些体现量子优越性的量子机器学习方案被提出, 比如Liu等^[74]巧妙地设计了一个基于离散对数问题的学习问题, 并证明了其量子优越性. 具体来说, 该量子机器学习算法的量子分类器是一个传统的支持向量机, 通过使用容错量子计算机来估计核函数. 他们同时证明了在假设离散对数问题是经典困难的情况下, 没有经典的多项式时间的学习算法可以比随机选取更好. 但由于求解离散对数问题的量子算法需要大规模的通用量子计算机, 也许该优越性问题需要一定时间才能真实体现其优势. 对于学习量子态的线性性质问题, Huang等^[75]论述了可以通过量子计算机的纠缠能力, 将多个量子态的拷贝通过量子电路纠缠起来, 从而实现对直接通过经典测量的经典学习算法进行指数加速. 因为该实验需要的量子资源较少, 因此有望在不久的将来在中等规模带噪音等量子(noisy intermediate-scale quantum, NISQ)机器上进行展现.
本文对于量子优越性问题的回顾和探索在这里将告一段落, 但科学界对量子优越性的探索远不止以上这些问题. 随着工业界和高校在量子设备规模上的里程碑进展, 未来能够在量子设备上展现出优越性的问题将会越来越多.