CN111052122A - 模拟量子电路 - Google Patents

Abstract

一种计算机实现的方法，包括：接收量子电路的数字描述；将所述量子电路的数字描述划分为多个量子子电路，其中所述多个量子子电路中的每个量子子电路包括一个或多个量子门；确定针对所述多个量子子电路的子电路依赖性；根据所述子电路依赖性来模拟所述多个量子子电路，以产生针对所述多个量子子电路中的每个量子子电路的模拟结果，其中所述多个量子子电路中的第一量子子电路和第二量子子电路各自包含被应用于公共量子位的一个或多个门，以及其中所述第一量子子电路和所述第二量子子电路使用纠缠张量指数而被独立地模拟。本文还公开了对应的计算机系统和计算机程序产品。

Description

模拟量子电路

背景技术

本发明一般地涉及量子电路，并且更具体地涉及模拟量子电路。

量子电路直接利用量子力学现象，诸如叠加和使能(enablement)，来处理信息。例如，量子电路可以包括将逻辑函数应用于各种输入的量子门。与对于每个电路元件限于明确状态(例如，0和1)的数字逻辑电路相比，量子电路可以同时表示和处理多个状态(经由叠加)。因此，量子计算可以能够比传统计算更快地解决一些问题，并且还能够解决当前对于传统计算来说太复杂的问题。

尽管量子计算有希望，但是量子电路难以构造、昂贵，并且遭受诸如缩放和量子去相干之类的各种问题。因此，需要能够使用商业上可获得的计算机来模拟相对大的量子电路。此外，还需要将量子计算装置的实际输出与通过针对正在实现的量子电路的模拟所预测的理想行为进行比较，以便评估量子装置能够执行所希望的量子电路的保真度。

发明内容

在本文公开的实施例的一个方面中，一种由一个或多个处理器执行的用于对包括多个量子门的量子电路进行模拟的方法包括：接收所述量子电路的数字描述；将所述量子电路的数字描述划分为多个量子子电路，其中所述多个量子子电路中的每个量子子电路包括一个或多个量子门；确定针对所述多个量子子电路的子电路依赖性；根据所述子电路依赖性对所述多个量子子电路进行模拟，以产生针对所述多个量子子电路中的每个量子子电路的模拟结果，其中所述多个量子子电路中的第一量子子电路和第二量子子电路各自包含被应用于公共量子位的一个或多个门，并且其中第一量子子电路和第二量子子电路使用纠缠张量指数而被独立地模拟。本文还公开了对应的计算机程序产品。

在本文公开的实施例的一个方面中，还公开了一种方法，该方法由一个或多个处理器执行，用于模拟包括多个量子门的量子电路，接收包括多个级的量子电路的数字描述，为每个初始级量子位创建子电路以产生多个子电路，将来自多个级中的一个或多个后续级的连接的非桥接门迭代地添加到多个子电路，直到不再有连接的非桥接门可用为止，选择被连接到多个子电路中的两个或更多个子电路的桥接门，确定是否使两个或更多个子电路纠缠，以及响应于确定使两个或更多个子电路纠缠，将桥接门添加到两个或更多个子电路中的仅一个子电路。本文还公开了对应的计算机程序产品。

在本文公开的实施例的一个方面中，一种由一个或多个处理器执行的用于模拟包括多个量子门的量子电路的方法，包括：接收包括量子门和对应量子位的一组量子子电路的数字描述；向每个量子位和每个非对角酉门的输出分配不同的张量指数；将张量指数变量从每个对角酉门的输入传播到输出；以及使用所分配的张量指数来执行每个量子子电路。本文还公开了对应的计算机程序产品。

附图说明

图1是示出根据本发明的至少一个实施例的量子态的一个示例的图示和相关联的等式；

图2是一组方程，描绘了对应于根据本发明的至少一个实施例的量子位的基矢量的一个示例；

图3是一组方程，描述了根据本发明的至少一个实施例的量子系统的张量表示的两个示例；

图4A是一组示意性符号，图4B是描绘根据本发明的至少一个实施例的量子门的各种示例的一组相应的张量表；

图5是对应于传统上被假设为不可能在当前可用的计算系统上模拟的大量子电路的执行计划；

图6是根据本发明的至少一个实施例的在此用作处理示例的量子电路的示意图以及对应的基于文本的逻辑描述；

图7是描绘根据本发明的至少一个实施例的量子电路模拟方法的一个示例的流程图；

图8A-图8C是描述与模拟图4和图5中描述的各种量子门相关联的张量方程和资源成本的文本图；

图9A-图9E是示出根据本发明的至少一个实施例的划分对模拟量子电路的一个特定示例所需的计算资源的影响的示意图和方程图；

图10是描绘根据本发明的至少一个实施例的量子电路划分方法的一个示例的流程图；

图11A是描绘根据本发明的至少一个实施例的量子电路执行方法的一个示例的流程图；

图11B是描绘了图11A中所描绘的量子电路执行方法的附加细节的流程图；

图12A-图12C是描绘量子电路的一个特定示例的预划分优化的一个示例的示意图；

图13A-图13D是描绘划分和执行量子电路的一个特定示例的四个示例的示意图；

图14是描绘了对应于图5的能够对当前可用的计算系统进行模拟的大量子电路的子电路的电路划分；

图15是描绘了适于执行本文所公开的方法中的一个或多个的计算装置的一个示例的框图。

具体实施方式

从诸如维基百科的公开可用源中提取的以下术语、定义和概念以及发明人的工作知识可以有助于理解本发明，尤其是对于那些不是模拟量子电路领域的技术人员。

量子叠加：由两个或更多个激励同时引起的净响应(例如，在电路元件中)是由每个激励单独引起的响应的总和。在量子系统的情况下，响应是可以是离散状态的线性叠加的量子状态。叠加由此使得量子电路能够同时表示多个状态或结果(例如，0和1的统计混合)。

量子系统：一种呈现量子效应如叠加和纠缠的系统。

量子态：在量子系统中(同时)存在或可用的状态(可能性)。

量子位：一种量子存储单元，其可以同时表示0状态和1状态的统计混合。

量子塌缩：测量量子力学系统的状态的动作，其使得所述系统演变为单个测量状态。在实际的量子力学系统中，测量的动作基本上从值的统计混合中选择单个实现的值。然而，在模拟量子电路中，可以在不破坏底层状态信息的情况下进行测量。

纠缠：在两个量子系统之间存在的效应，其量子力学状态是相互依赖的。例如，测量两个纠缠量子位中的一个的状态将告诉你关于另一个纠缠量子位的状态的信息，因为它们的状态是统计相关的。

量子数据：表示为一个或多个量子态的信息(例如，在诸如量子位的量子电路元件内)。

量子门：量子电路的元件，用于对量子数据执行逻辑或数学函数。图4和图5中示出了量子门的示例。

张量：实值或复数值的k维数组，其中k是张量的秩(rank)或阶数(order)。矩阵是二阶张量，矢量是一阶张量。张量可以用于在量子模拟中表示量子状态。

张量网络：一种对应于一组相互关联的张量方程的有向图。张量网络可以用于表示量子电路，其中图形(graph)中的节点是表示量子电路元件(例如，量子门)的张量，并且图形的边可以指示张量的指数变量。

张量收缩：一种将一系列两个或更多个相互关联的张量合并成单个张量的数学上严格的过程。张量收缩可以或者可以不倍增地增加所得到的张量的大小，这取决于合并张量的指数变量的关系。当量子电路被表示为张量网络时，张量收缩将由一个或多个边连接的两个或更多个节点合并成单个节点。

如本文所使用的，术语“模拟”和“执行”(例如，量子子电路)本质上是同义的，因为(与仅仅是真实的某物的近似的许多模拟相比)本文所公开的量子电路模拟方法产生真实的、计算上有效的结果。如本文所使用的，短语“指数变量”等是指导致访问期望的数据和/或存储器位置的任何类型的存储器寻址或指数(诸如本领域技术人员已知的那些)。

本文公开的至少一些实施例认识到，可以使用比常规假设更少的存储器来模拟量子电路。例如，本文公开的至少一些实施例将表示和模拟包括N个量子位的量子电路所需的存储器从2^N个复数值减少到该量的一部分。

具体地，本文公开的实施例中的至少一些实施例认识到，可以通过在子电路中的两个或更多个子电路中具有纠缠的量子电路元件来将量子电路划分成子电路。本文公开的至少一些实施例还认识到，一些子电路的模拟结果可以以片的形式计算，并且通过这样做，与传统预期相反，可以显著减少模拟整个量子电路所需的工作存储器。本发明的创造性见解之一在于，在量子电路的模拟期间，只要在模拟中达到被应用于量子位的所有剩余量子门都是对角酉门的点，就可以执行这些切片(slicing)操作。在这种情况下，可以引入诸如for循环的迭代构造以在量子位的0/1值上迭代，并且可以使用工作存储器的一半量在切片中执行涉及该量子位的后续张量操作，而不是采用张量切片。

应当注意，在整个说明书中对本文的特征、见解、优点或类似语言的引用并不意味着可以利用本文公开的实施例实现的所有特征和优点应当是本发明的任何单个实施例，或者在本发明的任何单个实施例中。相反，涉及特征和优点的语言被理解为意味着结合实施例描述的特定特征、优点或特性被包括在本发明的至少一个实施例中。因此，在整个说明书中，对特征、优点和类似语言的讨论可以但不一定是指相同的实施例。

此外，本发明的所述特征、见解、优点和特性可以以任何适当的方式组合在一个或多个实施例中。相关领域的技术人员将认识到，可以在没有特定实施例的一个或多个特定特征或优点的情况下实践本发明。在其他情况下，在某些实施例中可以认识到可能不在本发明的所有实施例中存在的附加特征和优点。这些特征和优点将从以下附图、描述和所附权利要求书中变得更加明显，或者可以通过如下文所述的本发明的实践来获知。

图1是示出根据本发明的至少一个实施例的量子态的一个示例的图示和相关联的等式。与其他粒子(诸如原子)结合的粒子(例如电子)被限制为离散(即量子化)的振荡能级，称为量子态。在狄拉克符号(又名左矢-右矢符号)中，这些状态被指定为|0>、|1>、|2>、|3>等，其中|0>对应于已知为基态的最低能级。

量子计算机操纵量子系统的状态以便执行计算并且解决问题。通常，仅使用两个最低能态，这导致被称为量子位的计算和存储单元。由于对单独电子的操纵和访问是有问题的，因此量子计算机的量子位典型地被实施为超导振荡器。示例包括transmon量子位，其是将电容器与超导约瑟夫逊结组合的半导体器件，超导约瑟夫逊结有效地用作非线性电感器并促进电路谐振。

如等式110所示，量子系统的主要振荡状态可以表示为n维矢量空间内的基矢量。量子系统的任意量子状态然后可以表示为这些基矢量与矢量空间中的每个基维度的复数标量乘数α_i的线性组合(即，叠加)。等式120示出了当进行测量时，量子系统塌缩到主要振荡状态之一，其中概率与在测量之前即刻的振荡状态的标量乘数α_i(也称为复振幅，或简称为振幅)的平方幅度成比例。

如方程130所示，特定量子态的时间演变由薛定谔

方程控制。术语H(t)被称为哈密尔顿函数，并且对应于系统中的总能量。它可以由定义标量乘数α_i的线性变换的矩阵来表示。如方程140所示，薛定谔方程的解具有形式|ψ(t)>＝U(t)|ψ(0)>，其中U(t)可以表示为也定义标量乘数α_i的线性变换的酉矩阵。然而，尽管哈密尔顿矩阵对应于量子系统的总能量，但是在薛定谔方程的解中出现的酉矩阵对应于量子系统的时间演化。

等式150显示酉矩阵具有其逆(inverse)等于其复共轭的转置的性质。这个特性反映了量子系统的时间演变是可逆的直到进行测量(即，所进行的任何动作都可以经由反向动作来撤销)的事实。测量是引起非酉变换的不可逆动作。

图2是一组方程，描绘了对应于根据本发明的至少一个实施例的量子位的基矢量的一个示例。如图2所示，一个量子位的主要量子状态，即|0>和|1>，每个都可以由一个长度为2的基矢量表示，该基矢量包括指示该系统排他地处于一个主要量子状态或另一个主要量子状态的二进制条目。如等式210所示，一个量子位的任何量子状态(即，|ψ>)可以被表示为|0>和|1>基本状态的一个线性组合(即，通过这些基本状态的标量乘数)。在所示的等式中，|0>和|1>基态的标量乘数(即幅度)分别是希腊字母alpha(α)和beta(β)。因此，一个测量的量子位塌缩为一个|0>状态的概率是|α|²，并且一个测量的量子位塌缩为一个|1>状态的概率是|β|²。

图3是一组方程，描述了根据本发明至少一个实施例的量子系统的张量表示的两个示例。代替更常见的Dirac符号，包括n个量子位的量子系统可以表示为由Markov和Shi引入的n维数组(即，张量)。具体地，在此用带有n个指数下标(i₁…i_n)的希腊字母psi(ψ)表示的张量310可以用于表示n个量子位的量子状态，其中观察到塌缩或测量值的概率由与表示为|i₁…i_n>的基本状态320相关联的复数标量幅度ψ确定。当量子系统被塌缩或测量时，基态320的每个指数下标(i₁…i_n)是二进制值。

量子态的张量表示和狄拉克表示之间的关系在等式330中示出。在狄拉克表示中的量子态是|0…0>、…、|1…1>基本状态的线性组合，其中对应的量子态张量的值是定义该线性组合的复数标量乘数。等式330中的张量值因此与等式210中的希腊字母alpha(α)和beta(β)起相同的作用。

方程340中示出了另一个示例量子系统(即，量子电路)的完整张量方程。在所描绘的示例中，在包括初始处于量子态ψ的N个量子位的量子电路中，将双量子位(two-qubit)门应用于量子位k和m，k＜m。等式340表示根据初始量子态ψ和张量u得到的量子态ψ'的张量的值，张量u对应于由双量子位门定义的酉线性变换。Dirac符号中的等效方程将明显更加复杂，需要将4维门张量u展开成2n乘2n维矩阵，其中u的16个值中的每个值在该矩阵的行和列的正确组合中复制2^(n-4)次。除非k＝m-1，否则Dirac符号的等效方程将相当混乱，而其使用张量符号容易表达。

图4A是一组示意性符号，图4B是一组相应的张量表，其描绘了根据本发明的至少一个实施例的量子门的各种示例。所描述的量子门包括Pauli门410、叠加门420、受控NOT门430、受控Z门440和non-Clifford门450。所描绘的量子门是可以在量子计算系统中使用的门的非穷举性示例。

Pauli门410对应于考虑了粒子的自旋与外部电磁场的相互作用的Pauli方程。叠加门420分别包括Hadamard门420A、S门420B和

门420C。Hadamard门420A将|0>和|1>主(异或)基态映射到|0>和|1>中间的状态，分别即(|0>+|1>)/√2和(|0>-|1>)/√2，这使得|0>和|1>基态的概率相等。S门420B和

门420C分别有时用于将90°相位旋转添加到叠加。

受控门作用于两个或更多个量子位，其中一个或多个量子位充当对特定操作的控制。利用受控Z(CZ)门440，量子位之一确定Pauli Z操作是否被应用于另一量子位。CZ门的作用在某种意义上是完全对称的，结果是相同的，与哪个量子位是控制无关。利用受控的NOT(CNOT)门430，这些量子位之一确定是否对另一个量子位应用一个Pauli X操作，从而导致该另一个量子位是NOT的(翻转的)。CNOT门430和CZ门440都可以用于使量子位纠缠和解缠。CNOT门的经典模拟是可逆XOR门。

non-Clifford门用于近似任意的酉变换。所描绘的non-Clifford T门450A和

门450B分别添加45°相位旋转。而Clifford门410到440仅允许实现有限数目的不同酉变换，T和

门的添加将该集合扩展到无穷大，使得能够通过这些门的适当组合将任何酉变换近似到任意精度。通用量子计算依赖于这种能力。

量子计算领域的技术人员将认识到，Z、S、

CZ、T和

门是对角酉门，也就是说，它们的狄拉克矩阵表示是对角的，其中非对角项是零。另一方面，对角酉门的张量表示仅需反映这些对角项，如图4B所示。

图5是对应于传统上被假设为不可能在当前可用的经典计算系统上模拟的大量子电路的执行计划500。如所描绘的，执行计划500包括其中包含门符号520的多个瓦片(tile)510。每个瓦片510对应于一个级或时间步，并且门符号520指示在所指示的级或时间步期间对一个或多个量子位执行的功能(变换)。在所描绘的实施例中，执行计划500在每行内从上到下逐行执行，并且从左到右逐片执行。本领域技术人员将理解，每个瓦片对应于量子位的7×7数组，并且需要2⁴⁹个存储器值来表示49个量子位的所有可能状态。因此，当使用两个8字节浮点值来存储(复杂)量子位状态信息时，需要2⁵³个字节(8千兆兆字节)的存储器来保证使用常规模拟技术对所描绘的执行计划的模拟。

图6是根据本发明的至少一个实施例的在此用作处理示例的量子电路650的示意图以及对应的基于文本的说明。在量子电路650中指定的量子门包括Hadamard门660、XPauli门670A、Y Pauli门670B、Z Pauli门670C和CNOT门680。所描绘的基于文本的描述符合OpenQASM规范，并且指示哪些门对特定量子位进行操作。假定指定的函数和门是依照级/时间步长顺序的。因此，所描绘的基于文本的描述是极其紧凑的。

图7是描绘根据本发明的至少一个实施例的量子电路模拟方法700的一个示例的流程图。如所描绘的，量子电路模拟方法700包括接收(710)量子电路的数字描述，进行(720)预划分优化，将量子电路划分(730)成子电路，确定(740)执行顺序，以及执行(750)量子电路。量子电路模拟方法700可以由诸如图15中描绘的计算机1500之类的计算机执行，并且使得能够在一个或多个常规计算机和相关联的存储设备上模拟量子电路。

接收(710)量子电路的数字描述可以包括接收量子电路的基于文本的或二进制的描述。该描述可以指示包括在电路中的量子门以及门之间的依赖性。在一个实施例中，数字描述符合OpenQASM规范。

进行(720)预划分优化可以包括进行减少执行量子电路所需资源的门置换(substitution)(例如，电路重写)。电路重写还可以包括在量子电路的最后级中执行门置换，其用从电路的末端向内引导的用于一些量子位的对角酉门的链替换非对角酉门。这种电路重写使得张量切片能够在电路中更早地执行，以便比没有这种重写的情况进一步降低存储器要求。电路重写还可以包括将多量子位门移位到电路的后级的门置换。这种电路重写可以推迟存储器需求的增长直到电路中的稍后，并且可以增加应用附加张量切片以甚至进一步减少模拟量子电路所需的存储器需求的机会。

将量子电路划分(730)为子电路可以包括(启发式地或穷举地)估计多个可能分区的资源成本，并且选择具有最低资源成本的划分。在一些实施例中，估计和选择是递归地进行的。在某些实施例中，每个输入量子位被分配给一个单独的子电路，并且这些子电路竞争以消耗它们所连接的后续级门。在一些实施例中，门依赖性图形被用于(至少最初)将量子电路划分成单个量子位和多个量子位子电路。

确定(740)执行顺序可以包括使用相关性信息来确定子电路的执行顺序。在一些实施例中，通过创建类似于图5的执行计划并比较每个子电路中的第一门的级或时间步长来确定执行顺序。

执行(750)量子电路可以包括根据执行顺序执行每个子电路。在一些实施例中，使用多个处理器，并且每个可用的处理器从执行控制器请求下一个未执行的子电路。在其他实施例中，为每个子电路产生一个进程，并且以与执行顺序相反的顺序分配进程的优先级，使得较早级子电路被分配较高的优先级。在一些实施例中，以跨多个处理器的并行分布式方式执行子电路的模拟；例如使用高性能计算技术。在一些实施例中，在图形处理单元上执行模拟计算。

图8A-图8C是描述与模拟图4和图5中描述的各种量子门相关联的张量方程和资源成本的文本图。如图所示，与根据所描绘的张量方程更新量子位相关联的资源成本取决于特定函数以及用于保持量子系统中的状态信息的量子位的数目。例如，应用于n个量子位的量子系统中的两个量子位的Hadamard门将需要

个复数乘法、2ⁿ个复数加法、以及

个字节的存储器。相比之下，受控Z门将需要相同字节数的存储器，但是将需要一半数目的复数乘法和零复数加法。这个相同属性适用于所有对角酉门，包括Z、S、

CZ、T和

门。通过为每个门实现专用代码以利用以下事实，即可以避免与零或与一相乘，并且与-1的相乘仅仅是符号改变，可以实现每个门的操作数目的进一步减少。类似地，复数与纯实数或纯虚数系数的乘法仅需要两个浮点乘法，而不需要加法，而不是通常的四个乘法和两个加法。在一些实施例中，本发明利用资源成本的知识来比较量子电路模拟过程中的选项。

图9A-图9E是示出根据本发明的至少一个实施例的划分对模拟量子电路的一个特定示例所需的计算资源的影响的示意图和方程图。

图9A描绘反映用于模拟量子电路的常规方法的电路划分，其中首先构造和初始化保持电路中的所有量子位的量子状态的数据结构，然后通过模拟以输入到输出顺序执行的每个门的效应来更新该数据结构。这种常规方法对应于电路划分，其中量子位的初始状态一起被放置在一个子电路中，并且门一起被放置在第二子电路中，如图所示。图9A中描述的等式反映了使用该方法执行的计算。首先构造并初始化初始状态张量φ，其中初始化采用KroneckerΔ张量

它是Dirac量子基态|0>的张量等价：

然后，通过以输入到输出顺序应用图8中所示的等式，从初始状态张量φ计算最终状态张量ψ。

图9B描绘了现有技术中已知的稍微更复杂的电路划分类型，其中量子位q[0]和q[1]被独立地模拟到可能的程度，直到遇到必须应用于两个量子位的多量子位门。在这种情况下的传统方法是然后组合q[0]和q[1]的独立模拟的结果，并且最后将剩余的门应用于所得到的组合状态以产生最终的量子状态。图9B中描述的等式精确地对应于该模拟方法。

图9C、图9D和图9E示出了本发明的创造性见解，即通过采用量子门的张量表示，代数定律使得人们能够任意地将门的集合划分为子电路，模拟每个子电路，并且组合它们的结果以产生电路的最终量子状态的数学上相同的计算。图9C和图9D示出了两个划分，其中门对量子位q[0]和q[1]的影响首先被独立地模拟，然后它们的结果被组合。在图9C中，CNOT门的模拟(应用于两个量子位并由此使它们纠缠)被分配到对应于量子位q[0]的模拟的顶部子电路，而在图9D中，CNOT门被分配到底部子电路。

到目前为止，量子电路模拟中的传统知识是，一旦通过应用诸如CNOT门的多量子位门使量子位纠缠，则必须一起模拟纠缠的量子位。换句话说，传统的知识认为，如果两个子电路包含应用于相同量子位的门，尤其是如果这两个子电路在它们的执行计划中在时间上叠加(即，如果两个子电路具有重叠的执行级)，则不能独立地模拟这两个子电路，这意味着一个子电路中的所有门不是严格地在另一子电路中的所有门之前或之后，而是两个子电路的门的排序在作为整体的电路内重叠。然而，图9C和图9D相反地示出了图9C和图9D中所示的方程产生了彼此之间以及与图9A和图9B中所示的方程之间数学上相同的结果，尽管明显违反了传统知识。

允许以这种方式执行模拟的实现洞察力是如图9D所示的纠缠指数的思想。纠缠指数是在两个不同子电路中的门张量之间共享的张量指数(index)(例如，变量)。在图9D中，b和c是纠缠指数。在图9C中，e和f是纠缠指数。这些纠缠指数提供了使包含应用于相同量子位的门的子电路能够被独立模拟并且使它们的结果以数学上正确的方式组合所需的数学簿记(bookkeeping)。

原则上，如图9E所示，可以使用这种见解来任意地划分量子电路中的门。然而，在本发明的优选实施例中，子电路的构造目标是实现总仿真的资源成本的净减少。

图10是描绘根据本发明的至少一个实施例的量子电路划分方法1000的一个示例的流程图。如所描绘的，量子电路划分方法1000包括为每个初始级量子位创建(1010)子电路，将后续级门添加(1020)到子电路，确定(1030)是否已经分配了所有门，确定(1040)执行顺序，选择(1050)桥接门，确定(1060)是否纠缠桥接的子电路，以及关闭(1070)桥接的子电路或将桥接门添加(1080)到纠缠的子电路中的一个。量子电路划分方法1000是至少图7中所示的划分操作730的一个示例，并且可以由诸如图15中描绘的计算机1500之类的计算机执行。量子电路划分方法1000使得能够以能够减少或最小化使用常规计算机和相关联的存储装置模拟量子电路所需的资源的方式来划分量子电路。

为每个初始级量子位创建(1010)一个子电路可以包括确定一个量子电路(至少最初)所需的量子位的数目并且初始化一个数据结构，该数据结构用于为该量子电路所需的这些量子位中的每一个定义一个子电路。将后续级门添加(1020)到子电路可以包括将仅需要来自当前被分配给子电路的量子位的输入的未分配的下一级门添加到每个子电路。该添加步骤还可以包括确定用于被分配给子电路的量子位的所有剩余的未分配门是否是对角酉门，并且如果是，则闭合该子电路，创建具有与闭合的子电路相同的被分配量子位的新的子电路，并且将该新的子电路标记为已经被创建用于对所有剩余的未分配门是对角酉门的(多个)被分配量子位进行切片的目的。闭合子电路可以包括将子电路标记为完成，以便防止向子电路添加其他门。

确定(1030)是否已经分配了所有门可以包括确定未分配的门计数或一些其他指示符是否指示已经将所有门分配给子电路。确定(1040)执行顺序可以包括进行结合图7描述的确定操作740。

选择(1050)桥接门可以包括选择未分配的下一级门，该门需要来自当前被分配给子电路的至少一个量子位以及当前未被分配给子电路的一个或多个量子位的输入。换言之，桥接门是需要来自当前创建的多个子电路的输入的门。

确定(1060)是否纠缠桥接子电路可以包括估计其中做出纠缠桥接子电路与不纠缠的决定的替换方案的资源成本，比较与每个决定相关联的资源成本，并且然后选择最低成本的替换方案。

闭合(1070)桥接的子电路可以包括将子电路标记为完整的，以便防止向桥接的子电路添加其他门。将桥接门分配(1070)到新的子电路可以包括创建新的子电路，将被闭合的桥接子电路的量子位分配到该新的子电路，并且然后将桥接门分配到该新的子电路。

将桥接门添加(1080)到纠缠子电路中的一个纠缠子电路可以包括将桥接门添加到包括在子电路中的门的列表。此添加步骤还可以包括首先用门的等效组合来替换桥接门，其中新的桥接门变成对角酉。一个例子是用图12B所示的CZ门和Hadamard门的组合代替CNOT门，以便用图12D所示的等效门组合来代替图12A所示的CNOT门。当进行这种置换时，新的桥接门被分配给桥接子电路之一，并且在这种重写中可能已经引入的任何单量子位门根据分配给那些子电路的量子位而被分配给子电路。例如，在用CZ门代替CNOT门的特定情况下，引入的Hadamard门被分配给相应的量子位所分配到的子电路，以便符合上面结合步骤1020描述的用于将后续级的门添加到子电路的规则。另一方面，CZ门可以被分配给任何一个纠缠的子电路。

图11A是描绘了根据本发明至少一个实施例的量子电路执行方法1100的一个示例的流程图。如所描绘的，量子电路执行方法1100包括接收(1110)量子子电路的有序集合，分配(1120)不同的指数变量，传播(1130)指数变量，执行(1140)每个量子子电路。量子电路执行方法1100使得能够执行被划分为子电路的量子电路。量子电路执行方法1100可以由诸如图15中描绘的计算机1500之类的计算机执行。

接收(1110)量子子电路的有序集合可以包括接收指向对象或数据结构的指针的有序列表，所述对象或数据结构定义包括其中包含的门的每个量子子电路。在一个实施例中，每个量子子电路的定义基本上是与图5中所示的执行计划类似的子电路执行计划。分配(1120)不同的指数变量可以包括将不同的指数变量分配给每个量子位的初始状态以及分配给每个非对角酉门的输出。

传播(1130)指数变量可以包括从输入到输出迭代地传播每个对角酉门的指数变量。执行(1140)每个量子子电路可以包括执行每个量子子电路并且以指定的顺序组合所生成的结果。

图11B是描述图11A中描述的执行操作1140的可能实施例的流程图。如所描绘的，执行(1140)子电路和组合结果的实施例可以包括构造(1150)张量的积以及执行(1160)求和。

构造(1150)张量积可以包括在步骤1120和1130标识属于子电路的门以及分配给那些门的指数变量，将这些指数变量分配为子电路中的门的对应张量的下标，以及将子电路的张量组合成以输入到输出顺序布置的积。构造(1150)张量积还可以包括根据通过结合图7所述的确定操作740和/或结合图10所述的确定操作1040得到的执行排序，将对应于子电路的模拟结果的张量组合成张量积。

执行(1160)求和可以包括按照上述构造操作1150中确定的输入到输出顺序计算子电路的张量的积，并且当在确定的输入到输出顺序中遇到指数变量时，对这些子电路内部的指数变量执行求和。对作为整体的电路内部的指数变量执行(1160)求和可以包括：当计算在上述用于组合子电路的模拟结果的构造操作1150中确定的张量的积时对这样的指数变量执行求和。在量子位的电路中没有门有待模拟的情况下，或者在该量子位的所有剩余门都是对角酉门的情况下，子电路的模拟结果的这种组合之前可以引入在一个或多个此类量子位的可能值上循环的for循环。然后可以为受影响张量的切片计算后续张量积及其总和，以减少后续计算的存储器需求。

图12A-图12C是描绘优化量子电路的一个特定示例的一个示例的示意图。在一些实施例中，可以在本文公开的方法内的各个点处进行门置换(也称为电路重写)。例如，诸如图12B所示的重写的电路重写可以结合图7所示的方法700的步骤720来执行，或者当执行图10所示的方法1000的步骤1080时执行。特别地，用CZ门和Hadamard门的等效配置代替桥接CNOT门，可以减少当对应子电路纠缠时引入的纠缠指数的数目，这又具有减少模拟所得纠缠子电路所需的存储器的量的效果。

返回参考图11A的步骤1140和如图11B中所示的其可能的实施例，本领域技术人员将理解，在本发明的至少一个实施例中，可以从由各个量子位的初始状态创建的初始子电路开始，以输入到输出顺序有效地模拟子电路。利用这种方法，将不会模拟后续子电路，直到已经模拟了它们所依赖的用于输入的先前子电路。每个子电路的模拟结果可以对应于可以在计算机存储器中表示为n维数组的n维张量。本领域技术人员将认识到，也可以采用提供等效表示的其他数据结构，例如线性数组。

在一个实施例中，存储在这些数据结构中的值可以是双精度复数浮点数，每个需要16字节的存储。n维张量/数组的存储器占用将需要2⁽ⁿ⁺⁴⁾个字节来存储张量/数组中的所有2ⁿ个值。

从各个量子位的初始状态创建的初始子电路可以是用在零位置中的值一和在一位置中的值零初始化的一维张量/数组。这种初始化对应于KroneckerΔ张量

它又对应于量子基态|0>：

对于仅依赖于一个在前输入子电路的后续子电路，可以使用在前输入子电路的模拟结果来初始化模拟结果数组。通常，如果在前输入子电路的模拟结果张量/数组具有维度n，并且如果已经标识出s个新的量子位用于在前输入子电路的模拟中尚未被切片的对应的后续子电路的切片，则该后续子电路的模拟可以涉及引入for-循环以循环针对切片而标识的s个新的量子位的可能值(如果有的话)，创建n-s维张量/数组(或其他合适的数据结构以保持针对后续子电路的模拟结果)，并且然后通过从针对由for-循环变量(如果有的话)的值标识的切片的在前输入子电路的模拟结果复制对应值来初始化该n-s维张量/数组。然后，可以在这些for循环内进行所讨论的当前后续子电路的模拟计算，因为这些分片for循环同样适用于这些下游子电路，所以还没有被模拟的所有下游子电路的模拟计算也可以。

对于依赖于两个在前输入子电路的在后子电路，这种在后子电路的模拟结果的初始维数由n+m-g-s给出，其中n和m分别是在前两个输入子电路的模拟结果中的维数，g是在这两个子电路之间共享的、在处理的这个阶段可以被求和的纠缠指数的数目，并且s是在任一在前输入子电路的模拟中为该在后子电路的切片而标识的、尚未被切片的新量子位的数目。该后续子电路的模拟可以涉及引入for-循环以对被标识用于切片的s个新量子位的可能值进行循环(如果有的话)，创建n+m-g-s维数组或其他合适的数据结构以保持后续子电路的模拟结果，并且然后通过对由for-循环变量(如果有的话)的值标识的切片执行两个在前输入子电路的模拟结果的张量乘法并且对在这两个子电路之间共享的、可以在处理的该阶段被求和的纠缠指数(如果有的话)进行求和来初始化该n+m-g-s维数组。

当以这种方式组合先前输入子电路的模拟结果以初始化后续子电路的模拟时，可以被求和的共享纠缠指数是来自最初被纠缠以创建纠缠指数的所有子电路的模拟结果现在正找到它们直接或间接进入该最终组合操作的方式的那些指数，并且这些指数不作为这些先前输入子电路中的任何一个的输出指数出现。该要求的第一部分反映了代数的分布规律：为了在指数变量上求和，包含该指数变量作为下标的所有项必须出现在求和中。该要求的第二部分反映了量子电路的指数变量可以被求和的条件：该变量必须完全在电路内部直到模拟的当前点，它不能与输出相关联。通常，当电路确实包含仅用于两个量子位的多量子位门时，只要被组合的两个子电路的模拟结果共享共同的纠缠指数，就将满足上述要求的第一部分。然而，如果电路包含三量子位门或更多，则必须明确地检查该第一条件。

当针对包含用于三个或更多个量子位的多量子位门的量子电路应用流程图1000中所示的过程时，仅可以发生多于两个在前输入子电路的模拟结果需要被组合作为到后续子电路的输入时的情况。这些情况的模拟步骤可以遵循与上述两个子电路情况相同的结构，包括用于决定哪些共享纠缠指数应该被求和的上述条件。通常，通过重复应用上述两输入方法以成对的方式组合这些结果在计算上可以是有利的。根据经验，在每个步骤组合的结果对应该是作为该步骤的结果产生最低维张量/数组的对。此经验法则有助于减少计算组合模拟结果所需执行的浮点运算的总数。当两个或更多子电路保留时，在模拟结束时可以使用该相同的方法来组合最终子电路的模拟结果。

一旦用于保存子电路的模拟结果的张量/数组已经被初始化，则可以通过以输入到输出的顺序将门应用于张量/数组来计算该子电路的最终模拟结果。对于不导致引入纠缠指数的门应用，定义这些计算的方程具有图3-图5中所示的形式，其中ψ表示在应用门之前的模拟结果张量/数组的值，ψ'表示在应用门之后的值。图3-图5中出现的方程仅仅是说明性的，本领域技术人员将认识到，对于未列出的其他类型的量子门，可以以明显的方式容易地构造相应的方程。

导致产生纠缠指数的门应用需要不同的处理，因为这种门应用通常增加模拟结果张量/数组中的维数，并且需要跟踪现在哪些维对应于分配给子电路的量子位，而哪些维对应于纠缠指数。

当在图10中描绘的过程中在步骤1060做出纠缠子电路的决定并且然后在步骤1080将桥接多量子位门分配给子电路中的一个时，当模拟多量子位门时，在模拟期间必须增加用于多量子位门被分配给的子电路的模拟结果张量/数组的大小。如果多量子位门是双量子位对角酉门，则必须添加一个额外的维度，并且在双量子位非对角酉门的情况下必须添加两个额外的维度。在三个或更多量子位门的情况下，必须进行尺寸的相应增加。这些额外的维度对应于纠缠的指数。

例如，考虑图13A中所描绘的量子电路和子电路。这些子电路可以按以下方式使用图10中所示的过程来获得。在步骤1010处创建用于量子位q[0]和q[1]的子电路之后，在步骤1020处可以将左上H门分配给用于q[0]的子电路，并且然后可以注意到，用于量子位q[0]的所有剩余门都是对角酉矩阵。后者允许闭合q[0]的左上子电路，并且启动用于量子位q[0]的新子电路，其中注释量子位q[0]现在可以被切片。同样在步骤1020，左下X和H可以被分配给量子位q[1]的子电路。由于桥接CZ门，在步骤1020中没有额外的门可以被分配给当前子电路，因此该过程可以进行到步骤1050以选择CZ门。在步骤1060，可以做出纠缠q[0]和q[1]的子电路的决定，并且在步骤1080，可以将CZ门分配给q[0]的当前子电路。然后，该过程可以返回到步骤1020，其中左上Z门可以被分配给q[0]的当前子电路，而左下H和Y门可以被分配给q[1]的子电路，从而得到图13A中所描述的子电路的配置。

继续到图11B中的步骤1150和1160，其描述了图11A中的执行步骤1140的实施例，左上子电路的模拟可以通过初始化张量/数组来进行，该张量/数组包含左上子电路到KroneckerΔ张量的模拟结果，然后应用H门来更新模拟结果：

右上部子电路的模拟然后可以包括引入量子位q[0]的切片for循环，并初始化右上部子电路的张量/数组以等于

的切片：

因为当CZ门与底部子电路纠缠时，其被分配给右上部子电路，所以可以分配具有附加维度的新张量/数组以适应在模拟CZ门的过程中的纠缠指数e：

然后可以照常执行Z门的模拟以更新这个新的张量/数组：

在当进行纠缠决定时未被分配多量子位门的子电路的情况下，模拟结果张量/数组必须增加大小(如果有的话)的(多个)点取决于引入的纠缠指数的数目，并且它们中的哪些(如果有的话)严格地在子电路内部和/或作为整体在电路内部。在被纠缠时未被分配多量子位子门的子电路内部的每个纠缠指数将向该子电路的模拟结果张量/数组添加额外的维度。不在子电路内部但在电路整体内部的纠缠指数将对一些下游子电路的模拟结果张量/数组增加额外的维度，其中当所述纠缠指数被纠缠时，所述子电路未被分配多量子位门。原因是在模拟中的某一点处必须对电路内部的所有指数求和。

引入纠缠指数的目的是通过增加模拟结果张量/数组的维度以便执行必要的计算簿记来使该技术工作，然后在共享纠缠指数的子电路的模拟结果被组合时执行求和，从而将这些求和推迟到模拟的稍后阶段。因此，重要的是跟踪整个电路上的纠缠指数，以便正确地处理它们。发生这种尺寸增加的确切点取决于所涉及的多量子位门是对角酉门还是非对角门。

作为示例，在图13A中所描绘的底部子电路的情况下，模拟结果可以被初始化为KroneckerΔ张量，然后可以照常应用X门和第一H门：

ψ′_c＝δ_c

φ＇_d←∑_cX_dcφ＇_c

φ′_e←∑_dH_edφ′_d

CZ门电路没有被分配给该子电路，因此指数变量e变成纠缠指数，其说明了CZ门电路对该子电路的影响。当应用第二H门时，不能执行对e求和，因为e是纠缠指数。相反，可以分配具有附加维度的新张量/数组，以适应在模拟第二H门的过程中的纠缠指数e：

φ′_c＝δ_c

φ′_d←∑_cX_dcφ′_c

φ′_e←∑_dH_edφ′_d

φ″_ef＝H_feφ′_e

Y门的模拟然后可以照常被执行，以更新该新的张量/数组：

φ′_c＝δ_c

φ′_d←∑_cX_dcφ′_c

φ′_e←∑_dH_edφ′_d

φ″_ef＝H_feφ′_e

φ″_eg←∑_fY_gfφ″_ef

注意，H门通常需要求和，因为它们是非对角门。当组合子电路的模拟结果时，最终将根据用于对纠缠指数求和的规则来执行该求和。纠缠指数的引入是用于将这些求和推迟到模拟的稍后阶段的机制。

当右上和下子电路的结果被组合时，最终可以对纠缠指数e求和。因为右上子电路是以切片的形式模拟的，所以对于右上张量，电路的最终模拟结果ψ_bg的组合步骤将在切片for循环内被执行：

For x in{0,1}do{

τ″_be|_b＝x＝CZ_be|_b＝xτ′_b|_b＝x

τ″_be|_b＝x←Z_b|_b＝xτ″_be|_b＝x

ψ_bg|_b＝x＝∑_eτ″_be|_b＝xφ″_eg

}

图13B示出了用于图13A中所示的相同电路的另一组子电路，其中在图10的步骤1080中，CZ门被分配给底部子电路而不是右上部子电路。在这种情况下，b现在是纠缠指数。在底部子电路的模拟中，初始模拟结果张量/数组可以被初始化为一维，然后当应用CZ门时，可以被增加到二维。

φ′_c＝δ_c

φ′_d←∑_cX_dcφ′_c

φ′_e←∑_dH_edφ′_d

φ″_be＝CZ_beφ′_e

φ＂_bf←∑_eH_feφ＂_be

φ″_bg←∑_fY_gfφ″_bf

在对右上子电路的模拟中，模拟结果张量/数组可以被初始化为如前所述的左上子电路结果的片段，但是这次当Z门被模拟时维度没有增加，因为纠缠指数b已经是模拟结果的指数并且Z是对角酉门，所以当应用它时不需要对b执行求和。因此，b不在子电路的内部，它是输出指数：

注意，如果上述子电路是其中非对角门最终被应用于后续子电路中的量子位q[0]的更大电路的一部分，则右上子电路的模拟结果张量/数组的维度将仍然没有改变，但是q[0]将没有被切片作为右上子电路的模拟的一部分。相反，在包含应用于量子位q[0]的非对角门的后续子电路的模拟期间，将发生模拟结果张量/数组的维度增加以适应纠缠指数变量b，因为在该点b将作为整体变成电路的内部指数，并且因此将必须对其求和。

如同图13A中描述的子电路一样，图13B中描述的右上张量和下张量的模拟结果将在针对上张量的切片for循环内部被组合，但是此时，因为b不是作为整体在电路内部，所以当组合结果时，b不会被求和：

如前所述，当决定纠缠由这种门桥接的两个子电路时，双量子位非对角酉门导致两个纠缠指数。图13C中所示的电路和子电路提供了一个例子。这些子电路可以通过在图10的步骤1060选择纠缠顶部和底部子电路，然后在步骤1080将CNOT门分配给顶部子电路，而不执行电路重写以用CZ门和H门代替CNOT来获得。通过将CNOT门分配给顶部子电路，e和f都变成纠缠指数。当模拟顶部子电路时，可以创建初始一维张量/数组以保持模拟结果，然后当模拟CNOT时可以创建三维张量/数组：

τ′_a＝δ_a

τ′_b←∑_b H_baτ′_a

τ″_cef＝∑_b CNOT _cfbeτ′_b

τ″_cef←Z_cτ″_cef

当模拟底部电路时，可以创建初始一维张量/数组以保持模拟结果，然后当模拟非对角Y门时可以创建三维张量/数组：

φ′_d＝δ_d

φ′_e←∑_dX_edφ＇_d

φ″_efg＝Y_gfφ′_e

然后，当结果被组合时，纠缠指数可以被求和，因为它们都在作为整体的电路内部：

在图10的步骤1080中，将CNOT门改为分配给底部子电路的情况下，则b和c变为如图13D所示的纠缠指数。当模拟顶部子电路时，可以创建初始一维张量/数组以保持模拟结果，并且当模拟Z门时可以仅创建二维张量/数组。在这种情况下，b已经是纠缠指数，并且Z门的模拟将c引入模拟结果张量/数组的指数变量中。

τ′_a＝δ_a

τ′_b←∑_bH_baτ′_a

τ″_bc＝Z_cτ′_b

当模拟底部子电路时，可以创建初始一维张量/数组以保持模拟结果，然后当模拟CNOT时可以创建三维张量/数组：

φ′_d＝δ_d

φ′_e←∑_dX_edφ′_d

φ″_bcf＝∑_eCNOT_cfbeφ′_e

φ″_bcg←∑_fY_gfφ″_bcf

因为c是输出指数而不是电路内部，所以当组合顶部和底部子电路的模拟结果时，仅对b而不是c执行求和：

ψ_cg＝∑_bτ″_bcφ″_bcg

注意，一旦引入了切片for循环，就需要在那些for循环内执行后续的模拟步骤，包括在达到该点之后模拟的子电路的切片for循环。因此，在执行中引入切片循环之前，应当模拟在没有切片的情况下模拟的所有子电路，以便避免那些模拟结果的冗余重新计算。注意，切片的引入是严格可选的，只要有足够的存储器可用于保存所得到的模拟结果。可以从可能切片的那些结果中挑选和选择实际上切片的那些结果。本领域技术人员还将认识到，可以将一些子电路的全部模拟结果存储在次级存储装置中，然后在切片循环中检索这些模拟结果的切片。这些完整的模拟结果本身可以在可能的时候以片的形式计算，并且写入到次级存储装置，而不必在主存储器中实现完整的模拟结果。

本领域技术人员同样将认识到，只有当计算的目的是计算电路的最终量子状态中的所有幅度时才需要切片回路。相反，如果仅仅想要计算测量结果的幅度，则可以转而用由测量结果指示的那些量子位的设置值来代替for循环。仍然执行切片操作，但是现在使用相应量子位的测量值。如果需要计算一组测量的幅度，则为了效率起见，可以首先计算不能被切片的子电路的模拟结果，然后可以建立一个环路以在每个测量的结果上迭代，并且在每次迭代时相应地设置限幅量子位的值。利用这种模拟方法，不再需要嵌套for-循环，这可以在其余子电路的模拟顺序中提供更大的自由度。

图14示出了将对应于图5的大量子电路划分为子电路，使得能够在当前可用的计算系统上模拟量子电路。图5示出了属于一类随机生成的量子电路，该量子电路由Boixo等专门设计，显然不可能在现有的经典计算机上模拟。如他们在其2016论文中要求保护的，“现有超级计算机不能用任何已知算法和显著保真度在大约7×7量子位的2D网格中模拟具有深度25的通用随机电路”，这一声明的基本原理是使用已知技术的这种模拟将需要8千兆兆字节的主存储器来仅存储量子状态信息，并且现有超级计算机都不具有那么多的存储器。通过划分图5中描述的7×7量子位、深度27的电路，并使用本发明对其进行模拟，我们能够仅使用4.5太字节来模拟电路，以存储模拟结果张量/数组。

图14描绘了我们所采用的划分。属于图12中的对应瓦片的含有数字“1”且具有白色背景的部分的图5中的门属于一个子电路，其将被称为顶部子电路。属于图12中的对应瓦片的包含数字“2”且具有浅灰色背景的部分的图5中的门属于将被称为底部子电路的另一子电路。属于图12中的对应瓦片的部分的图5中的门属于第三子电路，该第三子电路将被称为“左”子电路，该对应瓦片的部分包含具有深灰色背景的数字“3”，或者包含具有黑色背景的白色字母“S”。顶部和底部子电路是纠缠的，其中桥接门是跨越图5中描绘的顶部一行瓦片中的两个最右瓦片的第三和第四行的CZ门。这些CZ门可以被分配给顶部或底部子电路而不影响模拟电路的能力。在我们进行的模拟中，这些CZ门被任意地分配给底部子电路。顶部和底部子电路的组合需要0.5兆兆字节来存储它们的模拟结果，而剩下的子电路需要4兆兆字节。在计算顶部和底部子电路的模拟结果之后，设置切片环路以对由字母“S”标识的量子位和着色为浅绿色的量子位以及对应于7×7片的底部的剩余量子位的值进行切片。在提供64兆兆字节的可用主存储器的IBM Blue Gene Q计算机的四个机架上执行切片的计算。在六个不同的组(每组四个机架)上执行不同范围的循环，以便将整个计算加速到六倍。

还模拟了8×7量子位、深度23随机量子电路(未示出)的一个切片。这个56量子位电路以非常相似的方式被划分。在这种情况下，所构造的三个子电路的模拟结果仅需要存储3太字节的主存储器。相比之下，现有技术的模拟方法将需要1艾字节来存储主存储器中的整个量子状态并对其进行操作。这些例子用于说明本发明对于量子模拟的巨大优点。

基于上述说明，如何根据上述使用情况以及本发明的其他可能使用情况中的每一个的维数和字节数来计算每个子电路的模拟结果和最终模拟结果的初始和最终大小对于本领域技术人员而言应当是明显的。对于本领域技术人员来说，如何估计模拟每个子电路所需的浮点运算的数目，以及如何组合上述使用情况中的每一个的最终结果以实践本发明，以及如何实现本发明的其他可能的使用情况，也是明显的。本领域技术人员将认识到，可以结合图10中所示的过程采用各种现有技术优化技术，以例如找到最小化上述用例中的每一个以及本发明的其他可能用例的浮点操作数目的电路划分，其受到对目标部署系统上可用的最大存储器的限制。示例包括深度优先搜索、宽度优先搜索、迭代加深深度优先搜索、Dijkstra算法和A*搜索。

本领域技术人员将认识到，将图10中所示的过程实现为深度优先递归优化过程可以包括在图10中所示的该过程中的每个决策点处引入循环以循环所有可能的决策选择，然后在这些循环内，从该过程中的这些点递归地调用图10中所示的过程，以向前用于每个可能的选择，并且在循环结束时返回优化期望的资源成本度量的选择。这些判定点可以包括用于选择可分配桥接门的步骤1050、用于选择是否纠缠子电路的步骤1060、用于将桥接门分配给子电路的步骤1080，以及用于确定子电路执行顺序的步骤1040。在这些点处的一些决定可以替代地通过应用经验规则来做出，而其他决定可以被包括作为深度优先搜索的一部分。要最小化的期望资源成本度量可以包括最大存储器需求、计算所有幅度的浮点操作的总数、或者计算单个幅度的浮点操作的总数。如果违反了期望的约束，则也可以引入条件测试以放弃选择。期望的约束可以包括使模拟的总存储器需求保持在指定的限制内。它们还可以包括对深度优先过程本身所消耗的总运行时间的限制。深度优先过程可以被实现为根据期望的资源成本度量来记录迄今为止找到的当前最佳选择集合，使得如果深度优先过程在执行完整的搜索之前被终止，例如当施加运行时间限制时，则仍然可以从执行深度优先过程获得益处。

本领域技术人员将认识到，刚刚描述的深度优先搜索过程有效地生成了决策选择的可能序列以及由此引起的电路划分的树。宽度-第一搜索一次一层地探索这个树。本领域技术人员将认识到，宽度优先搜索可以被实现为迭代加深深度优先搜索，其中对所做出的决定的数目设置限制，并且一旦超过该限制就放弃搜索树的分支。宽度优先搜索的动机是搜索成本趋向于随搜索深度指数增长，因此如果可以在浅搜索深度内找到对优化问题的合理解，则该解可能是足够的。如果不是，则可以通过增加深度限制并再次执行搜索来加深搜索。

在本发明的上下文中，还可以不仅仅对搜索的深度设置限制，而是替代地对在图10的步骤1060中可以选择的纠缠选择的次数设置限制。如果在步骤1060从未做出纠缠的选择，而是总是继续到步骤1070，则步骤1070将被执行的次数将永远不会大于量子位的数目。原因是步骤1070具有将量子位的组合并在一起作为将子电路的结果合并在一起的副产品的效果，并且这种分组操作的数量不能多于被分组的量子位的数量。每次在步骤1060做出纠缠子电路的选择，有效搜索树在该点变宽，并且至少一个额外的层更深地增长。对可以进行纠缠的选择的次数设置迭代增加的限制可以由此限制针对限制的给定设置(其是广度优先搜索的基本目的)执行的搜索量，而同时在一组完全划分的电路上执行搜索优化。相反，简单地限制搜索的深度将导致在电路被完全划分为子电路之前，搜索树中的分支过早地终止，从而浪费了大量精力来生成和探索搜索树中的非解。

可以同样适用于本发明的宽度优先搜索的变化是Dijkstra算法。在图10所示的过程中，给定在各个决策点所作的任何选择序列，可以估计所得到的模拟过程直到实际模拟中的对应点所消耗的资源成本度量。示例包括迄今为止的浮点运算的累积数目和迄今为止的最大存储器要求。本领域技术人员将认识到，Dijkstra算法可以通过将数据结构放置到优先级队列数据结构中来实现，该优先级队列数据结构对决策选择序列以及直到所得模拟中的对应点的资源成本度量进行编码。然后，Dijkstra算法可以通过从优先级队列中选择最低成本的决策选择序列、估计与采取每个可能的下一决策选择相关联的资源成本、以及将得到的下一步决策选择和相关联的资源成本放置到优先级队列中并重复来进行。通过将决策选择序列放置并初始清空到优先级队列中，连同执行步骤1010和1020的资源成本，可以为图10中所示的过程初始化Dijkstra算法，所述资源成本是对应于步骤1050的第一决策点的前体。概念上讲，Dijkstra算法通过标识到目前为止获得的最低成本决策序列，然后一旦并入下一决策点的结果，就查看该决策序列接着通向何处来进行操作。

本领域技术人员将认识到，Dijkstra算法的进一步变型是A*搜索。通过将由决策选择序列产生的成本与如果从这些点向前做出最佳决策选择序列则这些成本将增加多少的下限估计相结合，A*搜索修改了Dijkstra算法。从概念上讲，通过标识具有最低总成本估计(与搜索中当前点的成本相比)的决策序列，并且一旦并入下一决策点的结果，就查看该决策序列接着通向何处，来进行A*搜索。在本发明的上下文中，假定现有张量在大小上不会增加，则可以通过计算应用任何剩余门的成本来获得剩余浮点操作数目的下界。在桥接子电路的多量子位门的情况下，最小的桥接子电路的大小可以用来计算应用该多量子位门的成本的下限。存储器需求增加的下限可以假设存储器需求不再增加。

图15是描绘适于执行本文公开的方法的计算装置(即，计算机1500)的一个示例的框图。应当理解，图15仅提供了一个实施例的图示，并不暗示对其中可以实现不同实施例的环境的任何限制。可以对所描述的环境进行许多修改。

如图所示，计算机1500包括通信结构1502，其提供(多个)计算机处理器1505、存储器1506、永久性存储装置1508、通信单元1512和(多个)输入/输出(I/O)接口1515之间的通信。通信结构1502可以用被设计成在处理器(诸如微处理器、通信和网络处理器等)、系统存储器、外围设备、以及系统内的任何其他硬件组件之间传递数据和/或控制信息的任何体系结构来实现。例如，通信结构1502可以用一个或多个总线来实现。

存储器1506和永久性存储装置1508是计算机可读存储介质。在所描述的实施例中，存储器1506包括随机存取存储器(RAM)1516和高速缓冲存储器1518。通常，存储器1506可以包括任何合适的易失性或非易失性计算机可读存储介质。

一个或多个程序可以被存储在永久性存储装置1508中，以供相应计算机处理器1505中的一个或多个经由存储器1506的一个或多个存储器来执行。永久性存储装置1508可以是磁硬盘驱动器、固态硬盘驱动器、半导体存储设备、只读存储器(ROM)、可擦除可编程只读存储器(EPROM)、闪存或能够存储程序指令或数字信息的任何其他计算机可读存储介质。

永久性存储装置1508使用的介质也可以是可移除的。例如，可移除硬盘驱动器可以用于永久性存储装置1508。其他示例包括光盘和磁盘、拇指驱动器、以及智能卡，它们被插入到驱动器中以便传送到也是持久存储装置1508的一部分的另一计算机可读存储介质上。

在这些示例中，通信单元1512提供与其他数据处理系统或设备的通信。在这些示例中，通信单元1512包括一个或多个网络接口卡。通信单元1512可以通过使用物理和无线通信链路中的一种或两种来提供通信。

(多个)I/O接口1515允许与可以被连接到计算机1500的其他设备输入和输出数据。例如，I/O接口1515可以提供到诸如键盘、小键盘、触摸屏和/或一些其他合适的输入设备的外部设备1520的连接。外部设备1520还可以包括便携式计算机可读存储介质，诸如拇指驱动器、便携式光盘或磁盘、以及存储卡。

用于实践本发明的实施例的软件和数据可以被存储在这样的便携式计算机可读存储介质上，并且可以经由(多个)I/O接口1515加载到持久性存储装置1508上。(多个)I/O接口1515还可以连接到显示器1522。显示器1522提供向用户显示数据的机制，并且可以是例如计算机监视器。

本领域技术人员将理解，以上公开的实施例可以适用于各种环境和应用。此外，基于在本发明的特定实施例中实现的应用来标识这里描述的程序。然而，应当理解，这里的任何特定程序术语仅是为了方便而使用，因此本发明不应当限于仅在由这样的术语标识和/或暗示的任何特定应用中使用。

本文公开的实施例包括系统、方法和/或计算机程序产品。计算机程序产品可以包括其上具有计算机可读程序指令的计算机可读存储介质(或多个介质)，所述计算机可读程序指令用于使处理器执行本文公开的方法。

计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以是――但不限于――电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携式压缩盘只读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质中。

用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构(ISA)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、集成电路配置数据或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言—诸如Smalltalk、C++等，以及过程式编程语言—诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)，该电子电路可以执行计算机可读程序指令，从而实现本发明的各个方面。

这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其他可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其他可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其他可编程数据处理装置、或其他设备上，使得在计算机、其他可编程数据处理装置或其他设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其他可编程数据处理装置、或其他设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

应当注意，本说明书不旨在限制本发明。相反，所呈现的实施例旨在覆盖包括在由所附权利要求限定的本发明的精神和范围内的一些备选、修改和等同物。此外，在所公开的实施例的详细描述中，阐述了许多具体细节以便提供对所要求保护的发明的全面理解。然而，本领域技术人员将理解，可以在没有这些具体细节的情况下实践各种实施例。

尽管以特定组合描述了本文所公开的实施例的特征和元件，但是每个特征或元件可以在没有实施例的其他特征和元件的情况下单独使用，或者在具有或不具有本文所公开的其他特征和元件的情况下以各种组合使用。

本书面描述使用所公开的主题的示例来使本领域技术人员能够实践本主题，包括制作和使用任何设备或系统以及执行任何结合的方法。主题的可专利范围由权利要求限定，并且可以包括本领域技术人员想到的其他示例。这些其他示例旨在处于权利要求的范围内。

Claims (24)

1.一种由一个或多个处理器执行的用于对包括多个量子门的量子电路进行模拟的方法，所述方法包括：

接收所述量子电路的数字描述；

将所述量子电路的所述数字描述划分成多个量子子电路，其中所述多个量子子电路中的每个量子子电路包括一个或多个量子门；

确定针对所述多个量子子电路的子电路依赖性；

根据所述子电路依赖性来模拟所述多个量子子电路，以产生针对所述多个量子子电路中的每个量子子电路的模拟结果；

其中所述多个量子电路中的第一量子子电路和第二量子子电路各自包含被应用于公共量子位的一个或多个门；以及

其中所述第一量子子电路和所述第二量子子电路使用纠缠张量指数而被独立地模拟。

2.根据权利要求1所述的方法，其中所述第一量子子电路中的所有门既不严格地在所述第二量子子电路中的所有门之前也不严格地在所述第二量子子电路中的所有门之后。

3.根据权利要求1所述的方法，其中所述第一量子子电路和所述第二量子子电路包括重叠的门级。

4.根据权利要求1所述的方法，其中桥接两个子电路的纠缠门被替换为单量子位门和对角酉纠缠门的等效组合。

5.根据权利要求1所述的方法，还包括变换所述量子电路以将纠缠门放置在所述量子电路的一个或多个较后级处。

6.根据权利要求1所述的方法，还包括变换所述量子电路以将对角酉量子门放置在所述量子电路的一个或多个最后级处。

7.根据权利要求1所述的方法，还包括使用所述多个量子子电路中的一个或多个量子子电路的结果来模拟所述量子电路的最后级。

8.根据权利要求1所述的方法，其中子电路以完全方式按输入到输出顺序进行模拟。

9.一种计算机程序产品，包括：

一个或多个计算机可读存储介质和被存储在所述一个或多个计算机可读存储介质上的程序指令，所述程序指令包括用于以下操作的指令：

接收量子电路的数字描述；

将所述量子电路的所述数字描述划分成多个量子子电路，其中所述多个量子子电路中的每个量子子电路包括一个或多个量子门；

确定针对所述多个量子子电路的子电路依赖性；

根据所述子电路依赖性来模拟所述多个量子子电路，以产生针对所述多个量子子电路中的每个量子子电路的模拟结果；

其中所述多个量子电路中的第一量子子电路和第二量子子电路各自包含被应用于公共量子位的一个或多个门；以及

其中所述第一量子子电路和所述第二量子子电路使用纠缠张量指数而被独立地模拟。

10.一种由一个或多个处理器执行的用于对包括多个量子门的量子电路进行模拟的方法，所述方法包括：

接收包括多个级的所述量子电路的数字描述；

为每个初始级量子位创建一个子电路以产生多个子电路；

迭代地将来自所述多个级中的一个或多个后续级的连接的非桥接门添加到所述多个子电路，直到不再有连接的非桥接门可用为止；

选择被连接到所述多个子电路中的两个或更多个子电路的桥接门；

确定是否纠缠所述两个或更多个子电路；以及

响应于确定使所述两个或更多个子电路纠缠，将所述桥接门添加到所述两个或更多个子电路中的仅一个子电路。

11.根据权利要求10所述的方法，还包括创建新的子电路，并且响应于确定不纠缠所述两个或更多个子电路，将所述桥接门分配给所述新的子电路。

12.根据权利要求10所述的方法，还包括将所述新的子电路添加到所述多个子电路。

13.根据权利要求10所述的方法，闭合所述两个或更多个子电路。

14.根据权利要求10所述的方法，还包括确定是否所有门已被分配给子电路。

15.根据权利要求10所述的方法，还包括确定针对所述多个子电路的子电路依赖性。

16.根据权利要求15所述的方法，还包括根据所述子电路依赖性来执行所述量子电路。

17.一种计算机程序产品，包括：

一个或多个计算机可读存储介质和被存储在所述一个或多个计算机可读存储介质上的程序指令，所述程序指令包括用于以下操作的指令：

接收包括多个级的量子电路的数字描述；

为每个初始级量子位创建一个子电路以产生多个子电路；

迭代地将来自所述多个级中的一个或多个后续级的连接的非桥接门添加到所述多个子电路，直到不再有连接的非桥接门可用为止；

选择被连接到所述多个子电路中的两个或更多个子电路的桥接门；

确定是否纠缠所述两个或更多个子电路；以及

响应于确定使所述两个或更多个子电路纠缠，将所述桥接门添加到所述两个或更多个子电路中的仅一个子电路。

18.一种由一个或多个处理器执行的用于对包括多个量子门的量子电路进行模拟的方法，所述方法包括：

接收包括量子门和对应量子位的一组量子子电路的数字描述；

将不同的张量指数分配给每个量子位以及每个非对角酉门的输出；

将张量指数变量从每个对角酉门的输入传播到输出；以及

使用所分配的所述张量指数来执行每个量子子电路。

19.根据权利要求18所述的方法，其中执行每个量子子电路包括构造针对所述量子子电路中的每个门的张量的积。

20.根据权利要求19所述的方法，其中执行每个量子子电路包括使用所分配的所述张量指数来计算所述张量的积。

21.根据权利要求18所述的方法，其中执行每个量子子电路包括对所述量子子电路内部的张量指数执行求和。

22.根据权利要求18所述的方法，还包括确定针对所述一组量子子电路的子电路依赖性。

23.根据权利要求21所述的方法，还包括根据所述子电路依赖性来执行所述量子电路。

24.一种计算机程序产品，包括：

一个或多个计算机可读存储介质和被存储在所述一个或多个计算机可读存储介质上的程序指令，所述程序指令包括用于以下操作的指令：

接收包括量子门和对应量子位的一组量子子电路的数字描述；

将不同的张量指数分配给每个量子位以及每个非对角酉门的输出；

将张量指数变量从每个对角酉门的输入传播到输出；以及

使用所分配的所述张量指数来执行每个量子子电路。

Images