量子计算的方法和相关装置与流程

1.本技术涉及量子计算领域，并且更具体地，涉及一种量子计算的方法和相关装置。

背景技术：

2.量子近似优化算法(quantum approximate optimization algorithm，qaoa)，在解决一些限制条件比较稀疏的大规模问题时(如解决所有点的度都为3的最大割问题)，在浅层量子线路就可以取得一定的效果。但是对于大体系的问题，太浅层的量子线路不会有太好的效果。提高量子线路的层数，qaoa会有更好的表现，但是qaoa算法在现有中等规模带噪声的(noisy intermediate scale quantum，nisq)量子计算机上运行会受到噪声的影响，过深层的量子线路可能会导致噪声带来的影响大于或抵消深度带来的好处，反而使得整体效果变得更差，最终结果可能深层线路结果还不如浅层线路。因此，亟需对qaoa 进行改进，以适用于解决更多的问题。

技术实现要素：

3.本技术提供一种量子计算的方法和相关装置，可以提升qaoa在浅层线路下的表现，还可以适用于在浅层线路下解决更多的问题。
4.第一方面，提供了一种量子计算的方法。该方法可以包括：构建量子近似优化算法 qaoa量子系统中的n个量子比特的初始量子态，初始量子态包括可调参数，n为大于1 的整数；将计算问题编码为qaoa量子系统的问题哈密顿量；将qaoa量子系统从初始哈密顿量向问题哈密顿量的基态演化；测量n个量子比特的至少一部分以获得qaoa量子系统的读出，并从读出确定计算问题的解决方案。
5.基于上述技术方案，初始量子态中包括可调参数，通过该可调参数可以实现初始量子态可调控。例如，在将qaoa量子系统从初始哈密顿量向问题哈密顿量的基态演化过程中，每次迭代都可以通过调整该可调参数来调控初始量子态。例如，可以根据每次迭代的实际情况，确定该可调参数，从而确定本次迭代的初始量子态；或者也可以根据上一次的迭代结果来确定该可调参数，从而确定本次迭代的初始量子态，等等。由于初始量子态是可调控的，且在某些情况下是可迭代的(如将前一次的优化结果作为下一次优化开始的初始量子态而形成迭代)，这样可以保证量子态的演化可以不完全交给量子线路来实现，也可以通过迭代初始量子态的方式来实现，从而不仅可以提升qaoa在浅层线路下的表现，还可以适用于解决更多的问题。
6.结合第一方面，在第一方面的某些实现方式中，构建qaoa量子系统中的n个量子比特的初始量子态，包括：通过旋转门构建qaoa量子系统中的n个量子比特的初始量子态，可调参数为旋转门的旋转角度。
7.基于上述技术方案，可调参数例如可以为旋转门的旋转角度，不仅可以实现初始量子态可调控，而且简单易实现。
8.结合第一方面，在第一方面的某些实现方式中，旋转门为ry旋转门或r
x
旋转门。
9.结合第一方面，在第一方面的某些实现方式中，初始量子态表示为：
10.|ψ
initial
》＝∏
iry
(θi)|0》i，或者，|ψ
initial
》＝∏
iry
(θi)|1》i11.其中，|ψ
initial
》表示初始量子态，θi表示可调参数。
12.结合第一方面，在第一方面的某些实现方式中，将qaoa量子系统从初始哈密顿量向问题哈密顿量的基态演化，包括：获取待优化参数以及优化次数k，k为大于1的整数；将qaoa量子系统从初始哈密顿量开始，对待优化参数优化k次，得到问题哈密顿量的基态，其中，本次优化对应的可调参数的取值是根据前一次的优化结果确定的。
13.基于上述技术方案，可以将前一次的优化结果作为下一次优化开始的初始量子态而形成迭代，这样通过采用迭代式更新初始量子态的方法进行演化，可以实现在不增加甚至降低求期望次数的情况下，得到精度非常高的结果。
14.结合第一方面，在第一方面的某些实现方式中，将qaoa量子系统从初始哈密顿量向问题哈密顿量的基态演化，包括：获取待优化参数以及优化次数k，k为大于1的整数；将qaoa量子系统从初始哈密顿量开始，对待优化参数优化k次，得到问题哈密顿量的基态，其中，待优化参数在本次优化的初始值为前一次优化结束时待优化参数的取值。
15.基于上述技术方案，待优化参数在本次优化的初始值为前一次优化结束时待优化参数的取值，迭代过程中对用于优化待优化参数的优化器的要求不高，也不需要每次迭代都进行优化，因此在达到同样效果情况下，可以省更多的计算资源。
16.结合第一方面，在第一方面的某些实现方式中，在前两次优化对应的成本函数之间的差值大于或等于预设阈值的情况下，待优化参数在本次优化的初始值为前一次优化结束时待优化参数的取值。
17.结合第一方面，在第一方面的某些实现方式中，初始哈密顿量为初始量子态对应的哈密顿量，初始哈密顿量表示为：
[0018][0019]
其中，hb表示初始哈密顿量，θi表示可调参数。
[0020]
第二方面，提供了一种量子计算装置。该装置可以包括：构建模块，用于构建量子近似优化算法qaoa量子系统中的n个量子比特的初始量子态，初始量子态包括可调参数， n为大于9的整数；编码模块，用于将计算问题编码为qaoa量子系统的问题哈密顿量；演化模块，用于将qaoa量子系统从初始哈密顿量向问题哈密顿量的基态演化；测量模块，用于测量n个量子比特的至少一部分以获得qaoa量子系统的读出，并从读出确定计算问题的解决方案。
[0021]
结合第二方面，在第二方面的某些实现方式中，构建模块，具体用于通过旋转门构建 qaoa量子系统中的n个量子比特的初始量子态，可调参数为旋转门的旋转角度。
[0022]
结合第二方面，在第二方面的某些实现方式中，旋转门为ry旋转门或r
x
旋转门。
[0023]
结合第二方面，在第二方面的某些实现方式中，初始量子态表示为：
[0024]
|ψ
initial
》＝∏
iry
(θi)|0》i，或者，|ψ
initial
》＝∏
iry
(θi)|1》i[0025]
其中，|ψ
initial
》表示初始量子态，θi表示可调参数。
[0026]
结合第二方面，在第二方面的某些实现方式中，装置还包括获取模块，获取模块，用于获取待优化参数以及优化次数k，k为大于1的整数；演化模块，具体用于将qaoa量子系
统从初始哈密顿量开始，对待优化参数优化k次，得到问题哈密顿量的基态，其中，本次优化对应的可调参数的取值是根据前一次的优化结果确定的。
[0027]
结合第二方面，在第二方面的某些实现方式中，装置还包括获取模块，获取模块，用于获取待优化参数以及优化次数k，k为大于1的整数；演化模块，具体用于将qaoa量子系统从初始哈密顿量开始，对待优化参数优化k次，得到问题哈密顿量的基态，其中，待优化参数在本次优化的初始值为前一次优化结束时待优化参数的取值。
[0028]
结合第二方面，在第二方面的某些实现方式中，在前两次优化对应的成本函数之间的差值大于或等于预设阈值的情况下，待优化参数在本次优化的初始值为前一次优化结束时待优化参数的取值。
[0029]
结合第二方面，在第二方面的某些实现方式中，初始哈密顿量为初始量子态对应的哈密顿量，初始哈密顿量表示为：
[0030][0031]
其中，hb表示初始哈密顿量，θi表示可调参数。
[0032]
第三方面，提供了一种量子计算机，该量子计算机可以用于执行上述第一方面提供的方法。
[0033]
可选地，该量子计算机包括量子比特线路(或者说量子比特电路)和量子比特的控制设备，量子比特的控制设备用于在量子比特线路(或者说量子比特电路)上操作。
[0034]
第四方面，提供了一种处理器，用于执行上述第一方面提供的方法。在执行这些方法的过程中，上述方法中有关获取信息或参数的过程，可以理解为处理器接收输入的上述信息或参数的过程。对于处理器所涉及的获取等操作，如果没有特殊说明，或者，如果未与其在相关描述中的实际作用或者内在逻辑相抵触，则均可以更加一般性的理解为处理器输入等操作。
[0035]
在实现过程中，上述处理器可以是专门用于执行这些方法的处理器，也可以是执行存储器中的计算机指令来执行这些方法的处理器，例如通用处理器。上述存储器可以为非瞬时性(non-transitory)存储器，例如只读存储器(read only memory，rom)，其可以与处理器集成在同一块芯片上，也可以分别设置在不同的芯片上，本技术实施例对存储器的类型以及存储器与处理器的设置方式不做限定。
[0036]
第五方面，提供一种计算机可读存储介质，该计算机可读介质存储用于设备执行的程序代码，该程序代码包括用于执行上述第一方面提供的方法。
[0037]
第六方面，提供一种包含指令的计算机程序产品，当该计算机程序产品在计算机上运行时，使得计算机执行上述第一方面提供的方法。
[0038]
第七方面，提供一种芯片，所述芯片包括处理器与接口，所述处理器通过所述接口读取存储器上存储的指令，执行上述第一方面提供的方法。
[0039]
可选地，作为一种实现方式，所述芯片还可以包括存储器，所述存储器中存储有指令，所述处理器用于执行所述存储器上存储的指令，当所述指令被执行时，所述处理器用于执行上述第一方面提供的方法。
[0040]
第八方面，提供一种系统，包括量子计算机和经典计算机。
附图说明
[0041]
图1是根据本技术实施例提出的方法的示意性框图。
[0042]
图2示出了适用于本技术实施例的gqaoa量子系统的一示意图。
[0043]
图3示出了适用于方案1的量子线路图的示意图。
[0044]
图4示出了适用于方案2的量子线路图的示意图。
[0045]
图5示出了20个点度为3的正则图的示意图。
[0046]
图6示出了采用不同方法解决度为3的正则图的最大割问题的示意图。
[0047]
图7示出了层数p＝1和p＝2时，δe随迭代次数变化的示意图。
[0048]
图8示出了参数(β，γ)在迭代过程中的变化趋势。
[0049]
图9示出了对参数(β，γ)进行固定步数的优化时δe随迭代次数变化的示意图。
[0050]
图10示出了采用方案2解决4～20个点的度为3的正则图的权重最大割问题的仿真结果的示意图。
[0051]
图11示出了适用于本技术实施例的一般图的一示意图。
[0052]
图12示出了采用方案2解决如图11所示的一般图的最大割问题的仿真结果的示意图。
[0053]
图13示出了采用方案2解决4～20个点的度为3的正则图的2-sat问题的仿真结果的示意图。
[0054]
图14示出了采用方案2解决4～20个点的度为3的正则图的最大独立集问题的仿真结果的示意图。
[0055]
图15示出了采用方案2解决5座城市的旅行商问题的仿真结果的示意图。
[0056]
图16示出了适用于本技术实施例的装置的示意性框图。
[0057]
图17示出了适用于本技术实施例的装置的示意性结构图。
[0058]
图18示出了适用于本技术实施例的系统的示意图。
具体实施方式
[0059]
下面将结合附图，对本技术中的技术方案进行描述。
[0060]
量子计算，是一门融合了多学科的交叉型学科，如融合了物理学、信息学、计算机学等学科。为了便于理解，首先对量子计算的相关概念进行简单的介绍。
[0061]
1、量子计算：基于量子逻辑的计算方式，量子计算的基本运算单位是量子比特(qubit)。
[0062]
2、量子比特：量子计算的基本运算单位。量子比特线路是为模拟物理中量子的能级系统创造的硬件系统。经典比特在经典计算机中以非0即1的形式存在，分别对应着低电平与高电平，经典比特同一时间表示一种状态。区别于经典比特，量子比特是以几率的形式存在的，在某一时间，它可以有cos2(θ)的概率存在于0态，以sin2(θ)的概率存在于1 态，在没有测量之前，可以认为一个量子比特“同时”表示出了0态和1态，测量之后，量子比特会塌缩到某一个确定的态上。作为示例，一个量子比特可以用公式1表示。
[0063]
|qubit》＝cos(θ)|0》+sin(θ)|1》
[0064]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
公式1
[0065]
其中，|》为狄拉克符号。
(satisfiability problem)、旅行商问题(traveling salesman problem，tsp)，等等。在面对大规模无特征或者特征不明显的组合优化问题时，经典算法的效果更加趋近于随机数生成器，qaoa则可以保证在不用设置太多待优化参数与构建深层量子线路的前提条件下，得到正确解。下面主要介绍qaoa。
[0081]
8、qaoa：构建思路是构建一个大的解域，然后通过哈密顿量的演化将解域中满足要求的解的概率或者说振幅放大，进而更容易获得正确解。
[0082]
qaoa，可以近似理解为量子退火算法(quantum annealing algorithm，qaa)的离散版本和变分版本的复合体。其将一个绝热含时演化算符exp(-ith(t))根据trotter分解，可以转为离散的基于量子门的演化，如公式2。
[0083][0084]
进一步，可以定义，其中，可调参数表示复数矩阵的矩阵指数。
[0085]
应理解，是整体的哈密顿算子,在演化结束时刻ti达到h
p
， h
p
表示待求解问题的hamiltonian。
[0086]
理论上可以证明，当分割的时间段足够小，该方法可以近似绝热算法。考虑到量子线路深度有限，目前主要采用量子经典混合计算实现，即将问题的部分复杂度交给经典计算机来完成。具体地，包括如下步骤。
[0087]
步骤1，在量子计算机上构建bell态|+》n＝|++...+》为初态。以单个量子比特说明，单个量子比特的逻辑状态可能处于|0》态、|1》态、|0》态和|1》态的叠加态(不确定状态)，|+》表示bell基，
[0088]
步骤2，交叉施加uc和ub量子门操作，直到达到设定深度p。
[0089]
步骤3，测量在此量子态下的期望值，得到cost function＝《ψ'
p
|h
p
|ψ'
p
》。其中， cost function表示成本函数。
[0090]
步骤4，根据测量期望值，反馈给经典计算机。经典计算机根据经典优化器(即经典计算机的优化器)，优化更新参数(β，γ)。其中，β＝[β1，β2，
……
，β
p
]、γ＝[γ1，γ2，
……
，γ
p
]。重复步骤1至步骤4，直至收敛或达到最大迭代次数，然后退出。
[0091]
上述关于量子经典混合计算的步骤仅是简单的示例说明，对此不作限定。简单来说，量子经典混合计算，即为一种内层利用量子线路进行计算，外层用传统的经典优化器调节变分量子线路参数的计算范式。
[0092]
qaoa是一种特定的量子线路结构假设，通过这样的量子线路产生的量子态可以用来近似非确定性多项式(non-deterministic polynomial，np)完全的组合数学优化问题的
结果，属于典型的量子经典混合计算范式。qaoa在解决一些限制条件比较“稀疏”的大规模问题时(如解决所有点的度都为3的最大割问题)，因为其条件可以拆散，所以qaoa 在浅层量子线路(p比较低时)，用很少的参数就可以取得一定的效果。满足某种条件， qaoa在浅层线路中的表现可能不会受到限制，然而在实际的模拟中，这会为优化器带来巨大的压力，往往一次优化难以得到最优值，对大的体系往往需要对优化后的参数进行扰动后再优化几次才可以得到一个相对比较好的值。
[0093]
对于大体系的问题，qaoa在浅层量子线路不会有太好的效果。vqe又因为其如果想得到比较好的结果，必须要使用特别多的参数，这就对经典计算机的优化器提出了非常大的挑战。对于变分算法来说，如果想要提升算法的表现，变分算法的量子线路需要提升层数，这对量子线路制备的可靠性提出巨大的挑战，现阶段很难满足；同时参数也会随着层数的变多而变多，在变分优化框架下，优化器可能会遇到梯度消失等情况，进而可能收敛到局部次优值。提高量子线路的层数，qaoa可能会有更好的表现，但是在当前量子计算硬件依旧处在一个不成熟的条件下，过深的量子线路也许会导致噪声带来的影响大于或抵消深度带来的好处，反而使得整体效果变得更差，最终结果可能深层线路结果还不如浅层线路的。
[0094]
有鉴于此，本技术实施例提出一种方案，主要对量子比特的初始量子态及其对应的初始哈密顿量(如记为hb)进行改进，以拓展原有的qaoa，使得可以提升qaoa在浅层线路下的表现，还可以适用于在浅层线路下解决更多的问题。
[0095]
本技术实施例提供的方法可以用于电子设备，如计算机终端，具体如普通电脑、量子计算机等；或者也可以应用于一些模拟平台，如量子软件模拟平台，具体如projectq或 hiq。可以理解，本技术实施例所能应用的系统架构和场景，可以适用于所有可以使用 qaoa算法的系统，比如中等规模带噪声的(noisy intermediate scale quantum，nisq)量子计算机(nisq量子计算机)。
[0096]
下面将结合附图详细说明本技术提供的各个实施例。
[0097]
图1是本技术实施例提供的一种量子计算的方法100的示意性框图。方法100可以包括如下步骤。
[0098]
110，构建qaoa量子系统中的n个量子比特的初始量子态，初始量子态包括可调参数，n为大于1的整数；
[0099]
120，将计算问题编码为qaoa量子系统的问题哈密顿量；
[0100]
130，将qaoa量子系统从初始哈密顿量向问题哈密顿量的基态演化；
[0101]
140，测量n个量子比特的至少一部分以获得qaoa量子系统的读出，并从读出确定计算问题的解决方案。
[0102]
量子系统的目标量子态可以是将特定的量子电路应用于量子系统的初始量子态的结果的量子状态。例如，目标量子态可以对应于hamiltonian的基态(ground state)。特定的量子电路表示hamiltonian下的量子系统的整体演化。
[0103]
在本技术实施例中，初始量子态是可调控的，且是可迭代的，这样可以保证量子态的演化可以不完全交给量子线路来实现，也可以通过迭代初始量子态的方式来实现。
[0104]
初始量子态包括可调参数，那么在每次迭代时，可以通过该可调参数确定每次迭代的初始量子态，使得初始量子态是可调控的。
[0105]
关于初始量子态的构建方式，至少包括以下几种实现方式。
[0106]
实现方式1，使用旋转门来构建初始量子态。基于该实现方式，可调参数例如可以为旋转门的旋转角度。
[0107]
实现方式2，当问题中某两个量子比特存在关联，那么可以使用一些含参的双比特门在初始量子态中构建这种关系，用参数来调控这种关系的强弱。基于该实现方式，可调参数例如可以为含参的双比特门。
[0108]
实现方式3，使用多比特门来构建初始量子态。例如，对于一些使用到了多比特信息的初始量子态，如使用到了d能级量子比特(qudit)，那么可以为每个qudit构造一个门 u(θ)来控制一个qudit的表达。基于该实现方式，可调参数例如可以为θ。其中，关于qudit 和qubit可以参考现有的描述，例如qubit表示二能级量子比特，qudit表示d能级量子比特，也就是所说的多能级情况。
[0109]
应理解，上述几种实现方式进行示例性说明，对此不作限定。任何可以使得初始量子态可调的方式，都适用于本技术实施例。例如，可以参考vqe对量子态的构建方式，构建初始量子态等等。
[0110]
下面，主要介绍上述的实现方式1。
[0111]
实现方式1，使用旋转门来构建初始量子态。
[0112]
一种可能的实现方式，使用ry旋转门来构建初始量子态。
[0113]
在构建每个量子比特的初始量子态时，采用y轴旋转门ry(θi)来使初始量子态 |0》＝[1,0]
t
绕布洛赫球中的y轴旋转一个角θi，这样对于n个量子比特，通过一组θ＝(θ1,θ2,......,θi,......θn)来构建初始量子态。其中，n个量子比特对应的θi，可以随机取值也可以按照一定的规律取值(如在(0，π)之间等间隔取值)，或者也可以是其他方式，对此不作限定。初始化时，n个量子比特对应的θi可以各不相同。与现有qaoa相比，在该实现方式中，通过将制备初始量子态的哈达玛(hadamard)门替换为了ry旋转门，从而可以精密调控每个量子比特的叠加分布。
[0114]
示例地，可以将前一次的优化结果作为下一次优化开始的初始量子态而形成迭代。也就是说，可调参数ry旋转门的旋转角度，可以根据前一次的优化结果确定下一次优化开始的初始量子态。例如，可以将每个量子比特的0-1态分布测量出来转化为ry旋转门的旋转角度θ，进而将前一次的优化结果作为下一次优化开始的初始量子态而形成迭代。这样通过采用迭代式更新初始量子态的方法进行演化，可以实现在不增加甚至降低求期望次数的情况下，得到精度非常高的结果。
[0115]
应理解，本技术实施例主要以采用ry旋转门来构建初始量子态为例进行示例性说明，对此不作限定，例如，可以使用不同的门构造可迭代的初始量子态，如r
x
(θ)门或者任意的类似(ry(θ)
·rx
(θ'))的单比特旋转门均可。
[0116]
可选地，可以选择与初始量子态相关的初始哈密顿量hb。
[0117]
一种可能的实现方式，hb为初始量子态的哈密顿量，或者说hb对应的本征矢量跟制备的初始量子态有很大的重叠度。
[0118]
以上述采用ry旋转门来构建初始量子态为例，ry(θi)旋转过后，在布洛赫球中实际上是落到了xz平面内，对应的矢量是[cos(θi),sin(θi)]，构建对应的本征哈密顿量hb如公式3。
[0119][0120]
上文分别描述了初始量子态和初始哈密顿量hb。下面结合图2介绍适用于本技术实施例的量子系统，为区分，将本技术实施例提出的qaoa衍生算法记为gqaoa。
[0121]
图2示出了适用于本技术实施例的gqaoa量子系统的一示意图。
[0122]
如图2所示，gqaoa量子系统可以包括变分参数模块，该变分参数模块类似于qaoa 量子系统中的变分参数模块。例如，变分参数模块包括第一参数模块和第二参数模块，如图2所示的和r
x,b
。其中，γ，β为变分参数，γ∈[0，π]，β∈[0，π]。表示复数矩阵-iγhc的矩阵指数。经过gqaoa量子系统中的变分参数模块，gqaoa量子系统的输出状态可以表示为：|ψ(β,γ,p)|。其中，p表示量子线路的层数。将gqaoa量子系统的输出状态代入量子优化问题，可以得到量子优化问题的目标函数，目标函数例如可以为损失函数(loss function)。一种可能的实现方式，gqaoa量子系统的经典部分，如可以利用变分法或者基于梯度的优化算法(例如，随机梯度算法或者adam)来优化迭代目标函数里面的参数向量β和参数向量γ，并将优化后的参向量反馈输入到gqaoa量子系统。通过优化迭代，直到满足最优条件或者达到预设的参数阈值，并且将优化后的参数向量记为β*和γ*。最终gqaoa量子系统输出接近量子优化问题的最优解的状态以及相应的近似目标值。关于变分参数模块，可以参考现有qaoa量子系统中的变分参数模块，此处不再赘述。
[0123]
如图2所示，gqaoa量子系统可以包括初始量子态，如记为如前所述，在本技术实施例中，初始量子态是可调控的，也就是说，初始量子态中的θ是可调的。
[0124]
以使用ry旋转门来构建初始量子态为例，本技术实施例提供两种优化方案，为区分，记为方案1和方案2。下面介绍这两种方案。
[0125]
方案1
[0126]
方案1可以包括如下步骤。
[0127]
1)设定优化次数k，k为大于1或等于1的整数。
[0128]
在计算中，可以按照设定的优化次数k优化k次。
[0129]
2)确定待优化参数的初始值：θ＝(θ1,θ2,......,θi,......θn)，β＝(β1,β2,......,βi,
……
β
p
)，γ＝(γ1,γ2,......,γi,
……
γ
p
)。可以看出，在本技术实施例中，待优化参数不仅包括变分参数γ，β，还包括可调参数θ。
[0130]
3)用θ与n个y轴旋转门ry(θi)，从|0》态构建初始量子态和hb。
[0131]
构建的hb如公式3所示。构建的初始量子态，例如可以表示为公式4。
[0132][0133]
4)根据问题构建问题哈密顿量，如记为h
p
。设定层数p，第i层的演化模块u
b，i
(θ,βi)、 u
p,i
(γi)，其中，βi∈(β1,β2,......,βi,......β
p
)，γi∈(γ1,γ2,......,γi,......γ
p
)，θ＝(θ1,θ2,......,θi,......θn)。
[0134]
作为示例，图3示出了适用于方案1的量子线路图。如图3所示，在p层线路中，每一层都包括演化模块ub(θ,β)和u
p
(γ)。
[0135]
5)按照优化次数k，优化k次。
[0136]
在本示例的计算中，参数的个数为(n+2p)，考虑到一次优化可能不足以优化到最优值，一种可能的实现方式，可以设置具体的优化次数k(例如k大于1)，按照优化次数 k优化k次。示例地，每次优化的参数的初始值为上次参数优化结束的终值。
[0137]
优化k次后，得到最终的优化值(θ'，β'，γ')。通过(θ'，β'，γ')重新按照量子线路进行构建，测量就会得到最终态。
[0138]
上文介绍了方案1，下面介绍方案2。
[0139]
方案2
[0140]
方案2可以包括如下步骤。
[0141]
1)设定优化次数k。
[0142]
2)给出一组数值不同的θ＝(θ1,θ2,......,θi,......θn)。例如，可以是随机确定的一组数值；或者也可以是按照某种规律取值，如在(0,π)之间等间隔取值，等等，对此不作限定。
[0143]
3)用θ与n个y轴旋转门ry(θi)，从|0》态构建初始量子态和hb。构建的hb如公式 3所示。构建的初始量子态，例如可以表示为公式4。
[0144]
4)根据问题构建问题哈密顿量h
p
。设定层数p，构建出第i层的演化模块u
b，i
(θ，βi)、 u
p，i
(γi)，其中，βi∈(β1，β2，......，βi，......β
p
)，γi∈(γ1，γ2，......，γi，......γ
p
)，θ＝(θ1，θ2，......，θi，......θn)。
[0145]
作为示例，图4示出了适用于方案2的量子线路图。如图4所示，在p层线路中，每一层都包括演化模块u
b，i
(θ，βi)和u
p，i
(γi)。
[0146]
5)确定(β
′
，γ
′
)。
[0147]
第一种可能的实现方式，可以使用经典计算机优化器优化参数β＝(β1，β2，......β
p
)，γ＝(γ1，γ2，......γ
p
)，得到优化后的参数(β
′
，γ
′
)。如根据成本函数(如 cost function＝《ψ
′
p
|h
p
|ψ
′
p
》)与初始量子态|ψ
initial
》，使用经典计算机优化器优化参数，得到优化后的参数(β
′
，γ
′
)。
[0148]
第二种可能的实现方式，(β
′
，γ
′
)为取上一次的(β，γ)。也就是说，取上一次的(β，γ) 赋值给(β
′
，γ
′
)。
[0149]
可选地，可以根据迭代数或者迭代结果选择使用上述哪一种实现方式确定(β
′
，γ)。
[0150]
例如，在迭代数为1(如k＝1)，可以使用上述第一种可能的实现方式确定(β
′
，γ
′
)，即使用经典计算机优化器优化参数β，γ；在迭代数大于1，可以使用上述第二种可能的实现方式确定(β
′
，γ)，即取上一次的(β，γ)赋值给(β
′
，γ
′
)。
[0151]
又如，本次与前一次的迭代结果相差小于预设阈值δ的情况下，可以使用上述第一种可能的实现方式确定(β
′
，γ
′
)，即使用经典计算机优化器优化参数β，γ；在本次与前一次的迭代结果相差大于或等于预设阈值δ的情况下，可以使用上述第二种可能的实现方式确定 (β
′
，γ
′
)，即取上一次的(β，γ)赋值给(β
′
，γ
′
)。
[0152]
6)使用(θ，β’，γ’)，构建出|ψ
′
p
》，对其测量得到每个比特的01概率分布将其转换为θ
′
，如果第i个量子比特取到0的概率为pi，则有θ
′
如公式5。
[0153]
[0154]
根据测量出的每个比特的概率，按照上式得到θ
′
。
[0155]
7)检查迭代次数是否达到设定值k，如果达到，则以最后一次迭代的测量结果为最终结果，如果没有则将(θ，β’，γ’)返回到第2步中，将其赋值给(θ，β，γ)。
[0156]
为清楚，适用于上述示例的伪代码如下。
[0157]
在方案2中，单比特调控参数θ是由迭代测量来调控与更新的，从伪代码可以看出，迭代过程中实际上剩余的参数(β，γ)对优化器的要求不高，也不需要每次迭代都进行优化，因此在达到同样效果情况下，采用方案2可以省更多的计算资源。
[0158]
下面介绍本技术实施例提供的gqaoa在不同类型的问题中的应用。
[0159]
问题1，最大割问题。
[0160]
最大割问题，可以简单的被描述成如下问题：对于一张由点与点相连的边组成的图，将其中的点分成两个点子集：a子集与b子集，如果a子集点与b子集点之间恰有边相连，那么这样的边可以记作一条“割”。最大割问题，即要出包含最大的割的数量的分类方法。
[0161]
下面结合几种不同类型的最大割问题，进行说明。
[0162]
一、4～20个点的度为3正则图的最大割问题。
[0163]
一张图中一个点所连接的边数被称作这个点的度，正则图(regular graph)中所有的点都有相同的度。作为示例，图5示出了20个点度为3的正则图。
[0164]
下面介绍采用本技术实施例来解决4～20个点的度为3正则图的最大割问题的实现方式。
[0165]
一般来讲，求解问题的步骤包括：1)对问题进行编码，构建问题的问题哈密顿量(即 h
p
)；2)目标问题是求解该问题哈密顿量h
p
在特定线路深度下的最优解。在本技术实施例中，可以通过gqaoa求解该问题哈密顿量h
p
在特定线路深度下的最优解。
[0166]
在该问题下的编码及构建问题哈密顿量h
p
：如上所述，在最大割问题中，可以将每个点分为两类。用一个量子比特表示一个点，量子比特的|0》态表示该点属于a子集，|1》态表示该点属于b子集。因此当一条边上两个点分类为(|0》，|1》)或者(|1》，|0》)，则该边可以被记做一条割，反之则不可以。
[0167]
在该问题下，问题哈密顿量h
p
需要计算每种分类方法中的割的数量。在此之前，可以定义一些算符的作用。作为示例，可以定义算符e1、e0，如下公式。
[0168][0169]
e1|0》＝0，e1|1》＝|1》
[0170]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
公式7
[0171]
e0|0》＝|0》，e0|1》＝0
[0172]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
公式8
[0173]
算符e1、e0，也可以记为判断算符，其可以用于判断一个态是否为|1》态或者|0》态。如果对于点i、j之间存在一条边(如记作{i，j})，那么通过下面算符可以判断这条边是否为一条割：
[0174][0175]
可以得出，h
p{i，j}
|0
i0j
》＝0，h
p{i，j}
|1
i1j
》＝0，h
p{i，j}
|1
i0j
》＝|1
i0j
》，h
p{i，j}
|0
i1j
》＝
|0
i1j
》。问题哈密顿量h
p
对图中的每一条边{i，j}∈edge进行判断，如公式10。
[0176][0176][0178]
构建问题的问题哈密顿量h
p
后，可以采用如上文所述的初始量子态的构建方法构建初始量子态，采用如上文所述的初始哈密顿量的构建方法构建初始哈密顿量hb。然后可以根据如方案1或方案2中所述的流程，在量子计算机或者模拟器上求解，直到收敛或者达到终止条件(如达到最大优化次数或迭代次数，或者达到设定阈值，等等)，然后退出循环。
[0179]
作为示例，图6示出了采用不同方法解决度为3的正则图的最大割问题的示意图。
[0180]
如图6所示，假设分别采用qaoa、方案1以及方案2，解决4～20个点的度为3的正则图的最大割问题。方案1中设定的优化次数为10次，方案2中设定的迭代次数为25 次。图6中用到的正则图可以是随机取至少3种不同的正则图进行计算并且将基于不同的正则图计算的结果取平均之后的结果。
[0181]
如图6所示，纵坐标表示《c》/c
min
，横坐标表示图点个数n(n可以取4～20)，曲线图表示《c》/c
min
随图点个数n的变化趋势。《c》/c
min
可以表示为公式11。
[0182][0183]
其中，e
ideal
表示理想成本函数，在此为该图最大割的数量，即正确解对应的成本函数。 e
calculation
表示实际模拟中计算所得的成本函数。《c》/c
min
越高，代表结果越好。从图6中可以看出，对于qaoa来讲，随着层数p的增加，qaoa的表现越来越好。如果只观察《c》/c
min
，随着图点个数n继续增加，《c》/c
min
的值基本保持不变，带来一种似乎解12 个点、20个点、甚至40个点的最大割问题，qaoa在层数p＝3时都会得到一个一样好的解。但是，成本函数的值有时并不能代表算法的直接表现，正确解出现在最终态中的概率(也称成功率)，可以更加准确的描述一个算法的优劣。因此，可以定义δe：
[0184]
δe＝e
ideal-e
calculation
[0185]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
公式12
[0186]
δe越小，说明计算解|ψ
′
p
》与正确解|ψ
ideal
》越接近，算法效果越好。图6中所有点均收敛到了δe＜10-1
，这种情况下对应的成功率(在|ψ
′
p
》中测出正确解的概率)已经高于95％了。
[0187]
对于qaoa来讲，从图6中可以看出，虽然随着图点个数n继续增加，《c》/c
min
的值基本保持不变，但是实际上，随着图点个数n变大，实际最大割的数值e
ideal
也在变大，因此尽管《c》/c
min
的值没有变化，δe的值会不断变大，导致成功率下降。
[0188]
对于本技术实施例提出的gqaoa来讲，可以在一定的迭代次数或者优化次数之后到一个δe＜10-1
的解，不仅在《c》/c
min
的比较中取得极大优势，实际在成功率上也大于 95％。
[0189]
此外，采用本技术实施例提出的gqaoa，不需要计算太多次的成本函数，因此可以消耗更少的计算资源。以本技术实施例提出的方案2为例，如图6所示，以n＝14为例。横坐标对于qaoa来讲可以表示层数p，对于方案2来讲可以表示迭代次数。可以看出，方案2使用一层量子线路(即p＝1)就可以达到qaoa较深层量子线路能达到的效果，极大的减少了构造量子线路的成本。
[0190]
此外，用本技术实施例提出的gqaoa，不需要计算太多次的成本函数，因此可以消耗更少的计算资源。对于成本函数的计算，主要是通过多次测量量子态来计算成本函数，然后取平均值。测量之后，量子态会塌缩，所以无法再使用。为了再次测量，一般需要再次利用量子线路构建这个量子态。所以成本函数的计算会消耗很多资源。用成本函数的计算次数来表示资源的消耗，作为示例，根据模拟经验，表1示出了在20个点度为3的正则图的最大割问题中，采用不同算法(即qaoa、方案1以及方案2)对应的成本函数的计算次数。
[0191]
表1
[0192][0193]
表1中的qaoa列中描述的是：在p＝1～3过程中，将参数(β，γ)优化到最优值所需要的计算次数；方案1列中描述的是：达到优化次数，经验上所需要的计算次数；方案2列中描述的是：达到迭代次数，经验上所需要的计算次数。由表1可以看出，采用方案 2可以节省更多的计算资源。
[0194]
下面，主要以本技术实施例提出的方案2为例，介绍方案2在不同问题中的应用。方案1在不同问题中的应用可以参考方案2在不同问题中的应用，此处不再赘述。
[0195]
可选地，在使用方案2解决问题时，可以通过适当增加量子线路的层数，实现快速收敛。
[0196]
作为示例，图7示出了层数p＝1和p＝2时，δe随迭代次数变化的示意图。假设采用方案2解决20个点的度为3的正则图的最大割问题，设置迭代次数为18，图7示出了δe 在迭代过程中的变化。图7中两个图的不同之处在于，一个图中表示δe的纵坐标采用线性坐标，另一个图中表示δe的纵坐标采用对数坐标。
[0197]
δe越小，说明计算解|ψ
′
p
》与正确解|ψ
ideal
》越接近，算法效果越好。如图7所示，在 p＝1时，大约10次左右迭代，δe就可以趋近于10-1
。比较p＝1和p＝2对应的曲线图，可以看出，对于方案2来说，随着层数p的上升，或者说量子线路深度的增加，达到相同精度所需要的迭代次数会减少。因此，可以通过适当增加量子线路的层数，实现快速收敛。
[0198]
可选地，在使用方案2解决问题时，在迭代过程中，不需要每次都对参数(β，γ)进行优化。
[0199]
一种可能的实现方式，可以根据预设阈值来判断是否需要对参数(β，γ)进行优化。
[0200]
作为示例，图8示出了参数(β，γ)在迭代过程中的变化趋势。假设采用方案2解决20个点的度为3的正则图的最大割问题，设置迭代次数为18。假设每次迭代都对参数(β，γ)进行优化，图8示出了p＝1时参数(β，γ)在迭代过程中的变化，和p＝2时参数(β，γ)在迭代过程中的变化。
[0201]
从图8中可以看出，可以看出，在p＝1或者p＝2时，各个参数的数值基本都在某一个区间内变化，只有少量的点不在区间内。因此，可以通过设计预设阈值δ，来对参数(β，γ)进行固定步数的优化。对参数(β，γ)进行固定步数的优化，可以理解为，不需要每次都对参数(β，γ)进行优化，可以在满足一定的条件下，再对参数(β，γ)进行优化，否则使用前一次所使用的(β，γ)。
[0202]
以第一次和第二次迭代为例，在第一次对参数(β，γ)进行优化，第二次迭代时使用的(β，γ)与第一次使用的(β，γ)相同，求出第二次迭代的成本函数。如果第二次迭代的成本函数相较第一次的变化值小于δ，那么在下次(即第三次)迭代时，可以对参数(β，γ)优化；如果第二次迭代的成本函数相较第一次的变化值大于或等于δ，那么在下次迭代时，可以不对参数(β，γ)优化，仍使用与第一次相同的参数(β，γ)；如果第二次迭代的成本函数相较上次的变化值小于0，则本次迭代作废，直接在本次迭代开始进行参数(β，γ)的优化。
[0203]
应理解，在每次迭代时，都可以使用类似于上述第一次和第二次的方式，判断下次是否需要对参数(β，γ)进行优化。
[0204]
作为示例，图9示出了对参数(β，γ)进行固定步数的优化时δe随迭代次数变化的示意图。
[0205]
比较图9与图7中p＝1的情况，图7所示p＝1时所对应的曲线，是在每轮迭代都对参数(β，γ)进行了优化下的仿真结果；图9所示的曲线，是对参数(β，γ)进行固定步数的优化下的仿真结果。图9中所示的再优化点，可以理解为是在此处对参数(β，γ)进行再优化的点。比较图9与图7可知，对参数(β，γ)进行固定步数的优化，可以实现通过较少的几次优化就可以取得较好的效果的目的。与图7相比，图9中所示的方式可以节省大量的计算资源。如果每次计算成本函数都重复多次的态构建-测量过程，每进行一步优化都计算一次成本函数，那么每次迭代都进行优化与进行固定步数的优化相比，进行固定步数的优化可以大大降低计算成本。
[0206]
通过上述方式，可以看出，对参数(β，γ)的精度要求并不高，因此在选择经典计算机的优化器时，可以有更多的选择，比如，贝叶斯优化器。贝叶斯优化方法可以根据少量的样本对黑盒函数做出预测，相比于一般的趋势预测函数与梯度下降函数在少步数的情况下具有很大的优势。对于对精度要求不高的优化，使用贝叶斯优化方法可以极大的降低运算的成本。
[0207]
二、4～20个点的度为3的权重最大割问题。
[0208]
权重最大割问题，是在最大割问题上为每条边引入一个处于(0,1]的权重，其对应的问题哈密顿量h
p
如公式13。
[0209][0210]
其中，w
i,j
表示边{i,j}的权重。关于各条边的权重，可以根据实际情况确定，或者也可以随机确定，对此不作限定。例如，在下文示例中，可以使用numpy.random.uniform的模块随机给出每条边的权重。
[0211]
确定问题对应的问题哈密顿量h
p
后，后续处理同上述4～20个点的度为3的正则图的最大割问题的处理流程类似，此处不再赘述。
[0212]
由于每条边的权重不同，所以切哪条边、哪条边先切这样的问题就会显得更重要。
以方案2为例，假设层数p＝1，图10示出了采用方案2解决4～20个点的度为3的正则图的权重最大割问题的仿真结果的示意图。
[0213]
迭代终止的条件，可以是达到预设的迭代次数，或者也可以是其他条件，如δe达到一定值。以迭代终止的条件为δe《10-1
为例，即δe达到10-1
时就停止迭代。图10中模拟所用的正则图可以是随机产生的相同的正则图。在本技术实施例中提及的仿真结果中，均可以经过重复多次计算得到的结果，如重复3次计算，图中可以是展示了其中某次的计算结果，对此下文不再赘述。由图10可以看出，随着图点个数n的增大，迭代次数具有上涨的趋势，且上涨的趋势不明显。因此，在面对非常大的权重最大割问题时，采用本技术实施例的方案(如方案2)，可以实现在n的低次幂多项式的步数中达到较高的精度，如实现δe《10-1
的精度。
[0214]
上文结合问题一和问题二中都是关于解决正则图的最大割问题，下面结合问题三，介绍解决一般图的最大割问题的方案。
[0215]
三、一般图的最大割问题。
[0216]
度为3的正则图，因为其度数较低且每个点度数相同，因此在最终考虑问题时，每个点在基本特质上是等价的，搜索会相对容易。对于一般图(即非正则图)，尤其是每个点度不相同且平均度较高的图，更加考验搜索算法的能力。
[0217]
作为示例，图11示出了适用于本技术实施例的一般图的一示意图。
[0218]
如图11所示，四张图各自的平均度都大于4。类似地，首先对问题进行编码，构建问题的问题哈密顿量(即h
p
)。然后可以采用如上文所述的初始量子态的构建方法构建初始量子态，采用如上文所述的初始哈密顿量的构建方法构建初始哈密顿量hb。以采用方案2为例，可以根据如方案2中所述的流程，在量子计算机或者模拟器上求解，直到收敛或者达到迭代终止条件(如达到最大迭代次数或者达到设定阈值)，然后退出循环。以方案2为例，假设层数p＝1，图12示出了采用方案2解决如图11所示的一般图的最大割问题的仿真结果的示意图。如图12所示，纵坐标表示δe，横坐标表示迭代次数，图12 所示的四条曲线分别对应图11所示的四张图((a),(b),(c),(d))的仿真结果。从图12可以看出，采用本技术实施例的方案(如方案2)，可以高效的解决一般图的最大割问题。
[0219]
上文结合问题1介绍了本技术实施例在解决最大割问题的应用。可以看出，本技术实施例的方案应用于解决最大割问题时，不仅可以实现较高的精度，还可以降低一定的计算成本，降低消耗的计算资源。
[0220]
问题2，可满足性问题。
[0221]
可满足性问题，可以简单的被描述成如下问题：对于一系列布尔值与其连接符(与、或、非等)共同组成一个表达式，其中的布尔值排列称之为“句子”，表达式中连接符是固定的，布尔值是可变的。如果对于某个句子在表达式中得到的值为真，那么可以称之为“满足条件”的句子，寻这样句子的问题，称之为可满足性问题。
[0222]
如果表达式的句子要求最长不超过2，那么问题就变成了2-满足性问题(2-sat)。以2-sat为例，对于这样的问题，哈密顿量可以简单给定如下规则：首先明确什么样的句子是满足条件的。示例地，可以结合前面问题1中的图来完成这个定义：每个点都是句子中的一个布尔值，一条边上的两个点可以认为是一个句子中的两个布尔值，可以简单定义，对于句子长度为1时(点)，要求其布尔值为真时，表达式为真；对于句子长度为2时(边)，要求两
个布尔值相等时为真，那么2-sat问题对应的问题哈密顿量h
p
可以如公式14。
[0223][0224]
构建问题的问题哈密顿量h
p
后，可以采用如上文所述的初始量子态的构建方法构建初始量子态，采用如上文所述的初始哈密顿量的构建方法构建初始哈密顿量hb。以采用方案2为例，可以根据如方案2中所述的流程，在量子计算机或者模拟器上求解，直到收敛或者达到迭代终止条件(如达到最大迭代次数或者达到设定阈值)，然后退出循环。以方案2为例，假设层数p＝1，图13示出了采用方案2解决4～20个点的度为3的正则图的 2-sat问题的仿真结果的示意图。从图13可以看出，采用本技术实施例的方案(如方案2)，可以高效的解决可满足性问题。
[0225]
问题3，最大独立集问题。
[0226]
以度为3的正则图为例。如前所述，每张图由点和边构成，所有点构成点集(如记为 node)，所有边构成边集(如记为edge)。如果存在某个点集那么称node' 为node的子点集。如果子点集中任意两点都不构成边，即那么称 node'为独立集。独立集的规模由其中包含的点的数量来评价。最大独立集问题，就是出一张图中最大的独立集。
[0227]
在该问题下的编码及构建问题哈密顿量h
p
：与最大割问题类似，不同之处在于，|0》态代表该点不属于独立集，|1》态代表该点属于独立集。在此具有两个任务：第一，需要输出结果中有多少个点是属于独立集的，也就是说输出有多少个|1》；第二，并非所有态为|1》的点都是符合要求的，因此需要鉴别与|1》相连的点是否都是|0》。
[0228]
作为示例，可以通过公式15完成第一项任务，即确定输出结果中有多少个点是属于独立集的。
[0229][0230]
完成第二项任务需要先明确：对于{i,j}∈edge，需要保证|0
i 0j》、|0
i 1j》、|1
i 0j》都是满足要求的，只有|1
i 1j》是不满足要求的，因此，可以通过公式16完成第二项任务。
[0231][0232]
在实际操作中，可能会出现重复删减的问题，即对于边{i,j}为|1
i 1j》，已经减去之后又有与点i连接的另一条边{i,k}也为|1
i 1k》，这样点i就被减去了两次。因为最优解不会存在一条边两边都为|1》的情况，所以这样的重复重复删减不会影响到最优解。
[0233]
编码及构建问题哈密顿量h
p
后，可以从初始哈密顿量开始向问题哈密顿量h
p
的基态演化。关于初始量子态以及初始哈密顿量hb，可以参考上文的描述，此处不再赘述。
[0234]
假设，已经知道一个最大独立集的解，在这个解的基础上，可以任选一个态为|0s》的点s将其翻转为|1s》。如果有点s与另一个态为|1i》的点i相连，则点s与点i都要从独立集中删去，这样得到的独立集比已知的最大独立集点少，并非最优解；如果点s并不与目前独立集中的任何一个点相连，则说明点s应该属于独立集，这就表示假设中已知的最大独立集并非最大独立集，这违反上述假设。同样可以证明，如果在假设解中有一条边的两个点都为
|0》，那么将其都翻转为|1》，得到的解似乎与假设解结果相同，但这也是不对的，如果存在这样的边，那么说明其中必然有一个点可以属于最大独立集，这又与假设相违背。以此可以外推至所有的情况。
[0235]
相比于qaoa来说，本技术实施例提供的方案可以适用于上述设置。对于qaoa来说，上述设置可能会带来一些问题。因为尽管最优解是正确且唯一的，但是次优解可能会存在上述证明中存在的不合理情况，即所得到的解并非独立集，但是与独立集的最次优解相同，这在问题规模变大时会导致很大的问题。因为对于实际应用时，解得最优解的代价是很大的，比如需要非常多的测量次数或者非常深的线路深度，此时得到一个次优解往往是较优的一个方案。qaoa在面对更大规模的问题时更容易得到次优解，但是如果次优解有可能不是满足“独立集”要求的合理解，这就需要一系列的处理导致计算成本的上升，或者直接更改哈密顿量，这样会进一步增加单层线路的复杂度，成本会很高。
[0236]
以方案2为例，假设层数p＝1，图14示出了采用方案2解决4～20个点的度为3的正则图的最大独立集问题的仿真结果的示意图。图14中一些变化趋势明显的点表示的是重新优化的点。从图14可以看出，采用本技术实施例的方案(如方案2)，可以在比较少的迭代次数下达到δe《10-1
的精度，如前所述，成功率均达到了95％以上，可以高效的到最优解。
[0237]
问题4，旅行商问题。
[0238]
旅行商问题是路径规划问题，在实际生活中有着诸多应用，比如时间表规划，寻最短路径等等。
[0239]
旅行商问题，可以简单的被描述成如下问题：一位以卖货为生的旅行商人要从自己的家城市a出发，前往几个不同的城市去卖货最后回到家中，城市之间有各不相同的距离，那么需要帮助旅行商规划出最短的路径。旅行商问题分为两类，一类是所有城市之间都是连通的，这样旅行商问题就变成了排序问题；另一类是城市之间并不都是相互连通的，那么问题就变成了两个：首先要确定现有的地图上是否存在一个遍历每座城市的圈，即哈密顿圈问题，其次要到这个最短的圈。本技术实施例主要以第一类问题为例进行示例性说明。
[0240]
旅行商问题具有对称性，即从哪里出发是不重要的，只要排序时每座城市的相邻两座城市是相同的，那么方案便是相同的，因此排序时可以选择固定一座城市作为起点，去排列剩下几座城市，从而达到破缺这种对称性的目的。因此，解决n座城市的旅行商问题，可以计算n-1座城市的排序即可。下面，主要以解决n＝5的旅行商问题为例，进行说明。假设5座城市分别记为：0号城市、1号城市、2号城市、3号城市、4号城市。
[0241]
在该问题下的编码及构建问题哈密顿量h
p
：假设起始城市为0号城市，实际对剩余 1～4号城市进行编码即可。假设用量子比特的排序来代表城市的排序，用量子比特的值来代表城市编号，编号时编码采用二进制编码。例如，|00 01 10 11》实际代表的城市排序为： 0、1、2、3、4、0，以此类推。可以看到，此时每两个量子比特代表一座城市，可以把这两个量子比特当做一个qudit，每个qudit所包含的量子比特数目可以记作m，那么可以简单得到，m是log2(n-1)的向上取整。
[0242]
哈密顿量在该问题下具有两个任务。第一项任务，计算整个路程的长度。可以定义一个判断算符，如公式17。
[0243]
[0244]
其中，k表示要判断的比特串的十进制数li是二进制数，有k＝l＝l12
m-1
+l22
m-2
+
…
lm。下标i代表的是第i个qudit，这个判断算符可以判断某一个qudit转换为十进制后是否是想要的k。
[0245]
可以通过公式18计算路程。
[0246][0247]
因为没有对0号城市编码，且0号城市作为起点，后两项计算的就是从0号城市到第一座城市的距离与第n-1座城市到0号城市的距离。
[0248]
通过上式，可以完成路程的计算，即完成第一项任务。
[0249]
第二项任务，防止有不合理的城市出现。在n座城市的旅行商问题里，不合理的城市是指，有一些城市出现了2次及以上或者未出现，因此需要保证这部分哈密顿量在所有城市仅出现一次时最低，这部分可以通过构造一个二次函数来实现，如公式19。
[0250][0251]
其中c是一个设置的常数，通过设置c可以保证最后解收敛到正确解上。
[0252]
对于m《(n-1)的情况，不合理的情况还有第二种就是出现“不存在”的城市。比如，对于计算6座城市的情况，编码的城市有5座，每个qudit的数量是log25的向上取整(即为3)。3个量子比特可以表示8座城市，那么不存在的城市(如6、7、8号城市)在解中就可能会出现。对于此情况，可以通过设置这些城市与其他城市的距离非常大来解决。
[0253]
基于上述分析，构建的n座城市的旅行商问题的问题哈密顿量h
p
如公式20。
[0254]hp
＝h
p,count-h
p,limit
[0255]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
公式20
[0256]
以方案2为例，假设层数p＝1，图15示出了采用方案2解决5座城市的旅行商问题的仿真结果的示意图。如图15所示，纵坐标表示δe，横坐标表示迭代次数，从图15可以看出，采用本技术实施例的方案(如方案2)，可以高效的解决旅行商问题。
[0257]
上文结合问题1至问题4，介绍了本技术实施例在不同问题中的应用。
[0258]
应理解，在上述一些实施例中，以通过ry旋转门构建初始量子态为例进行了示例性说明，对此不作限定。
[0259]
以上结合图1至图15详细说明了本技术的方法，下面结合图16至图18详细说明本技术的装置。应理解，装置实施例的描述与方法实施例的描述相互对应，因此，未详细描述的内容可以参见上文方法实施例，为了简洁，这里不再赘述。
[0260]
图16是本技术实施例提供的装置的示意性框图。该装置1600可以包括构建模块1610，用于构建量子近似优化算法qaoa量子系统中的n个量子比特的初始量子态，初始量子态包括可调参数，n为大于9的整数；编码模块1620，用于将计算问题编码为qaoa量子系统的问题哈密顿量；演化模块1630，用于将qaoa量子系统从初始哈密顿量向问题哈密顿量的基态演化；测量模块1640，用于测量n个量子比特的至少一部分以获得qaoa 量子系统的读出，并从读出确定计算问题的解决方案。
[0261]
一示例，构建模块1610，具体用于通过旋转门构建qaoa量子系统中的n个量子比特
的初始量子态，可调参数为旋转门的旋转角度。
[0262]
又一示例，旋转门为ry旋转门或r
x
旋转门。
[0263]
又一示例，初始量子态表示为：
[0264]
|ψ
initial
》＝∏
iry
(θi)|0》i，或者，|ψ
initial
》＝∏
iry
(θi)|1》i[0265]
其中，|ψ
initial
》表示初始量子态，θi表示可调参数。
[0266]
又一示例，装置还包括获取模块，用于获取待优化参数以及优化次数k，k为大于1 的整数；演化模块1630，具体用于将qaoa量子系统从初始哈密顿量开始，对待优化参数优化k次，得到问题哈密顿量的基态，其中，本次优化对应的可调参数的取值是根据前一次的优化结果确定的。
[0267]
又一示例，装置还包括获取模块，用于获取待优化参数以及优化次数k，k为大于1 的整数；演化模块1630，具体用于将qaoa量子系统从初始哈密顿量开始，对待优化参数优化k次，得到问题哈密顿量的基态，其中，待优化参数在本次优化的初始值为前一次优化结束时待优化参数的取值。
[0268]
又一示例，在前两次优化对应的成本函数之间的差值大于或等于预设阈值的情况下，待优化参数在本次优化的初始值为前一次优化结束时待优化参数的取值。
[0269]
又一示例，初始哈密顿量为初始量子态对应的哈密顿量，初始哈密顿量表示为：
[0270][0271]
其中，hb表示初始哈密顿量，θi表示可调参数。
[0272]
该装置1600可实现对应于根据本技术实施例的方法实施例中的步骤或者流程，该装置1600可以包括用于执行图1中的方法的单元或者说模块。并且，该装置1600中的各单元和上述其他操作和/或功能分别为了实现图1中的法实施例的相应流程。
[0273]
应理解，各单元或者说模块执行上述相应步骤的具体过程在上述方法实施例中已经详细说明，为了简洁，在此不再赘述。
[0274]
还应理解，上述各个单元或模块的划分仅是一种示例性说明，对此不作限定。
[0275]
如图17所示，本技术实施例还提供一种装置1700。该装置1700包括处理器1710。可选地，该装置1700包括的处理器1710为一个或多个。
[0276]
可选地，如图17所示，该装置1700还可以包括存储器1720。可选地，该装置1700 包括的存储器1720可以为一个或多个。处理器1710与存储器1720耦合，存储器1720用于存储计算机程序或指令和/或数据，处理器1710用于执行存储器1720存储的计算机程序或指令和/或数据，使得上文方法实施例中的方法被执行。可选地，该存储器1720可以与该处理器1710集成在一起，或者分离设置。
[0277]
可选地，该装置1700还可以包括输入装置1730和输出装置1740。可选地，该输入装置1730和输出装置1740集成在一起，或者分离设置。输入装置1730，可以用于接收输入的数字或字符信息，以及产生上述方法中涉及到的有关的信号输入，例如从经典计算机输入的待优化参数。输出装置1740可以用于输出结果，或者也可以包括一些显示设备以显示数据或结果等等。
[0278]
可选地，处理器1710、存储器1720、输入装置1730和输出装置1740可以通过总线或者其他方式连接，图17中以通过总线连接为例。
[0279]
应理解，图17仅是一种示例性说明，任何可以实现上述方法的结构，都适用于本技术实施例。
[0280]
本技术实施例还提供一种系统1800。该系统1800例如可以包括量子硬件1810(例如量子处理器，量子计算机等等)。
[0281]
量子硬件1810包括一个或多个量子比特线路1811(或者也可以称为量子比特电路 1811)。量子比特线路1811可以包括被制备到初态，并可以应用量子门对其操作的量子比特。制备初态的方法可以参考上文方法实施例。量子硬件1810中包括的量子比特线路的物理实现类型可以变化。例如，在一些实施方式中，量子硬件1810可包含超导量子比特线路(或超导量子比特线路电路)，例如超导电荷量子比特线路，超导磁通量子比特线路或超导相位量子比特线路。通常，量子比特线路1811可以是频率可调的。
[0282]
可选地，量子硬件1810还可以包括量子比特的控制设备1812。量子比特的控制设备 1812包括被配置为在一个或多个量子比特线路1811上操作的设备。例如，量子比特的控制设备1812可以包括用于实现量子逻辑门的硬件。实际应用中，多个量子比特电路可以组成一个量子电路，多个量子电路可以做在一个芯片上，一个芯片上的多个量子电路可以共用一套控制设备。
[0283]
可选地，该系统1800还可以包括经典处理器1820(例如经典计算机)。系统1800 可以被配置为使用量子硬件1810和经典处理器1820来结合执行量子计算和经典计算，如执行方法实施例中的方法。
[0284]
经典处理器1820可以被配置为执行量子控制的程序。例如，经典处理器1820被配置为构建用于实现各个量子门的控制脉冲。例如，经典处理器1820可以接收指定了特定幺正量子门或多个幺正量子门的序列的数据，例如输入数据。然后经典处理器1820可以设计控制脉冲，该控制脉冲可以由量子比特的控制设备1812生成，并且被施加到一个或多个量子比特线路1811。
[0285]
可选地，经典处理器1820可以包括通用代价函数生成器1821，可用于为对应的量子门或量子门序列定义通用量子控制代价函数。
[0286]
可选地，经典处理器1820可以包括一个或多个优化工具箱1822，优化工具箱在满足约束的同时提供极大化或极小化的功能，例如求解线性编程、二次编程、非线性编程、约束线性最小二乘法、非线性最小二乘法、或非线性方程等等。示例地，优化工具箱1822 可以用于产生上文所述的待优化参数γ，β。
[0287]
简单来说，经典处理器1820可以用于与量子硬件1810配合以便共同解决一些计算问题。
[0288]
应理解，上述图18仅是一种示例性说明，关于量子硬件1810的具体结构，以及系统 1800包括的具体设备，不作严格限定。
[0289]
本技术实施例还提供一种计算机可读存储介质，其上存储有用于实现上述方法实施例中的方法的计算机指令。
[0290]
本技术实施例还提供一种包含指令的计算机程序产品，该指令被计算机执行时使得该计算机实现上述方法实施例中的方法。
[0291]
上述提供的任一种装置中相关内容的解释及有益效果均可参考上文提供的对应的方法实施例，此处不再赘述。
[0292]
应理解，本技术实施例中提及的处理器，例如可以是量子处理器，即量子级计算机处理器。或者也可以是中央处理单元(central processing unit，cpu)，还可以是其他通用处理器、数字信号处理器(digital signal processor，dsp)、专用集成电路(application specific integrated circuit，asic)、现成可编程门阵列(field programmable gate array，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。
[0293]
还应理解，本技术实施例中提及的存储器可以是易失性存储器和/或非易失性存储器。其中，非易失性存储器可以是只读存储器(read-only memory，rom)、可编程只读存储器(programmable rom，prom)、可擦除可编程只读存储器(erasable prom，eprom)、电可擦除可编程只读存储器(electrically eprom，eeprom)或闪存。易失性存储器可以是随机存取存储器(random access memory，ram)。例如，ram可以用作外部高速缓存。作为示例而非限定，ram可以包括如下多种形式：静态随机存取存储器(static ram， sram)、动态随机存取存储器(dynamic ram，dram)、同步动态随机存取存储器 (synchronous dram，sdram)、双倍数据速率同步动态随机存取存储器(double data rate sdram，ddr sdram)、增强型同步动态随机存取存储器(enhanced sdram，esdram)、同步连接动态随机存取存储器(synchlink dram，sldram)和直接内存总线随机存取存储器(direct rambus ram，dr ram)。
[0294]
需要说明的是，当处理器为通用处理器、dsp、asic、fpga或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件时，存储器(存储模块)可以集成在处理器中。
[0295]
还需要说明的是，本文描述的存储器旨在包括但不限于这些和任意其它适合类型的存储器。
[0296]
本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用使用不同方法来实现所描述的功能，但是这种实现不应认为超出本技术的保护范围。
[0297]
在本技术所提供的几个实施例中，应该理解到，所揭露的装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。此外，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。
[0298]
所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元实现本技术提供的方案。
[0299]
另外，在本技术各个实施例中的各功能单元可以集成在一个单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。
[0300]
在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实
现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本技术实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。例如，所述计算机可以是个人计算机，服务器，或者网络设备等。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(dsl)) 或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质(例如，软盘、硬盘、磁带)、光介质(例如，dvd)、或者半导体介质(例如固态硬盘(solid state disk，ssd)等。例如，前述的可用介质可以包括但不限于：u盘、移动硬盘、只读存储器(read-only memory，rom)、随机存取存储器(random access memory，ram)、磁碟或者光盘等各种可以存储程序代码的介质。
[0301]
以上所述，仅为本技术的具体实施方式，但本技术的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本技术揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本技术的保护范围之内。因此，本技术的保护范围应以所述权利要求的保护范围为准。

技术特征：

1.一种量子计算的方法，其特征在于，包括：构建量子近似优化算法qaoa量子系统中的n个量子比特的初始量子态，所述初始量子态包括可调参数，n为大于1的整数；将计算问题编码为所述qaoa量子系统的问题哈密顿量；将所述qaoa量子系统从初始哈密顿量向所述问题哈密顿量的基态演化；测量所述n个量子比特的至少一部分以获得所述qaoa量子系统的读出，并从所述读出确定所述计算问题的解决方案。2.根据权利要求1所述的方法，其特征在于，所述构建qaoa量子系统中的n个量子比特的初始量子态，包括：通过旋转门构建所述qaoa量子系统中的所述n个量子比特的初始量子态，所述可调参数为所述旋转门的旋转角度。3.根据权利要求2所述的方法，其特征在于，所述旋转门为r
y
旋转门或r
x
旋转门。4.根据权利要求2或3所述的方法，其特征在于，所述初始量子态表示为：|ψ
initial
>＝∏
i
r
y
(θ
i
)|0>
i
，或者，|ψ
initial
>＝∏
i
r
y
(θ
i
)|1>
i
其中，|ψ
initial
>表示所述初始量子态，θ
i
表示所述可调参数。5.根据权利要求1至4中任一项所述的方法，其特征在于，所述将所述qaoa量子系统从所述初始哈密顿量向所述问题哈密顿量的基态演化，包括：获取待优化参数以及优化次数k，k为大于1的整数；将所述qaoa量子系统从所述初始哈密顿量开始，对所述待优化参数优化k次，得到所述问题哈密顿量的基态，其中，本次优化对应的所述可调参数的取值是根据前一次的优化结果确定的。6.根据权利要求1至5中任一项所述的方法，其特征在于，所述将所述qaoa量子系统从所述初始哈密顿量向所述问题哈密顿量的基态演化，包括：获取待优化参数以及优化次数k，k为大于1的整数；将所述qaoa量子系统从所述初始哈密顿量开始，对所述待优化参数优化k次，得到所述问题哈密顿量的基态，其中，所述待优化参数在本次优化的初始值为前一次优化结束时所述待优化参数的取值。7.根据权利要求6所述的方法，其特征在于，在前两次优化对应的成本函数之间的差值大于或等于预设阈值的情况下，所述待优化参数在本次优化的初始值为前一次优化结束时所述待优化参数的取值。8.根据权利要求1至7中任一项所述的方法，其特征在于，所述初始哈密顿量为所述初始量子态对应的哈密顿量，所述初始哈密顿量表示为：其中，h
b
表示所述初始哈密顿量，θ
i
表示所述可调参数。9.一种量子计算装置，其特征在于，包括：构建模块，用于构建量子近似优化算法qaoa量子系统中的n个量子比特的初始量子态，所述初始量子态包括可调参数，n为大于9的整数；
编码模块，用于将计算问题编码为所述qaoa量子系统的问题哈密顿量；演化模块，用于将所述qaoa量子系统从初始哈密顿量向所述问题哈密顿量的基态演化；测量模块，用于测量所述n个量子比特的至少一部分以获得所述qaoa量子系统的读出，并从所述读出确定所述计算问题的解决方案。10.根据权利要求9所述的装置，其特征在于，所述构建模块，具体用于通过旋转门构建所述qaoa量子系统中的所述n个量子比特的初始量子态，所述可调参数为所述旋转门的旋转角度。11.根据权利要求10所述的装置，其特征在于，所述旋转门为r
y
旋转门或r
x
旋转门。12.根据权利要求10或11所述的装置，其特征在于，所述初始量子态表示为：|ψ
initial
>＝∏
i
r
y
(θ
i
)|0〉
i
，或者，|ψ
initial
>＝∏
i
r
y
(θ
i
)|1>
i
其中，|ψ
initial
>表示所述初始量子态，θ
i
表示所述可调参数。13.根据权利要求9至12中任一项所述的装置，其特征在于，所述装置还包括获取模块，所述获取模块，用于获取待优化参数以及优化次数k，k为大于1的整数；所述演化模块，具体用于将所述qaoa量子系统从所述初始哈密顿量开始，对所述待优化参数优化k次，得到所述问题哈密顿量的基态，其中，本次优化对应的所述可调参数的取值是根据前一次的优化结果确定的。14.根据权利要求9至13中任一项所述的装置，其特征在于，所述装置还包括获取模块，所述获取模块，用于获取待优化参数以及优化次数k，k为大于1的整数；所述演化模块，具体用于将所述qaoa量子系统从所述初始哈密顿量开始，对所述待优化参数优化k次，得到所述问题哈密顿量的基态，其中，所述待优化参数在本次优化的初始值为前一次优化结束时所述待优化参数的取值。15.根据权利要求14所述的装置，其特征在于，在前两次优化对应的成本函数之间的差值大于或等于预设阈值的情况下，所述待优化参数在本次优化的初始值为前一次优化结束时所述待优化参数的取值。16.根据权利要求9至15中任一项所述的装置，其特征在于，所述初始哈密顿量为所述初始量子态对应的哈密顿量，所述初始哈密顿量表示为：其中，h
b
表示所述初始哈密顿量，θ
i
表示所述可调参数。17.一种量子计算机，其特征在于，包括：量子比特线路和量子比特的控制设备，所述量子比特的控制设备用于在所述量子比特线路上操作，以便实现如权利要求1至8中任意一项所述的方法。18.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序或指令，当所述计算机程序或指令在计算机上运行时，使得所述计算机执行如权利要求1至8中任意一项所述的方法。

技术总结

本申请提供了一种量子计算的方法和相关装置。该方法可以包括：构建量子近似优化算法QAOA量子系统中的n个量子比特的初始量子态，初始量子态包括可调参数，通过该可调参数可调控每次迭代时的初始量子态，n为大于1的整数；将计算问题编码为QAOA量子系统的问题哈密顿量；将QAOA量子系统从初始哈密顿量向问题哈密顿量的基态演化；测量n个量子比特的至少一部分以获得QAOA量子系统的读出，并从读出确定计算问题的解决方案。通过本申请，可以保证量子态的演化可以不完全交给量子线路来实现，也可以通过迭代初始量子态的方式来实现，从而不仅可以提升QAOA在浅层线路下的表现，还可以适用于解决更多的问题。于解决更多的问题。于解决更多的问题。