相关申请的交叉引用
本申请要求于2018年12月3日提交的美国专利申请号62/774,479“使用量子计算的改进的交换系统”的申请日的权益，并且其整体通过引用并入于此。
本发明涉及量子计算。
背景技术：
交换系统实现交换计划，其中交易中的参与方将资源或服务直接交换为其他资源或服务，而无需使用诸如金钱之类的交换介质。
一个示例交换系统是实现肾脏移植交换计划的系统。肾脏移植允许患有肾脏疾病的患者用已故的或优选是活体的捐献者的健康肾脏替代其无功能的肾脏。在许多国家，器官贩卖是被禁止的和非法的，因此，活体捐献者通常与患者密切相关。但是，即使患者能够找到愿意捐出其肾脏的捐献者，通常情况下，肾脏与患者的身体也是不相容的。如果移植了不相容的肾脏，患者的身体可能会排斥器官，从而导致移植的失败。
在移植之前，可以以一定的置信度对捐献者肾脏和患者的相容性进行测试和确认。然后，如果发现患者-捐献者对是不相容的或者不能很好地匹配，则该对可以加入肾脏交换计划，以将捐献者肾脏与另一潜在的患者-捐献者对互换。因此，通过在患者-捐献者对的群组之间互换肾脏，肾脏交换计划使得肾脏移植中常见的不相容性问题能够被克服。
肾脏交换的概念最初由费利克斯·拉帕波特(felixrapaport)于1986年提出，并且第一个肾脏交换计划于1991年在韩国实施。从那时起，这个思想就在世界各地逐渐被采纳和执行。如今，许多相容的患者-捐献者对都加入了肾脏交换计划，以寻找更匹配的肾脏。在2015年，执行了最大的所记录的肾脏交换，其在三个月的时间内涉及34对患者-捐献者对和26家不同的医院。
由于肾脏交换的日益普及，肾脏交换计划的规模不断增长。如本说明书中所述，在肾脏交换系统中分配肾脏的互换是一个组合优化问题，并且其在强制执行某些限制时是np完全的。因此，需要高效的算法来解决肾脏交换优化问题。由于肾脏交换问题的np完全性，没有在经典计算机上解决该问题的高效算法。
技术实现要素：
本说明书描述了用于使用量子计算资源在交换系统中分配项目的方法和系统。
利用量子力学现象来执行计算的量子计算资源可以被用来高效地解决np完全问题。近年来，由于量子退火计算机的变得商业可用以及诸如超导量子计算之类的技术的实验性突破，量子计算已变得越来越流行。
量子计算领域最初在二十世纪80年代被引入，特别是由理查德·费曼(richardfeynman)、大卫·德意志(daviddeutsch)和保罗·贝尼奥夫(paulbenioff)等物理学家引入。与使用离散和实向量空间中的位串进行的经典计算相反，量子计算使用量子粒子作为计算资源，其可以被描述为允许复杂幅度(希尔伯特空间)的连续向量空间中的状态。量子计算的优势来自诸如叠加和纠缠之类的量子力学现象，它们允许一个量子系统同时处于不同的状态，并且在多个量子系统内保持相关以及与其他量子系统保持相关。
量子计算领域在1994年受到特别关注，当时彼得·索尔(petershor)提出了第一个量子算法——一种用于整数因式分解的算法——与对应的最佳经典算法相比，该算法证明了指数级加速。这是一个重要的发现，因为诸如rsa密码系统之类的现代密码术的成功是由于难以对大的复合整数进行因式分解。该提议以及后来发现的许多其他高效的量子算法已经证明了量子计算机的潜力。
总体上，可以以一种方法来实现本说明书中描述的主题的一个创新方面，该方法包括：接收表示交换问题的数据；从接收到的数据确定交换问题的整数编程公式；将交换问题的整数编程公式映射到交换问题的二次无约束二进制优化(qubo)公式；从量子计算资源获得表示对交换问题的解决方案的数据；以及基于表示对交换问题的解决方案的所获得的数据来发起动作。
该方面的其他实现包括对应的经典、量子或经典-量子计算机系统、装置和被记录在一个或多个计算机存储设备上的计算机程序，每个都被配置为执行方法的各动作。一个或多个经典计算机和量子计算机的系统可以被配置为借助于在系统上安装有软件、固件、硬件或其组合来执行特定的操作或动作，该软件、固件、硬件或其组合在操作中使或一起使系统执行动作。一个或多个计算机程序可以被配置为借助于包括指令来执行特定的操作或动作，该指令在由数据处理装置执行时使装置执行动作。
前述实现和其他实现可以各自可选地包括单独的或组合的以下特征中的一个或多个特征。在一些实现中，要被解决的交换问题的整数编程公式包括：要被最大化的目标函数；以及包括等式约束和不等式约束的一个或多个约束。
在一些实现中，将交换问题的整数编程公式映射到交换问题的qubo公式包括：将要被最大化的目标函数映射到要被最小化的qubo目标函数；以及将惩罚项添加到要被最小化的qubo目标函数，其中惩罚项基于一个或多个约束而被确定。
在一些实现中，方法还包括确定惩罚项，包括：对于每个等式约束：当约束被满足时，将约束表示为等于零的等式，并且当约束不被满足时，将约束表示为等于严格正值的等式；将等式乘以权重以生成对应的部分惩罚项；以及将所生成的部分惩罚项包括在惩罚项中。
在一些实现中，方法还包括：对于每个不等式约束：将不等式约束公式化为包括松弛变量的等式约束，其中每个松弛变量是二进制变量；使用包括松弛变量的等式约束来确定惩罚项。
在一些实现中，当量子计算资源包括量子退火计算机时，可选地，其中使用量子绝热计算来计算对交换问题的解决方案。
在一些实现中，当量子计算资源包括基于门的通用量子计算机时，可选地，其中使用量子近似优化算法来计算对交换问题的解决方案。
在一些实现中，方法还包括：执行对表示从量子计算资源获得的、对交换问题的解决方案的数据的经典的后处理。
在一些实现中，基于表示对交换问题的解决方案的所获得的数据来发起动作包括：基于对交换问题的解决方案来交换资源或服务。
在一些实现中，接收到的数据包括表示以下的数据：交换问题参与方，其中每个参与方在不使用交换介质的情况下提供资源或服务以交换其他资源或服务；对交换问题参与方之间的交换的约束；以及要被解决的交换问题。
在一些实现中，交换问题包括肾脏交换问题。
在一些实现中，交换问题参与方包括不相容的捐献者-接受者对，其中每个不相容的捐献者-接受者对包括：(i)愿意捐献肾脏的捐献者，以及(ii)需要与捐献者提供的捐献者肾脏类型不同的捐献者肾脏的患者。
在一些实现中，对交换问题参与方之间的交换的约束包括：第一约束，该第一约束确保没有肾脏被捐献超过一次；第二约束，第二约束确保：仅当不相容的捐献者-接受者对中的患者接收来自另一捐献者的肾脏时，不相容的捐献者-接受者对中的捐献者才捐献肾脏。
在一些实现中，要被解决的肾脏交换问题包括：将肾脏交换问题建模为顶点和有向加权边的图，其中顶点表示不相容的捐献者-接受者对，边表示相容的捐献者-接受者对；并且边权重表示相容的捐献者-接受者对的医学益处；以及确定增加相关联的肾脏移植的整体医学益处的、捐献者-接受者对的一个或多个不相交的循环(cycle)。
在一些实现中，一个或多个不相交的循环中的每一个不相交的循环中的捐献者-接受者对的数目低于预定阈值。
在一些实现中，基于表示对交换问题的解决方案的所获得的数据来发起动作包括：基于对交换问题的解决方案来移植多个肾脏。
本说明书中描述的主题可以以特定方式来实现，以实现以下优点中的一个或多个优点。如本说明书中所述，利用量子计算资源的交换系统可以获得对经典计算资源难以解决的交换问题的解决方案。例如，一些交换问题是np完全的，例如归因于与交换问题相关联的约束。由于在经典计算机上没有解决np完全问题的高效算法，因此传统交换系统无法高效地解决这样的交换问题。但是，通过使用本说明书中描述的技术将交换问题重新公式化，可以将交换问题提供给具有高效解决交换问题的处理能力的量子计算资源。
如本说明书中所述，利用量子计算资源的交换系统可以被应用于各种技术应用，包括肾脏交换计划、用于交易商品和服务的数字平台、或用于在微网格网络和电效用分布网之间交换电能的计划。
使用肾脏交换问题作为特定示例，仅在美国，估计有超过100,000人在等待肾脏的移植名单上。这些人在移植前可能会等待平均四到五年。在这样的等待期中，在移植名单上每年有数千人在等待时死亡。当被应用于肾脏交换问题时，本说明书中所述的交换系统可以被用来增加移植数目。此外，患者可以更好地与捐献者匹配。患者-捐献者器官的相容性增加可以使得患者摄取的防止器官排斥的药物(例如环孢素衍生物)的量减少。患者的医疗保健可以得到改善并且死亡率得到降低。
在附图和以下描述中阐明了本说明书的主题的一个或多个实现的细节。根据说明书、附图和权利要求书，本主题的其他特征、方面和优点将变得显而易见。
附图说明
图1示出了用于实现交换计划的示例系统。
图2是用于使用量子计算资源来解决交换问题的示例过程的流程图。
图3是用于将交换问题的整数编程公式映射到交换问题的qubo公式的示例过程的流程图。
在各个附图中，相同的附图标记和标号指示相同的元素。
具体实施方式
本说明书描述了用于使用量子计算资源来解决例如肾脏交换计划的交换问题的方法和系统。提供了一种将交换问题公式化为二次无约束二进制优化(qubo)问题的方法。量子退火计算机可以自然地解决qubo问题，并且基于门的通用量子计算机可以利用量子近似优化算法(qaoa)来高效地寻找对qubo问题的良好近似解决方案。
图1描绘了用于实现交换计划的示例系统100。系统100是被实现为在处于一个或多个位置中的一个或多个经典或量子计算设备上的计算机程序的系统的示例，其中可以实现以下描述的系统、组件和技术。
系统100包括整数编程公式器104、qubo公式器106、经典后处理器108和一个或多个量子计算资源，例如量子退火器110a和量子门处理器110b。为了方便起见，图1中示出了两个附加的量子计算资源，其中量子计算资源在系统100的外部。然而，在一些实现中，系统100可以与更多或更少的附加量子计算资源进行通信，或者系统100可以包括量子计算资源。系统100的组件可以例如通过诸如局域网或广域网之类的通信网络来与每个附加量子计算资源进行数据通信。
系统100被配置为接收表示交换问题的数据作为输入，例如输入数据102。如下面参考图2的步骤202更详细描述的，输入数据102可以包括指定要被解决的交换问题的数据。例如，输入数据102可以包括表示交换问题参与方的数据，其中每个参与方例如在不使用交换介质的情况下提供资源或服务以交换其他资源或服务。输入数据102还可以包括表示交换问题参与方之间的交换约束的数据。
系统100处理接收到的输入数据102，以生成表示要被发起的动作(例如动作112)的输出数据。这些动作基于对交换问题的确定的解决方案。例如，动作可以包括基于对交换问题的解决方案的资源或服务的交换。
系统100被配置为确定对由输入数据102表示的交换问题的解决方案。为了确定对交换问题的解决方案，系统100使用整数编程公式器104、qubo公式器106或经典后处理器108中的一个或多个。
整数编程公式器104被配置为：接收输入数据102，并且处理接收到的输入数据以确定由输入数据102表示的交换问题的整数编程公式114。下面参考图2描述在处理接收到的输入数据时由整数编程公式器104执行的示例操作。
整数编程公式器104被配置为：将由输入数据102表示的交换问题的所确定的整数编程公式114提供给qubo公式器106。qubo公式器106被配置为：接收由输入数据102表示的交换问题的整数编程公式114，并且将由输入数据102表示的交换问题的整数编程公式114映射到由输入数据102表示的交换问题的二次无约束二进制优化(qubo)公式116。下面参考图2描述由qubo公式器106执行以映射接收到的交换问题的整数编程公式的示例操作。
系统100被配置为将表示交换问题的qubo公式116的数据传输给一个或多个量子计算资源，交换问题由输入数据102表示。例如，qubo公式器106可以将要被解决的交换问题的qubo公式116直接提供给一个或多个量子计算资源。
量子计算资源可以包括量子退火器计算资源，例如量子退火器110a。量子退火器是被配置为执行量子退火的设备，量子退火是用于使用量子隧穿在给定的候选状态集上找到给定目标函数的全局最小值的过程。量子隧穿是一种量子力学现象，其中量子力学系统克服了经典描述的系统无法克服的、能量格局中的局部障碍。一些量子退火器设备执行被称为绝热量子计算的量子退火的子类，其依赖于绝热定理来执行计算。
如果以可接受的格式将问题公式化，则量子退火器设备可以解决问题。例如，量子退火器设备可以通过将qubo公式映射到量子退火器设备的量子位网络中来解决问题的一些qubo公式。
量子计算资源可以包括一个或多个量子门处理器，例如量子门处理器110b。量子门处理器包括一个或多个量子电路，即，用于量子计算的模型，其中使用对一定数目的量子位(量子位)进行操作的量子逻辑门序列来执行计算。
量子门处理器可以被用来解决某些优化问题，例如可以被公式化为qubo问题的问题。例如，一些量子门处理器可以通过使用门模型来模拟对应的绝热量子退火过程来解决qubo问题。例如，与使用量子退火器设备直接执行对应的绝热量子退火过程相比，这可能是有利的，因为并非所有的量子退火器设备都可以实现表示优化问题的物理量子系统。例如，一些量子退火器设备可能不提供解决优化问题所必需的物理相互作用。在这些示例中，可以将描述优化问题的哈密顿函数(hamiltonian)分解成单量子位或多量子位量子门的序列，并且通过在量子位的寄存器上应用单量子位或多量子位门的序列并且随后测量量子位的寄存器，可以获得对优化问题的解决方案。
一个或多个量子计算资源被配置为处理接收到的数据以生成表示对交换问题的解决方案的输出数据118，该一个或多个量子计算资源接收所传输的、表示交换问题的qubo公式116的数据，交换问题由输入数据102表示。一个或多个量子计算资源被配置为将所生成的输出数据118提供给系统100，例如提供给经典后处理器108。
系统100被配置为从一个或多个量子计算资源接收输出数据118。经典后处理器108被配置为处理接收到的输出数据118。处理输出数据118可以包括：基于对交换问题的解决方案，确定要被采取的一个或多个动作，例如资源的交换。
系统100被配置为输出表示可以被采取的、所确定的动作的数据112。例如，系统100可以将数据112提供给中介方(broker)或包括中介方，该中介方基于输出数据来发起动作。
图2是用于使用量子计算资源来解决交换问题的示例过程200的流程图。为了方便起见，过程200将被描述为由位于一个或多个位置的一个或多个经典或量子计算设备的系统来执行。例如，根据本说明书被适当地编程的图1的示例系统100可以执行过程200。
系统接收表示交换问题的数据(步骤202)。接收到的数据可以包括表示交换问题参与方的数据，其中每个参与方例如在不使用交换介质的情况下提供资源或服务以交换其他资源或服务。接收到的数据还可以包括表示对交换问题参与方之间的交换的约束的数据。接收到的数据还可以包括指定要被解决的交换问题的数据。
在一些实现中，交换问题可以是肾脏交换问题。在这些实现中，交换问题参与方可以包括多个捐献者-接受者对，其包括(i)愿意捐献肾脏的捐献者以及(ii)需要捐献者肾脏的患者。捐献者和接受者可以具有不同的匹配级别。例如，如果第一捐献者-接受者对中的捐献者提供的肾脏与第二捐献者-接受者对中的接受者具有相同的类型或具有其他相容的特性，例如成功移植(无器官排斥的功能性)机会很大，则第一对中的捐献者与第二对中的接受者可能具有高匹配级别。相反地，如果第一对中的捐献者提供的肾脏是不同类型的或具有其他不相容的特性，例如成功移植的机会不大，则第一对中的捐献者与第三捐献者-接受者对中的接受者可能具有较低匹配级别。如果成功种植的机会非常低，例如低于预定阈值，则捐献者-接受者对可以被称为不相容对，因为该捐献者将永远不被允许向该接受者捐献肾脏。在本说明书中，不相容的捐献者-接受者对是指匹配级别低的捐献者-接受者对。
在交换问题是肾脏交换问题的实现中，对交换问题参与方之间的交换的约束可以包括第一约束，其确保没有肾脏被捐献超过一次。另外，约束还可以包括第二约束，其确保仅当不相容的捐献者-接受者对中的患者从另一捐献者接收肾脏时，该捐献者-接受者对的捐献者才捐献肾脏。
在一些实现中，系统可以将接收到的表示交换问题的数据建模为图。例如，系统可以进行如下建模：要被解决的肾脏交换问题可以被表示为顶点和有向加权边的图，其中顶点表示不相容的或不完全匹配的捐献者-接受者对，边表示相容的或更完全匹配的捐献者-接受者对，并且边权重表示相容的或更完全匹配的捐献者-接受者对的医学益处。该系统还可以从该图中确定捐献者-接受者对的一个或多个不相交的循环，其增加了相关联的肾脏移植的整体医学益处。在一些情况下，一个或多个不相交的循环中的每一个循环中的捐献者-接受者对的数目低于预定阈值，例如，基于可用医学资源确定的阈值。例如，在一些情况下，可能难以组织和同步为大量捐献者-接受者对实施肾脏交换所需的医学资源，例如外科医生、助手、手术室。
例如，可以在有向图g(v,e)上定义肾脏交换网络，其中顶点集v＝{v1,v2,...,vn}中的每个元素vi表示第i个患者-捐献者对，其中捐献者愿意将他/她的不相容肾脏捐献给患者，并且边集e中的每个元素对应于一个有序对(i,j)，其指示从顶点vi到顶点vj的方向性边。用ei,j表示对(i,j)的边，并且如果vi的患者与vj的捐献者的身体类型相容，则假定ei,j在e中，这给出：
e＝{ei,j|vi患者与vj的捐献者身体类型相容，1≤i,j≤n}(1)
由系统定义的图的边可以是加权边。可以存在被指派给不同边的不同权重，其中边的权重表示每个个体移植的效用或优先级。在本说明书中，wi,j表示边ei,j的权重，其中wi,j>0归因于正效用，并且c表示g(v,e)中的循环集，其中每个c∈c是循环中所有顶点的集。一个循环表示涉及该循环中的患者-捐献者对的成功肾脏交换。
g(v,e)上的肾脏交换问题的目的是找到不相交(因为每个患者-捐献者对只能捐献一个肾脏且接收一个肾脏)循环集
其以以下约束为条件
系统从接收到的数据中确定交换问题的整数编程公式(步骤204)。要被解决的交换问题的整数编程公式可以包括要被最大化的目标函数和包括等式和不等式约束的一个或多个约束。下面描述了肾脏交换问题的整数编程公式的示例。
作为示例整数编程问题的肾脏交换问题
为了将上述肾脏交换问题映射到整数编程问题，系统引入以下变量。对于匹配c*的任何实例，当且仅当ei,j∈e并且ei,j被c*中的循环覆盖时，令xi,j＝1，否则xi,j＝0。注意，在任何匹配中，如果边ei,j不存在(即
以下是解决肾脏交换问题的示例整数编程问题：
关于约束
等式(5)保证：每当不存在从vi到vj的边时，xi,j＝0。等式(6)和(7)用以确保：每个顶点在其处于一个循环中时都具有一个进入边和一个出去的边(在形成循环的路径中不存在不连续性)，并且每个顶点最多被穿越一次(所有循环不相交)。
系统将交换问题的整数编程公式映射到交换问题的二次无约束二进制优化(qubo)公式(步骤206)。图3是用于将交换问题的整数编程公式映射到交换问题的qubo公式的示例过程300的流程图。为了方便起见，过程300将被描述为由位于一个或多个位置的一个或多个经典或量子计算设备的系统执行。例如，根据本说明书被适当地编程的图1的示例系统100可以执行过程200。
系统将要被最大化的目标函数映射到要被最小化的qubo目标函数(步骤302)。系统将惩罚项添加到要被最小化的qubo目标函数，其中基于一个或多个约束来确定惩罚项(步骤308)。
在一些实现中，系统确定惩罚项。这可以包括确定针对交换问题的整数编程公式中的等式约束和不等式约束的惩罚项(步骤304和306)。
确定针对等式约束的惩罚项(步骤304)可以包括：对于每个等式约束：在约束被满足时将约束表示为等于零的等式，并且在约束不被满足时将约束表示为等于严格正值的等式，将等式乘以权重来生成对应的部分惩罚项，并且将所生成的部分惩罚项包括在惩罚项中。
确定针对不等式约束的惩罚项(步骤306)可以包括：将不等式约束公式化为包括松弛变量的等式约束，其中每个松弛变量是二进制变量，并且使用包括松弛变量的等式约束如上所述地确定惩罚项。
下面描述将等式(4)-(7)给出的肾脏交换问题的整数编程公式映射到交换问题的二次无约束二进制优化(qubo)公式。
到qubo问题的示例映射化简
回想一下，qubo问题的目标函数采取以下形式：
g(x)＝xtmx(8)
其中x表示具有二进制变量x1,x2...,的列向量，并且m表示给定的对称矩阵。因此，通过扩展上述等式(8)，可以将其写为仅包含二次项的以下形式：
等式(9)也可以被写为g(x)＝∑imi,ixi ∑i＜j(2mi,j)xixj(10)
因为由于xi是二进制，所以x2＝xi。此处，只存在线性和二次交叉项。
qubo问题的标准形式是目标函数的最小化。因此，等式(4)可以用其qubo标准形式被写为：
当系统接收到的数据包括等式约束时，例如b＝c，其中b表示变量的函数，则将足够大的惩罚添加到目标函数，使得不允许b>c或b<c。也就是说，w·(b-c)2可以被添加到目标函数中。因为由于等式(5)-(7)仅涉及二进制变量和整数系数，在这种情况下(b-c)2为0或≥1，因此w可以被选择为足够大，使得在约束不被满足时要付出较大惩罚。
例如，w可以被选择为等于
因此，当不满足约束条件时，它将施加幅度≥w的正惩罚，其大于
也就是说，考虑具有惩罚的新目标函数
当不满足约束时，新目标函数将具有值>0，并且因此不会处于最小值，因为平凡(trivial)分配(无交换的实例，其中对于所有i，xi＝0)给出了为0的值。
使用以上详述的思想，可以将等式(5)-(7)给出的约束并入到目标函数等式(11)中，如下。
对于由等式(5)给出的约束，对于不存在从vi到vj的边的每个对(i,j)，添加如下惩罚
对于由等式(6)给出的约束，对于每个i∈{1,2,...,n}，添加w倍的惩罚
(∑jxi,j-∑jxj,i)2＝(∑jxi,j)2 (∑jxj,i)2-2∑j,kxi,jxk,i＝∑j(xi,j xj,i) 2∑k＜j(xk,ixj,i xi,kxi,j)-2∑j,kxi,jxk,i(15)
对于由等式(7)给出的约束，因为约束是不等式而不是等式，所以过程更加复杂。将不等式约束映射到等式约束的一种典型方式是引入“松弛”变量，对于每个i∈{1,2,...,n}，引入新的二进制变量
yi∈{0,1}(16)
回想一下，等式(7)的不等式约束为∑jxi,j≤1(17)
以下等式(18)中给出的约束是由等式(17)给出的约束的等效约束
∑jxi,j-yi＝0，yi∈{0,1}.(18)
结果：对于固定的i，令yi∈{0,1}为自由变量，则约束∑jxi,j≤1等效于约束∑jxi,j-yi＝0。
结果的证明：为了表明两个约束是等效的，已证明它们相互暗示。
首先，令∑jxi,j≤1被满足。然后，由于xi,j≥0，0≤∑jxi,j≤1。
因此∑jxi,j＝0或1，并且yi可以分别被选择为0或1，使得∑jxi,j-yi＝0。
为了表明相反情况，令∑jxi,j-yi＝0被满足。因为yi≤1，所以∑jxi,j＝yi≤1。(q.e.d.)
因此，通过引入二进制变量
对于那些约束中的每一个约束，添加w倍的惩罚
根据等式(14)、(15)和(20)，应当被添加到目标函数的总惩罚为w·f(x,y)，其中x是具有元素xi,j的n×n矩阵，并且y是具有元素yi的n向量，其中
最后，标准qubo形式的目标函数为
其中f(x,y)由等式(21)给出。
等式(22)给出针对线性项xi,j和yi及其乘积(二次)项的qubo系数。因此，可以计算出针对该qubo问题的系数矩阵m(参见等式8)。变量的维数(或数目)乍一看是|v|2 |v|，但是由于对于
解决方案是在目标函数被最小化时的xi,j。
在一些实现中，为了实践性，可能存在额外的期望约束，其是对循环长度的固定上边界。这是由于以下事实：当涉及过多的参与方时，肾脏交换要困难得多。
对此的一种解决方案是将所有边权重wi,j减小适当的量∈>0，使得所有的新权重
返回图2，系统向量子计算资源提供交换问题的qubo公式。系统从量子计算资源获得表示对交换问题的解决方案的数据(步骤208)。在一些实现中，量子计算资源可以是量子退火计算机。在这些实现中，可以使用量子绝热计算来计算对交换问题的解决方案。在其他实现中，量子计算资源可以是基于门的通用量子计算机。在这些实现中，可以使用量子近似优化算法或其他量子经典混合变分算法来计算对交换问题的解决方案。
在一些实现中，系统可以执行对表示从量子计算资源获得的、对交换问题的解决方案的数据的经典的后处理。在由以上等式(22)给出的qubo公式中，经典的后处理可以包括在xi,j变量上应用恒等算子，并且忽略yi变量。
系统基于所获得的表示对交换问题的解决方案的数据来发起动作(步骤210)。发起动作可以包括：基于对交换问题的解决方案来发起资源或服务的交换。例如，当交换问题是肾脏交换问题时，发起动作可以包括：基于对交换问题的解决方案来发起多个肾脏的移植。
本说明书中描述的数字和/或量子主题的实现以及数字功能性操作和量子操作可以以数字电子电路装置、合适的量子电路装置或更一般的量子计算系统、以有形地体现的数字和/或量子计算机软件或固件、以包括在本说明书中公开的结构及其结构等同物的数字和/或量子计算机硬件或者以它们中的一个或多个的组合来实现。术语“量子计算设备”可以包括但不限于量子计算机、量子信息处理系统、量子密码系统或量子模拟器。
本说明书中描述的数字和/或量子主题的实现可以被实现为一个或多个数字和/或量子计算机程序，即，在有形的非暂态存储介质上编码的数字和/或量子计算机程序指令的一个或多个模块，以用于由数据处理装置执行或控制数据处理装置的操作。该数字和/或量子计算机存储介质可以是机器可读存储设备、机器可读存储基板、随机或串行存取存储器设备、一个或多个量子位或它们中的一个或多个的组合。备选地或附加地，程序指令可以被编码在能够编码数字和/或量子信息的人工生成的传播信号上，例如机器生成的电、光或电磁信号，其被生成以对数字和/或量子信息进行编码，以用于传输到合适的接收器装置，以由数据处理装置执行。
术语量子信息和量子数据是指由量子系统携带、保持或存储在量子系统中的信息或数据，其中最小的非平凡系统是量子位，即定义量子信息的单位的系统。应当理解，术语“量子位”涵盖了在对应的上下文中可以适当地近似为两个级别系统的所有量子系统。这样的量子系统可以包括例如具有两个级别或更多个级别的多级别系统。举例来说，这样的系统可以包括原子、电子、光子、离子或超导量子位。在许多实现中，计算基态被标识为基态和第一激发态，但是，应当理解，用较高级别的激发态来标识计算态的其他设置是可能的。术语“数据处理装置”是指数字和/或量子数据处理硬件，并且涵盖用于处理数字和/或量子数据的各种装置、设备和机器，例如包括可编程数字处理器、可编程量子处理器、数字计算机、量子计算机、多个数字和量子处理器或计算机及其组合。装置还可以是或进一步包括专用逻辑电路装置，例如fpga(现场可编程门阵列)、asic(专用集成电路)或量子模拟器，即被设计为模拟或产生有关特定量子系统的信息的量子数据处理装置。特别地，量子模拟器是一种专用量子计算机，其不具有执行通用量子计算的能力。除硬件之外，该装置还可以可选地包括为数字和/或量子计算机程序创建执行环境的代码，例如，构成处理器固件、协议栈、数据库管理系统、操作系统或它们中的一个或多个的组合的代码。
数字计算机程序也可以被称为或被描述为程序、软件、软件应用、模块、软件模块、脚本或代码，其可以以任何形式的编程语言来编写，包括经编译或经解释的语言、或声明性或过程性语言，并且它可以以任何形式被部署，包括作为独立程序或作为模块、组件、子例程或适用于在数字计算环境中使用的其他单元。量子计算机程序也可以被称为或被描述为程序、软件、软件应用、模块、软件模块、脚本或代码，其可以以任何形式的编程语言来编写，包括经编译或经解释的语言、或声明性或过程性语言，并且被转换成合适的量子编程语言，或者可以以量子编程语言(例如qcl或quipper)来编写。
数字和/或量子计算机程序可以但不必对应于文件系统中的文件。程序可以被存储在保存其他程序或数据(例如，被存储在标记语言文档中的一个或多个脚本)的文件的一部分中、专用于所讨论的程序的单个文件中、或多个协调文件中，例如存储一个或多个模块、子程序或代码的各部分的文件中。可以将数字和/或量子计算机程序部署为在一个数字计算机或一个量子计算机上执行，或者在位于一个站点处或跨多个站点分布且通过数字和/或量子数据通信网络互连的多个数字计算机和/或量子计算机上执行。量子数据通信网络应当被理解为是可以使用例如量子位的量子系统来传输量子数据的网络。通常，数字数据通信网络不能传输量子数据，但是量子数据通信网络可以传输量子数据和数字数据二者。
本说明书中描述的过程和逻辑流可以由一个或多个可编程数字计算机和/或量子计算机执行，其适当地与一个或多个数字处理器和/或量子处理器一起操作，执行一个或多个数字和/或量子计算机程序以通过对输入的数字和量子数据进行操作并且生成输出来执行各功能。过程和逻辑流也可以由专用逻辑电路装置(例如，fpga或asic)或量子模拟器、或者由专用逻辑电路装置或量子模拟器和一个或多个经编程的数字和/或量子计算机的组合来执行，或者也可以将装置实现为专用逻辑电路(例如，fpga或asic)或量子模拟器、或者专用逻辑电路装置或量子模拟器和一个或多个经编程的数字和/或量子计算机的组合。
对于被“配置为”执行特定操作或动作的一个或多个数字和/或量子计算机的系统，意味着该系统已在其上安装了软件、固件、硬件或在操作中使系统执行操作或动作的其组合。对于要被配置为执行特定操作或动作的一个或多个数字和/或量子计算机程序，意味着一个或多个程序包括指令，该指令在由数字和/或量子数据处理装置执行时使装置执行操作或动作。量子计算机可以从数字计算机接收指令，该指令在由量子计算装置执行时使装置执行操作或动作。
适用于执行数字和/或量子计算机程序的数字和/或量子计算机可以基于通用或专用数字和/或量子处理器或两者，或任何其他种类的中央数字和/或量子处理单元。通常，中央数字和/或量子处理单元将从只读存储器、随机存取存储器或适合用于传输例如光子的量子数据的量子系统、或其组合接收指令以及数字和/或量子数据。
数字和/或量子计算机的基本元件是用于进行或执行指令的中央处理单元以及用于存储指令和数字和/或量子数据的一个或多个存储器设备。中央处理单元和存储器可以由专用逻辑电路装置或量子模拟器补充或并入在其中。通常，数字和/或量子计算机还将包括或可操作地耦合，以从用于存储数字和/或量子数据的一个或多个大容量存储设备接收数字和/或量子数据，或将数字和/或量子数据传送到一个或多个大容量存储设备，或者既从一个或多个大容量存储设备接收数字和/或量子数据又将数字和/或量子数据传送到一个或多个大容量存储设备，大容量存储设备例如磁盘、磁光盘、光盘或适合用于存储量子信息的量子系统。但是，数字和/或量子计算机不需要具有这样的设备。
适合用于存储数字和/或量子计算机程序指令和数字和/或量子数据的数字和/或量子计算机可读介质包括所有形式的非易失性数字和/或量子存储器、介质和存储器设备，举例来说，包括半导体存储器设备，例如eprom、eeprom和闪存存储器设备；磁盘，例如内部硬盘或可移除磁盘；磁光盘；cd-rom和dvd-rom磁盘；和量子系统，例如被俘获的原子或电子。应当理解，量子存储器是可以以高保真度和高效性长时间存储量子数据的设备，例如光-物质接口，其中光被用于传输，并且物质用于存储和保留量子数据的诸如叠加或量子相干性之类的量子特征。
对本说明书中描述的各种系统或其各部分的控制可以在数字和/或量子计算机程序产品中被实现，该产品包括存储在一个或多个非暂态机器可读存储介质上并且在一个或多个数字和/或量子处理设备上可执行的指令。本说明书中描述的系统或其各部分可以各自被实现为一种装置、方法或系统，其可以包括一个或多个数字和/或量子处理设备以及用以存储可执行指令来执行本说明书中所述操作的存储器。
虽然本说明书包含许多特定的实现细节，但是这些不应被解释为对所要求保护的范围的限制，而应被解释为可以特定于特定实现的特征的描述。在本说明书中，在分离的实现的上下文中描述的某些特征也可以在单个实现中组合实现。相反，在单个实现的上下文中描述的各种特征也可以分离地在多个实现中或以任何合适的子组合来实现。而且，尽管以上可以将特征描述为以某些组合起作用并且甚至最初如此要求保护，但是在一些情况下可以从组合中切除所要求保护的组合中的一个或多个特征，并且所要求保护的组合可以涉及子组合或子组合的变体。
类似地，虽然在附图中以特定顺序描绘了操作，但是这不应被理解为要求以所示的特定顺序或以连续的顺序执行这样的操作，或者不应被理解为执行所有图示出的操作以实现期望的结果。在某些情形中，多任务和并行处理可能是有利的。此外，在上述实现中的各种系统模块和组件的分离不应被理解为在所有实现中都需要这种分离，并且应当理解，所描述的程序组件和系统通常可以被集成在单个软件产品或系统中或者被封装成多个软件产品。
已经描述了本主题的特定实现。其他实现在所附权利要求的范围内。例如，权利要求中记载的动作可以以不同的顺序来执行并且仍然实现期望的结果。作为一个示例，附图中描绘的过程不一定需要所示的特定顺序或连续顺序来实现期望的结果。在一些情况下，多任务和并行处理可能是有利的。
1.一种计算机实现的方法，包括：
接收表示交换问题的数据；
从接收到的所述数据确定所述交换问题的整数编程公式；
将所述交换问题的所述整数编程公式映射到所述交换问题的二次无约束二进制优化(qubo)公式；
从量子计算资源获得表示对所述交换问题的解决方案的数据；以及
基于表示对所述交换问题的解决方案的所获得的所述数据来发起动作。
2.根据权利要求1所述的方法，其中所述交换问题的所述整数编程公式包括：
要被最大化的目标函数；以及
一个或多个约束，包括等式约束和不等式约束。
3.根据权利要求2所述的方法，其中将所述交换问题的所述整数编程公式映射到所述交换问题的qubo公式包括：
将要被最大化的所述目标函数映射到要被最小化的qubo目标函数；以及
将惩罚项添加到要被最小化的所述qubo目标函数，其中所述惩罚项基于所述一个或多个约束而被确定。
4.根据权利要求3所述的方法，还包括确定所述惩罚项，包括：
对于每个等式约束：
当所述约束被满足时，将所述约束表示为等于零的等式，并且当所述约束不被满足时，将所述约束表示为等于严格正值的等式；
将所述等式乘以权重，以生成对应的部分惩罚项；以及
将所生成的所述部分惩罚项包括在所述惩罚项中。
5.根据权利要求4所述的方法，还包括：
对于每个不等式约束：
将所述不等式约束公式化为包括松弛变量的等式约束，其中每个松弛变量是二进制变量；
使用包括松弛变量的所述等式约束来确定所述惩罚项。
6.根据权利要求1所述的方法，其中当所述量子计算资源包括量子退火计算机时，可选地，其中对所述交换问题的所述解决方案使用量子绝热计算来计算。
7.根据权利要求1所述的方法，其中当所述量子计算资源包括基于门的通用量子计算机时，可选地，其中对所述交换问题的所述解决方案使用量子近似优化方法或其他量子经典混合变分算法来计算。
8.根据权利要求1所述的方法，还包括：执行对从所述量子计算资源获得的、表示对所述交换问题的解决方案的所述数据的经典的后处理。
9.根据权利要求1所述的方法，其中基于表示对所述交换问题的解决方案的所获得的所述数据来发起动作包括：基于对所述交换问题的所述解决方案来交换资源或服务。
10.根据权利要求1所述的方法，其中接收到的所述数据包括表示以下的数据：
交换问题参与方，其中每个参与方在不使用交换介质的情况下提供资源或服务以交换其他资源或服务；
对交换问题参与方之间的交换的约束；以及
所述交换问题。
11.根据权利要求10所述的方法，其中所述交换问题包括肾脏交换问题。
12.根据权利要求11所述的方法，其中所述交换问题参与方包括不相容的捐献者-接受者对，其中每个不相容的捐献者-接受者对包括：(i)愿意捐献肾脏的捐献者，以及(ii)需要与所述捐献者提供的捐献者肾脏类型不同的捐献者肾脏的患者。
13.根据权利要求11所述的方法，其中对交换问题参与方之间的交换的约束包括：
第一约束，所述第一约束确保没有肾脏被捐献超过一次；
第二约束，所述第二约束确保：仅当不相容的捐献者-接受者对中的患者接收来自另一捐献者的肾脏时，所述不相容的捐献者-接受者对中的捐献者才捐献肾脏。
14.根据权利要求11所述的方法，还包括：
将所述肾脏交换问题建模为顶点和有向加权边的图，其中
顶点表示不相容的捐献者-接受者对，
边表示相容的捐献者-接受者对；并且
边权重表示相容的捐献者-接受者对的医学益处；以及
确定增加相关联的肾脏移植的整体医学益处的、捐献者-接受者对的一个或多个不相交的循环。
15.根据权利要求14所述的方法，其中所述一个或多个不相交的循环中的每个不相交的循环中的捐献者-接受者对的数目低于预定阈值。
16.根据权利要求11所述的方法，其中基于表示对所述交换问题的解决方案的所获得的所述数据来发起动作包括：基于对所述交换问题的所述解决方案来移植多个肾脏。
17.一种系统，包括：
经典处理器；
量子计算设备，所述量子计算设备与所述经典处理器进行数据通信；
其中所述经典处理器和所述量子计算设备被配置为执行操作，所述操作包括：
接收表示交换问题的数据；
从接收到的所述数据确定所述交换问题的整数编程公式；
将所述交换问题的所述整数编程公式映射到所述交换问题的二次无约束二进制优化(qubo)公式；
从所述量子计算设备获得表示对所述交换问题的解决方案的数据；以及
基于表示对所述交换问题的解决方案的所获得的所述数据来发起动作。
18.根据权利要求17所述的系统，其中要被解决的所述交换问题的所述整数编程公式包括：
要被最大化的目标函数；以及
一个或多个约束，包括等式约束和不等式约束。
19.根据权利要求18所述的系统，其中将所述交换问题的所述整数编程公式映射到所述交换问题的qubo公式包括：
将要被最大化的所述目标函数映射到要被最小化的qubo目标函数；以及
将惩罚项添加到要被最小化的所述qubo目标函数，其中所述惩罚项基于所述一个或多个约束而被确定。
20.根据权利要求19所述的系统，还包括确定所述惩罚项，包括：
对于每个等式约束：
当所述约束被满足时，将所述约束表示为等于零的等式，并且当所述约束不被满足时，将所述约束表示为等于严格正值的等式；
将所述等式乘以权重，以生成对应的部分惩罚项；以及
将所生成的所述部分惩罚项包括在所述惩罚项中。
技术总结