英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

arXiv:1804.02733v2 [quant-ph] 11 Jun 2018

用于素因数分解的量子退火

Shuxian Jiang1, Keith A. Britt2, Alexander J. McCaskey2, Travis S. Humblelowast;2, and Sabre Kaisdagger;1,3 1Department of Computer Science, Purdue University, West Lafayette, IN 47906

2Quantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, TN 37831 3Department of Chemistry, Physics and Birck Nanotechnology Center, Purdue University, West Lafayette, IN 47906

摘要

我们开发了一个框架，通过首先将其作为优化函数编写，然后使用辅助变量将k位耦合（k ge; 3)）项转换为二次项，将任意整数分解问题转换为可执行的Ising模型。 我们的资源有效方法使用O(log2(N))二进制变量（qubits）来查找整数N的因子。 我们将介绍如何分别使用4,12,59和94个逻辑量子位对15,143,59989和376289进行分解。 使用D-Wave 2000Q测试该方法以找到嵌入并确定给定复合数的素因子。 该方法是通用的，并且可以用于在可用量子位数增加时考虑更大的整数。

1. 简介

整数分解问题将整数N减少到其素因子p和q。这个问题在数论中是基础，对加密数据存储和通信有广泛的影响[29]。虽然找到整数因子是一个计算难题，但它并不相信属于NP难问题的类。然而，在实际意义上，所有已知的经典因子算法是确定性的并且没有未经证实的假设需要在log N中具有时间指数。因此，整数因子分解问题被用作许多加密方法的基本硬度假设，包括广泛部署的RSA密码系统。用于整数因子分解的最快的，已知的经典算法是通用数字场筛选方法[16]，其在相对于整数N所需的操作数量中指数地缩放。

量子计算理论已经显示出减少解决某些问题所需的操作数量的潜力，并且已经进行了许多努力来开发可以解决整数因子化问题的量子计算机。与经典确定性方法相比，解决因子分解问题的量子方法可以被视为概率方法。 Shor算法可能是最着名的整数分解量子算法。为了计算整数N，Shor的算法需要多项式运算次数[27]，从而提供超过一般数筛的指数加速。 Shor的算法通过将因子化问题简化为订单查找问题来实现。已经进行了许多尝试以在量子计算硬件上实现Shor算法。 Vandersypen等人。 [28]在分子中使用七个自旋-1 / 2核作为量子位来计算N = 15，而Lanyon等人。 [15]，Lu等人。 [17]，和Politi等人。 [25]已经使用光子系统实现了Shor算法的编译版本，用于分解N =15.Martın-Lopez等。 [19]使用量子位回收计算21，Lucero等。 [18]使用超导量子比特来计算因子15.Geller等人[10]使用Shor算法的简化版本来计算费马素数3,5,17,257和65537的乘积.Shor算法不仅可用于求解整数分解问题，还可用于解决其他定序问题。最近，Grosshans等[11]提出使用量子阶次寻找算法分解安全半素数，降低了失效概率

在量子计算的电路模型中提出了Shor用于阶次寻找的量子算法。但另一个同样强大的量子计算模型（直到多项式简化）是量子绝热计算模型[9]（QAC），它也可以用来解决整数分解问题。彭等人。 [24]已经开发出使用QAC分解21的方法，他们在三比特的核磁共振量子处理器中实现了这种算法，而Xu等人。 [30]使用相似的核磁共振技术分析143。 Schaller等人的一种新方法。 [26]使用乘法表来产生一组方程，并使用它们来产生二次成本函数。 Dridi等。 [8]使用Grouml;bner碱进一步优化了这种方法，减少了所需的辅助变量和方程的数量。

在这篇文章中，我们介绍了一种使用称为量子退火的QAC变体求解整数分解问题的新方法。我们的方法基于将问题直接数学转换为Ising Hamiltonian，这可以使用当前可用的量子处理器来实现。接下来，为了考虑硬件约束，我们引入了一种修改的乘法方法，该方法在不增加所需的量子位数的情况下减小了成本函数中系数的范围。该方法是通用的，资源有效的，并且不依赖于临时计算。

量子退火利用量子涨落解决了优化问题[13]。量子绝热计算（QAC），由Farhi等人开发。 [9]，在给定复数哈密顿量的情况下接近相同的任务，其基态编码优化问题的解。这种计算始于一个简单的，充分表征的哈密顿量的基态，然后绝热地演化为复数问题哈密顿量。根据绝热定理[21]，系统状态也将演变问题哈密顿量的基态，前提是进化足够慢以防止对任何高位状态的激发。在退火过程结束时，测量的量子位将在有限的确定度内（由于封闭系统内的噪声）编码问题的最优解。

量子系统的时间依赖哈密顿量是通过组合初始哈密顿量和最终哈密顿量[1]给出的。

t t

H(t) = (1 minus; T )H_B T H_P . (1)

这里 H_B是最初的哈密顿量，具有众所周知且易于构造的基态，我们认为它具有一般形式

H_B = minus; Sigma; sigma;⁽ⁱ⁾

x

(2)

与Pauli算子sigma;x定义x基。 哈密顿量的HP是最终的哈密顿量，它的基态编码

优化问题的给定实例的解决方案。 找到整数的素因子将被映射到一般形式的最终伊辛哈密顿量

HP = Sigma; hisigma;(i) Sigma; Jijsigma;(i)sigma;(j)

z

z

z

(3)

其中sigma;z定义了z基和局部场hi和耦合Jij定义了分解问题实例。

HP提供系统的总能量。

物理系统的时间相关哈密顿量H（t）根据Schrouml;dinger方程演化

d

idt |psi;(t)) = H(t) |psi;(t)) (4)

其中|psi;（t））是系统在任何时间tisin;[0，T]的状态。 设|phi;i（t））是H（t）的第i个瞬时本征态，即H（t）|phi;i

（t））= Ei（t）|phi;i（t））在整个演化过程中成立。 如果系统初始化为基态

|phi;0（t = 0）），则演化进行得足够慢以避免激励到更高位的本征态，例如|phi;1（t））。 最终系统将在瞬时地

面本征态|phi;0（t = T））中准备。

因子N = pq的直接方法，其中p和q是素数是让 l1 = |log2(p)int;, l2 = |log2(q)int;，并且，在不失一般性的情况下，我们

取 p = (x_l1 minus;1x_l1 minus;2...x₁1)₂, q = (x_l1 l2 minus;2x_l1 l2 minus;3...x_l1 1)₂，并且 l₁ gt; l₂

其中xi是二进制数。 所以 且

我们可以定义成本函数 。 为了将成本函数的阶数减少到二次，我们

需要 辅助变量，如果 辅助变量的值是

加上变量为了表示这些因素，我们使用

作为二进制变量，当p=q时我们也能让

我们通过N = 15的因子分解来说明这种直接方法。

这意味着p最多为2位，q最多为3位，那么我们定义p =（x11）2 = x1times;2 1，q =（x2x31）2 = x2times;2

2 x3times;2 1，xiisin;{0,1}}，因为p和q是素数。 目标函数f（x1，x2，x3）=（N-pq）2

最小化有以下内容

现在，我们将3局部项减少到2局部项如下[2]：对于x，y，zisin;{0,1}，xy = z iff xy-2xz-2yz 3z = 0，和iff xy-2xz-2yz 3zgt; 0.也很容易检查x1x2x3 = x4x3 2（x1x2 - 2x1x4 - 2x2x4

3x4）如果x4 = x1x2，x1x2x3 lt;x4x3 2（x1x2 - 2x1x4 - 2x2x4 3x4），如果x4 x1x2。 因此，x1x2x3术语

可以通过用x4替换x1x2，加上约束条件作为惩罚项，将其转换为二次形式：

min（x1x2x3）= min（x4x3 2（x1x2 - 2x1x4 - 2x2x4 3x4）（5）这里我们通过引入一个新变量并将约束条件替换为惩罚项来将3局部项转换为2局部项。 原始函数。我们获得（参见附录A.1了解更多详细信息）一个Ising函数，该函数将使用本地字段hT和耦合J进行优化

• 1. 结果

我们使用D-Wave 2000Q量子退火炉来演示该方法。 为了解决D-Wave硬件上的问题，我们需要将问题哈密顿量嵌入到嵌合硬件图上，同时保持能量最小化目标函数[12]。 这个过程要求D-Wave系统的用户解决两个问题：轻微嵌入[4,14]和参数设置[5]。

在ttj（V j，Ej）中的tt（V，E）的次要嵌入由映射phi;：定义，使得每个顶点被映射到ttj的连接子树以及if 然后存在t iu, iv isin; G0，使得和。 如果在G和之间存在这样的映射，我们说G是的次要，我们使用来表示这种关系。

在参数设置中，我们在次要嵌入图中分配每个节点和每个边，使得：（1）对于由相同顶点i扩展的树Ti中的每个节点，其值满足，（2）对于每个边 在由相同顶点i扩展的树Ti中，值Jik，ikt需要足够大以确保对应于相同逻辑量子位的所有物理量子位具有相同值并且（3）对于次要中的每个边缘 嵌入原始图形中的图形，我们可以使用相同的Jij值。因子15和21的实验结果如图1所示。这些图显示了从最低能量到最高能量（从左到右）的解码解。在某些情况下，观察到的比特被解码为正确的

因素。例如，N = 21有几个（3,7）解。只有第一个（最左边）对应于最低点

能源状态。其他一直是更高能量的解决方案。为了在D波机器上通过合理地减少控制硬件位精度来计算更大的数量并执行量子退火，我们引入了修改的乘法表方法。修正的乘法表方法允许我们减少用作量子位和耦合器的系数的Ising参数值的范围，从而减少控制硬件满足最终哈密顿量所需的精度位。修改的乘法表方法使用局部最小化的乘积。 p和q的位串中的各个位，以减少最终哈密顿量的全局最小化所需的变量数。此外

• • 1. 用退火时间200分解15 (b) 用退火时间200分解21

图1：D-Wave机器的实验结果：获得不同解决方案的。例如，x轴中的（3,5）表示15的因子分解是3乘以5，y轴中的数字表示获得该因子分解的速率。

减少描述最终哈密顿量所需的逻辑量子位数，该方法还缩小了描述最终哈密顿量所需的系数值范围。系数范围的详细分析见附录A.5。值得注意的是，修改后的乘法表方法并没有消除将4体和3体项减少为二次项的需要，但确实减少了这些较高体项的数量，使我们可以将它们嵌入到D-Wave硬件。我们使用近似log（N）二进制变量来表示

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20054]，资料为PDF文档或Word文档，PDF文档可免费转换为Word