量子计算算法:离散对数和因式分解(Peter Shor)

煤油灯科技2022-08-16 09:18

摘要

计算机通常被认为是一种通用的计算设备;也就是说,它被认为能够模拟任何物理计算设备,计算时间成本最多为多项式因子。如果把量子力学考虑在内,这一结论是否仍然成立也不清楚。以David Deutsch为首的几位研究人员开发了量子力学计算机的模型,并研究了它们的计算特性。本文给出了在量子计算机上寻找离散对数和因式分解整数的 Las Vegas 算法,该算法采用多个步骤,输入大小为多项式,例如要因式分解的整数的位数。这两个问题在经典计算机上通常被认为是困难的,并且已被用作几个提议的密码系统的基础。 (因此,我们给出了量子密码分析的第一个例子。)

1.引言

自从量子力学发现以来,人们发现量子力学中概率定律的行为是违反直觉的。由于这种行为,量子力学现象的行为与我们所熟悉的经典物理现象截然不同。费曼似乎是第一个提出这对计算有什么影响的人。他论证了为什么这种行为会使在经典(或冯·诺伊曼)计算机上模拟量子力学的计算成本过高。他还提出了使用基于量子力学原理的计算机来避免这个问题的可能性,从而含蓄地提出了相反的问题:通过在计算机中使用量子力学,您是否可以比在经典计算机上更有效地进行计算。 在量子力学和计算领域的其他早期工作由Benioff完成。虽然他并没有提出量子力学是否赋予了计算额外的能力,但他确实证明了可以通过量子过程的可逆幺正演化来模拟图灵机,这是量子计算的必要前提。 Deutsch是第一个给出明确的量子计算模型的人。他定义了量子图灵机和量子电路,并研究了它们的一些特性。

本文的下一部分讨论了量子计算与经典复杂性类别的关系。因此,我们将首先为那些没有此背景的读者简要直观地讨论复杂性类别。通常有两种资源限制了计算机解决大问题的能力:时间和空间(即内存)。算法分析领域将算法对这些资源的渐近需求视为问题大小的函数。当算法的步数增长为输入大小的多项式时,理论计算机科学家通常将算法归类为有效算法。可以通过有效算法解决的问题类别称为PP 。这个分类有几个很好的属性。一方面,它可以合理地反映算法在实践中的性能(尽管运行时间是输入大小的 10 次方的算法并不是真正有效的)。另一方面,这种分类在理论上很好,因为不同的合理机器模型产生相同的PP 类。我们将看到这种行为在量子计算中再次出现,其中量子机器的不同模型在运行时间上的差异不会超过多项式因子。

本文还讨论了其他计算复杂性类。其中一个是PSPACE,这些问题可以通过输入大小的内存多项式来解决。另一个重要的复杂度类是NP,直观上是指数搜索问题。这些问题可能需要搜索指数大小的空间来找到解决方案,但是一旦找到解决方案,就可以在多项式时间内验证解决方案(可能使用多项式数量的额外支持证据)。我们还将讨论另外两个传统的复杂性类。一个是 BPP,这是一种可以在多项式时间内用一个随机数生成器以高概率解决的问题。另一个是P#PP^{\#P} ,如果可以有效地计算指数级多个项的总和(其中这些总和必须满足每个项在多项式时间内可计算的要求),那么这些问题可以在多项式时间内解决。这些类的关系如下:

BPP 和 NP 的关系是未知的。

在计算机中使用量子力学是否能使人获得更多的计算能力,这个问题尚未得到令人满意的回答。虽然这个问题在之前的研究中得到了解决,但没有说明如何在量子多项式时间内解决任何在 BPP 中无法解决的问题(一类可以在有界误差概率的多项式时间内解决的问题)。Bernstein和Vazirani的论文为计算复杂度的量子计算理论奠定了基础,促进了最近对这一问题的研究。这篇论文中包含的一个结果是一个预言问题(一个涉及“黑盒子”子程序的问题),它可以在量子图灵机上用多项式时间完成,而在经典计算机上需要超多项式时间。这是第一个迹象,除了没有人知道如何在没有指数减速的情况下在经典计算机上模拟量子计算机之外,量子计算可能比用随机数生成器扩大的经典计算获得大于多项式的加速。Simon改进了这一结果,他给出了一个更简单的oracle问题的构造,在量子计算机上需要多项式时间,而在经典计算机上需要指数时间。事实上,通过将Simon的预言视为一个子程序,这个结果就变成了一个有希望的问题,它在量子计算机上需要多项式时间,在经典计算机上看起来似乎非常困难。本文给出的离散对数“简单情况”的算法直接类似于simon算法,即组Zk2Z{k\atop 2} 替换为组Zp−1Z_{p-1} ;我是在看到Simon的论文后才发现这个算法的。

在Bernstein和Vazirani论文的另一个结果中,严格定义了一类特定的量子图灵机,并给出了一个通用的量子图灵机,它可以模拟该类的任何其他量子图灵机。不幸的是,这些量子图灵机是否能够模拟其他类的量子图灵机还不清楚,因此这个结果并不完全令人满意。Yao纠正了这种情况,证明了量子图灵机可以模拟多项式大小的量子电路,并且可以被这些量子电路所模拟,其速度最多为多项式。他进一步定义了具有kk 个头的量子图灵机,并表明这些机器可以在减速系数为2k2^k 的情况下进行模拟。这似乎表明,这类问题可以在多项式时间内在这些机器上解决,可能具有有界概率ϵ<1/3\epsilon<1/3 的误差,是相当稳健的。此类称为BQP,类似于经典的复杂性类BPP,这些问题可以在概率图灵机上用一个有界的误差概率来解决。此类BQP可以被认为是在量子图灵机上可有效解决的一类问题。

由于BPQ⊆\subseteq P#PP^{\#P} ⊆PSPACE\subseteq PSPACE ,任何证明 BQP 严格大于 BPP 的非相对化证明都将暗示结构复杂性结果BPP⊆PSPACEBPP\subseteq PSPACE 尚未得到证明。鉴于这一困难,我想到了几种方法;一个是表明BQP⊆BPPBQP\subseteq BPP 将导致被认为是不同的经典复杂性类别的崩溃。第二种方法是证明与预言相关的结果。Bennett等人表明,相对于随机预言机,NP⊆BQPNP\subseteq BQP 并非如此。这一证明实际上表明量子计算机不能反转单向函数,而只能证明单向预言,即作为子程序给出的“黑盒”函数,不允许量子计算机查看内部。这种预言结果在过去一直具有误导性,尤其是在IP=PSPACEIP=PSPACE 的情况下。我们采用的第三种方法是在 BQP 中解决一些经过充分研究的问题,该问题没有多项式时间算法已知。这表明,量子干涉所赋予的额外功率至少很难使用经典计算来实现。 Bernstein 和 Vazirani 和 Simon也为 BPP 中未知的问题提供了多项式时间算法,但是这些问题是专门为此目的而发明的,尽管 Simon 的问题看起来并不人为,并且可以想象是有用的。

离散对数和整数因式分解是两个已被广泛研究但没有多项式时间算法已知的数论问题 。事实上,人们普遍认为这些问题很难,以至于基于密码系统 已经提出了关于它们的硬度的问题,并且基于因式分解的硬度的 RSA 公钥密码系统正在使用中。 我们证明了这些问题可以在 BQP 中解决。

目前,没有人知道如何建造量子计算机,尽管在量子力学定律下似乎是可能的。对于这种计算机的可能设计已经提出了一些建议,但是要建立这些计算机中的任何一个都将会有实质性的困难。即使可以建造小型量子计算机,但将规模扩大到足以进行有趣计算的机器可能会带来根本性的困难。 希望这篇论文能够激发对实际构建量子计算机是否可行的研究。

即使从未建造过量子计算机,这项研究也确实阐明了在经典计算机上模拟量子力学的问题。 对任意哈密顿量执行此操作的任何方法都必须能够模拟量子计算机。 因此,任何用于模拟最多多项式减速的量子力学的通用方法都将导致用于因式分解的多项式算法。

2.量子计算

在本节中,我们将简要介绍量子计算,强调我们将使用的属性。 对于更完整的概述,建议读者参考 Simon 的论文或早期关于量子计算复杂性理论的论文。

在量子物理学中,一个实验表现得好像它同时沿着所有可能的路径进行。每条路径都有一个复杂的概率振幅,这是由实验的物理性质决定的。实验中任何特定结果的概率与所有通向该结果的路径振幅和绝对值的平方成正比。为了对一系列路径进行求和,结果必须在所有方面都是相同的,即宇宙必须处于相同的状态。量子计算机的行为与此大致相同。 计算同时沿着所有可能的路径进行,并且每条路径都与一个复振幅相关联。 为了确定机器任何最终状态的概率,我们将到达该最终状态的所有路径的幅度相加,然后对该总和的绝对值求平方。

观察这个过程的一个等价的方法是想象机器在计算的每一步都处于某种状态的叠加状态。我们将态的叠加表示为

其中幅值aa 为复数,使得Σi∣ai∣2=1\Sigma_i\rvert a_i\rvert^2=1 ,并且每个∣Si⟩\rvert S_i\rangle 是机器的基本状态;在量子机器中,基本状态由磁带上写入的内容以及磁头的位置和状态定义。 在量子电路中,基态是由电路中某一级别的所有导线上的信号值来定义的。如果在某一特定步骤检查机器,则看到基状态∣Si⟩\rvert S_i\rangle 的概率为∣ai∣2\rvert a_i\rvert^2 ;然而,根据海森堡不确定性原理,在计算过程中看着机器会干扰其他的计算过程。

量子力学定律只允许状态的酉变换。一个酉矩阵的共轭转置等于其逆矩阵的矩阵,并且要求用酉矩阵表示状态变换可确保获得所有可能结果的概率加起来为 1。 此外,量子图灵机和量子电路的定义只允许局部酉变换,即对固定位数进行酉变换。

在这一点上,也许一个例子会提供信息。 假设我们的机器处于状态叠加状态

然后应用酉变换

到我们状态的最后两位。 也就是说,我们将向量 (2.2) 的最后两位分量乘以矩阵 (2.3)。 然后机器将进入状态叠加

请注意,如果我们从状态叠加开始,结果会有所不同

如果观察到它,它在任何特定配置中具有相同的概率。

我们现在给出一些有用的量子计算特性。 从量子物机或量子电路的定义来看,这些事实并不是立即显而易见的,它们对于构建量子机器的算法非常有用。

事实 1:当且仅当确定性计算是可逆的时,在量子计算机上可以执行确定性计算。根据可逆计算的结果,只要我们将输入aa 保留在机器上,我们就可以计算任何多项式时间函数f(a)f(a) 。 要擦除aa 并用f(a)f(a) 替换它,我们还需要ff 是一对一的,并且aa 可以从 f(a)f(a) 在多项式时间内计算; 即ff 和f−1f^{-1} 都是多项式时间可计算的。

事实2:任何多项式大小的酉矩阵都可以使用多项式的基本酉变换来近似,因此可以在量子计算机上以多项式时间进行近似。 此外,该近似值足够好,可以在计算结果中引入最多有界的错误概率。

3.构建酉变换

由于量子计算涉及酉变换,因此能够建立某些有用的酉变换是很有帮助的。本节我们将给出一些在量子机器上构建酉变换的技术,这将导致我们展示如何在多项式时间内构建一个特定的酉变换。 这些转换通常以矩阵形式给出,行和列都由状态索引。 这些状态将对应于计算机上的整数表示; 特别是,除非另有说明,否则行和列将从 0 开始索引。

我们将在本文中反复使用的一个工具是下面的酉变换,它的求和得到一个傅里叶变换。考虑一个数字aa 与0≤a≤q0\leq a\leq q 对于某个qq , qq 的位数是多项式。我们将执行将状态∣a⟩\rvert a\rangle 转换为状态

也就是说,我们应用其第(a,b)\left(a,b\right) 项为1q1/2exp⁡(2πiab/q){{{1\over q^{1/2}}\exp(2\pi iab/q)}} 的酉矩阵。 这种转换是我们算法的核心,我们称这个矩阵为AqA_q 。 由于我们将使用AqA_q ,对于指数大小的qq ,我们必须说明如何在多项式时间内完成这种转换。 事实上,我们只能对平滑数qq 执行此操作,即质因数较小的数。 在本文中,我们将处理对于某些固定cc 不包含大于(logq)c\left(logq\right)^c 的素功率因数的平滑数 qq 。 也可以在多项式时间内对所有平滑数qq 进行这种变换;Coppersmith 展示了如何使用本质上是快速傅立叶变换对q=2kq=2^k 进行此变换,并且这大大减少了因式分解所需的运算次数。

如果我们知道一个因数分解q=q1q2q3⋅⋅⋅qkq=q_1q_2q_3\cdot\cdot\cdot q_k ,其中gcd⁡(qi,qj)=1\operatorname{gcd}\left(q_i,q_j\right)=1 ,并且kk 和所有qiq_i 都是多项式大小的,我们将展示如何在多项式时间内通过组合AqA_q ,来构建变换AqiA_{qi} 。为此,我们首先需要一个关于量子计算的引理。

引理 3.1 假设矩阵BB 是一个块对角线mn×mnmn\times mn 酉矩阵,由沿对角线的nn 个相同的m×mm\times m 矩阵B′B^{\prime} 和其他任何地方的0′s0^{\prime}s 组成。 进一步假设状态转换B′B^{\prime} 可以在时间T(B′)T\left(B^{\prime}\right) 上在量子图灵机上完成。 然后矩阵BB 可以在T(B′)+(log⁡mn)cT\left(B^{\prime}\right)+\left(\log mn\right)^c 时间内在量子图灵机上完成,其中cc 是一个常数。

我们将此矩阵BB 称为B′B^{\prime} 的nn 个副本的直接和,并使用符号B=B= ⊕n\oplus_n B′B^{\prime} 。 该矩阵BB 是B′B^{\prime} 和InI_n 的张量积,其中InI_n 是n×nn\times n 单位矩阵。

证明:假设磁带上有一个数字aa 。 我们可以从a=mα1+α2a=m\alpha_1+\alpha_2 可逆地计算α1\alpha_1 和α2\alpha_2 。 此计算从磁带中删除 aa 并将其替换为α1\alpha_1 和α2\alpha_2 。 现在α1\alpha_1 告诉aa 包含在哪个块中,α2\alpha_2 告诉该块中矩阵的哪一行是aa 行。 然后我们可以将B′B^{\prime} 应用于α2\alpha_2 以获得β2\beta_2 (在此过程中擦除α2\alpha_2 )。 现在,结合α1\alpha_1 和β2\beta_2 以获得b=mα1+β2b=m\alpha_1+\beta_2 给出了BB 应用于aa 的结果(具有正确的幅度)。B′B^{\prime} 的计算需要T(B′)T\left(B^{\prime}\right) 时间,其余的计算是log⁡m+logn\log m+logn 中的多项式。

我们现在展示如何获得AqA_q ,以获得平滑的qq 。 我们将AqA_q 分解为多项式的单位变换的乘积,所有这些都可以在多项式时间内执行; 这使我们能够在多项式时间内构造AqA_q 。 假设我们有q=q1q2q=q_1q_2 且gcd⁡(q1,q2)=1\operatorname{gcd}\left(q_1,q_2\right)=1 。我们要做的是表示Aq=CDA_q=CD ,其中通过重新排列DD 的行和列我们得到⊕q1Aq2\oplus_{q1}A_{q2} , 并且重新排列行和CC 的列我们得到⊕q2Aq1\oplus_{q2}A_{q1} 。 只要CC 和DD 的行和列的这些重新排列可以在多项式时间内执行(即,给定行rr ,我们可以在多项式时间内找到它所在的行r′r^{\prime} )并且逆运算也可以在多项式时间,然后通过使用上面的引理和递归,我们可以在量子计算机上获得多项式时间的方式来执行AqA_q 。

我们现在需要定义CC 和DD 并检查Aq=CDA_q=CD 。 要定义CC 和DD ,我们需要一些初步定义。 回想一下q=q1q2q=q_1q_2 ,其中q1q_1 和 q2q_2 互质。 令w=exp(2πi/q)w=exp\left(2\pi i/q\right) 。 令uu 为数(mod  q)\left(\mod q\right) ,使得u≡0(mod  q1)u\equiv0\left(\mod q_1\right) 且u≡−1(mod  q2)u\equiv-1\left(\mod q_2\right) 。 根据中国余数定理,这个数是存在的,并且可以在多项式时间内计算出来。我们将行和列索引a、b和ca、b和c 分解如下:a=α1q2+α2a=\alpha_1q_2+\alpha_2 、b=β1q1+β2b=\beta_1q_1+\beta_2 和c=γ1q1+γ2c=\gamma_1q_1+\gamma_2 。注意a、b和ca、b和c 定义中的不对称性。

现在我们可以定义CC 和DD :

且

很容易看出CD(a,c)=C(a,b)D(b,c)CD\left(a,c\right)=C\left(a,b\right)D\left(b,c\right) 其中b=α2q1+γ2b=\alpha_2q_1+\gamma_2 因为我们需要α2=β1\alpha_2=\beta_1 和β2=γ2\beta_2=\gamma_2 来确保C(a,b)C\left(a,b\right) 和 D(b,c)D\left(b,c\right) 。 现在,

所以CD(a,C)=Aq(a,c)CD\left(a,C\right)=A_q\left(a,c\right) 。

我们现在将概述如何重新排列CC 的行和列,以获得矩阵⊕q2Aq1\oplus_{q2}A_{q1} 。 矩阵CC 可以放在块对角形式中,其中块由α2=β1\alpha_2=\beta_1 索引(因为所有带有α2≠β1\alpha_2\ne\beta_1 的条目都是00 )。令u+1=tq2(mod  q)u+1=tq_2\left(\mod q\right) 。 在给定的块α2=β1\alpha_2=\beta_1 内,条目是这样的

因此,如果我们重新排列该块中的行,以便它们通过α′≡α1+α2t(mod  q1)\alpha^{\prime}\equiv\alpha_1+\alpha_2t\left(\mod q_1\right) 进行索引,我们将获得具有幅值1q1/21{1\over q{1/2\atop 1}} exp⁡(2πiα′β2/q1)\exp\lparen2\pi i\alpha^{\prime}\beta_2/q_1) 的变换α′→β2\alpha^{\prime}\xrightarrow{}\beta_2 ; 即,由(α′,β2)\left(\alpha^{\prime},\beta_2\right) 项等于1q1/21{1\over q{1/2\atop 1}} exp⁡(2πiα′β2/q1)\exp\lparen2\pi i\alpha^{\prime}\beta_2/q_1) 的酉矩阵给出的变换,即Aq1A_{q1} 。矩阵DD 可以类似地重新排列以获得矩阵⊕q1Aq2\oplus_{q1}A_{q2} 。

我们还需要展示如何在多项式时间内找到介于nn 和2n2n 之间的平滑qq 。 实际上有更接近nn 的平滑qq ,但这就是我们所需要的。 不知道如何在多项式时间内找到非常接近nn 的平滑数。

引理 3.2 给定nn ,有一个多项式时间算法可以找到一个数qq ,其中n≤q<2nn\leq q<2n ,使得没有大于clogqclogq 的素数除以qq ,对于某个常数cc 与nn 无关。

证明 要找到这样的qq ,将素数2⋅3⋅5⋅7⋅11⋅⋅⋅pk2\cdot3\cdot5\cdot7\cdot11\cdot\cdot\cdot p_k 相乘,直到乘积大于nn 。 现在,如果这个乘积大于2n2n ,则将其除以保持数字大于nn 的最大素数。 这会产生所需的qq 。 在 mm 和2m2m 之间总是存在一个素数,所以n≤q<2nn\leq q<2n 。 素数定理和一些计算表明,最大的素数除法qq 的大小为O(logn)O\left(logn\right) 。

请注意,如果我们使用 2% 单位根的 Coppersmith 变换A2kA_{2^k} ,我们设q=2kq=2^k ,其中k=l[log⁡2n]+1k=l\left\lbrack\log_2n\right\rbrack+1 。

4.离散对数:简单案例

离散对数问题是:给定一个素数 p,乘法组的生成器gg (mod  p)\left(\mod p\right) 和一个x(mod  p)x\left(\mod p\right) ,找到一个rr 使gr=x(mod  p)g^r=x\left(\mod p\right) 。我们将首先给出在p−1p-1 是平滑的情况下在量子计算机上离散对数的多项式时间算法。 该算法与Simon论文中的算法类似,只是用Zp−1Z_{p-1} 代替了组Zk2Z{k\atop 2} 。平滑情况本身并不是一个有趣的成就,因为在这种情况下已经有经典计算机的多项式时间算法; 然而,解释这种情况比解释离散对数或分解算法的一般情况更容易,并且由于这三种算法相似,这个例子将说明更复杂的算法是如何工作的。

我们将从磁带上的x、g和px、g和p 开始我们的算法。(即,在我们机器的量子存储器中)。 我们试图计算rr 使得gr≡x(mod  p)g^r\equiv x\left(\mod p\right) 。 因为我们永远不会删除它们,所以x、g和px、g和p 是常数,我们将通过磁带的其他内容指定我们机器的状态。

该算法从统一“选择”数字aa 和b(mod  p−1)b\left(\mod p-1\right) 开始,所以这一步之后机器的状态是

该算法接下来可逆地计算gax−b(mod  p)g^ax^{-b}\left(\mod p\right) ,因此我们必须将值aa 和bb 保留在磁带上。 机器状态现在是

我们现在要做的是使用变换Ap−1A_{p-1} 来映射a→ca\xrightarrow{}c 与幅度1(p−1)1/2exp⁡(2πiac/(p−1)){{{1\over \left(p-1\right)^{1/2}}\exp(2\pi iac/\left(p-1\right))}} 和b→db\xrightarrow{}d 与幅度1(p−1)1/2exp⁡(2πibd/(p−1)){{{1\over \left(p-1\right)^{1/2}}\exp(2\pi ibd/\left(p-1\right))}} 。 正如上一节所讨论的,这是一个酉变换,并且由于p−1p-1 是平滑的,它可以在量子机器上的多项式时间内完成。这将使机器处于状态

我们现在计算机器在状态∣c,d,y⟩\rvert c,d,y\rangle 和y≡gky\equiv g^k (mod  p)\left(\mod p\right) 时计算结束的概率。这个概率是机器可以产生这种状态的所有方式的总和平方的绝对值, 或者

其中所有a,ba,b 的和满足a−rb≡k(mod  p−1)a-rb\equiv k\left(\mod p-1\right) 。 这种情况源于这样一个事实,即计算路径只有在给出相同的y≡ga−rb≡gk(mod  p)y\equiv g^{a-rb}\equiv g^k\left(\mod p\right) 时才会产生干扰。 我们现在将方程a≡k+rb(mod  p−1)a\equiv k+rb\left(\mod p-1\right) 代入上述指数。 然后上面的总和减少到

然而,如果d+rcd+rc ≠0(mod  p−1)\ne0\lparen\mod p-1) 上面的和是在一组(p−1)st\left(p-1\right)^{st} 个单位根上均匀分布在单位圆周围,因此概率为00 。如果d≡−rcd\equiv-rc 是p−1p-1 乘以相同的根,得到(p−1)e2πikc/(p−−1)\left(p-1\right)e^{2\pi ikc/\left(p--1\right)} ,所以概率是1/(p−1)21/\left(p-1\right)^2 。我们可以通过计算有(p−1)2\left(p-1\right)^2 个状态∣c,−rc,y⟩\rvert c,-rc,y\rangle 来检查这些概率加起来等于11 ,因为有p−1p-1 个选择c(mod  p−1)c\left(\mod p-1\right) 和p−1p-1 个选择y≠0(mod  p)y\ne0\left(\mod p\right) 。

因此,我们的计算产生了一个随机的c(mod  p−1)c\left(\mod p-1\right) 和相应的d≡−rc(mod  p−1)d\equiv-rc\left(\mod p-1\right) 。如果cc 和p−1p-1 是相对质数,我们可以通过除法得到rr 。因为我们是在所有可能的c中以相等的概率进行选择,cc 和p−1p-1 相对质数的机会是ϕ(p−1)/(p−1)\phi\left(p-1\right)/\left(p-1\right) ,其中ϕ\phi 是欧拉ϕ−function\phi-function 。很容易求出ϕ(p−1)/(p−1)>1/log⁡(p)\phi\left(p-1\right)/\left(p-1\right)>1/\log(p) 。(实际上,限制ϕ(p−1)/(p−1)≈e−r/log⁡log⁡p\phi\left(p-1\right)/\left(p-1\right)\thickapprox e^{-r}/\log\log p )因此,我们只需要大量的实验,在log⁡p\log p 上是多项式,就可以得到高概率的rr 。事实上,我们可以找到一组cc ,使得p−1p-1 的每个质数因子中至少有一个是质数的,只要在预期的常数次内重复这个实验。这也给了我们足够的信息来得到rr 。

5.关于精度的说明

量子力学计算机振幅所需的精度位数可能是实用性的障碍。 可行和不可行之间普遍接受的理论分界线是多项式精度(即问题大小的对数位数)是可行的,而更多的则是不可行的。 这是因为在量子计算机上,相位角需要通过一些物理设备来获得,而以优于多项式精度的方式构建此类设备无疑是不切实际的。 事实上,即使是多项式精度也可能被证明是不切实际的; 但是,将其用作理论分界线会产生很好的理论性质。

因此,我们需要证明上一节中的计算只需要在幅度中使用多项式精度。 写下表达式exp⁡(2πiac/(p−1))\exp(2\pi iac/\left(p-1\right)) 的行为似乎暗示我们需要指数精度,因为这个相位角是指数精度的。 幸运的是,情况并非如此。 考虑相同的矩阵Ap−1A_{p-1} ,其中每一项 exp⁡(2πiac/(p−1))\exp\left(2\pi iac/\left(p-1\right)\right) 都替换为exp⁡(2πiac/(p−1)±πi/20)\exp\left(2\pi iac/\left(p-1\right)\pm\pi i/20\right) 。 每个正例,即导致d≡−rcd\equiv-rc 的情况,仍然会以几乎与以前一样大的概率发生; 我们不是添加具有完全相同相位角的 p−1p-1 个幅度,而是添加具有几乎相同相位角的p−1p-1 个幅度,因此总和的大小只会减少一个常数因子。因此,算法将给出一个(c,d)\left(c,d\right) ,其中d≡−rcd\equiv-rc 具有常数概率(而不是概率1)。

回想一下,我们通过最多将log⁡p\log p 矩阵AqA_q 相乘来获得矩阵Ap−1A_{p-1} 。 此外,Ap−1A_{p-1} 中的每个条目最多是log⁡p\log p 项的乘积。 假设每个相位角在Aqi′sA_{qi}^{\prime}s 中最多偏离ϵ/log⁡p\epsilon/\log p 。 然后在产品中,每个相位角最多会偏离ϵ\epsilon ,这足以以恒定的成功概率执行计算。 一个类似的论点表明,AqA_q 中幅度的大小可以偏离多项式分数。 类似的论点适用于离散对数的一般情况和因式分解,以表明在这些情况下,我们也只需要幅度的多项式精度。

我们仍然需要展示如何从精度有限的恒定大小的酉矩阵中构造 AqiAq_i 。 论点与上述大致相同,但我们不会在本文中给出它们,因为事实上,Bennett等人已经证明,对于量子图灵机上的任何计算,使用多项式精度来获得高概率的答案是足够的。

由于精度很容易成为量子计算实用性的限制因素,因此建议研究量子算法实际需要多少精度。 尽管 Bemstein 和 Vazirani 表明所需的精度位数永远不会超过量子计算机所采取的计算步骤数的对数,但在某些算法中它可能需要更少的精度。 有趣的悬而未决的问题是,是否有可能以低于多项式的精度进行离散对数或因式分解,以及是否可以在精度和时间之间进行权衡。

6.因式分解

因式分解的算法类似于离散对数的一般情况的算法,只是稍微简单一些。 我在离散对数的一般情况之前介绍了这个算法,以便按照复杂度增加的顺序给出本文中的三种算法。 对离散对数感兴趣的读者可以跳到下一节。

我们不是给出一个量子计算机算法来分解nn ,而是给出一个量子计算机算法来寻找乘法组中元素xx 的阶数(mod  n)\left(\mod n\right) ;即xr≡1(mod  n)x^r\equiv1\left(\mod n\right) 的最小整数rr 。 从因式分解到元素的顺序有一个随机减少。

为了分解一个奇数nn ,给定一个元素的阶数的计算方法,我们随机选择一个xx ,找出rxr_x 的阶数xx ,并计算gcd⁡(xrx/2−1,n)\operatorname{gcd}\left(x^{r_{x/2}}-1,n\right) 。只有当rxr_x 是奇数或xrx/2≡−1(mod  n)x^{r_{x/2}}\equiv-1\left(\mod n\right) 时,这才不能给出nn 的非平凡除数。使用这个判据,可以证明该算法找到一个概率至少为1−1/2k1-1/2^k 的nn 因子,其中kk 是nn 的不同素数因子的个数。因此,只要nn 不是素幂,该方案就可以工作; 但是,使用经典方法可以有效地分解素数。

给定xx 和nn ,要找到满足xr≡1(mod  n)x^r\equiv1\left(\mod n\right) 的rr ,我们执行以下操作。 首先,我们找到一个2n2≤q<4n22n^2\leq q<4n^2 的平滑qq 。 接下来,我们将机器置于表示数字a(mod  q)a\left(\mod q\right) 的状态的统一叠加中。 这使我们的机器处于状态

与离散对数的算法一样,我们不会在机器的状态中写入n,x或qn,x或q ,因为我们从不改变这些值。

接下来,我们计算xa(mod  n)x^a\left(\mod n\right) 。 由于我们将xx 和aa 保留在磁带上,因此可以可逆地完成。 这使我们的机器处于状态

然后我们执行傅里叶变换AqA_q ,将a→ca\xrightarrow{}c 映射到幅度1q1/2exp⁡(2πiac/q){{{1\over q^{1/2}}\exp(2\pi iac/q)}} 。 这使我们的机器处于状态

最后,我们观察机器。 仅观察cc 的值就足够了,但为了清楚起见,我们假设我们同时观察cc 和xa(mod  n)x^a\left(\mod n\right) 。 我们现在计算我们的机器以特定状态结束的概率∣c,xk(mod  n)⟩\rvert c,x^k\left(\mod n\right)\rangle ,其中我们可以假设0≤k<r0\leq k<r 。对所有可能的方式求和达到这个状态,我们发现这个概率是

其中总和是所有aa ,0≤a<q0\leq a<q ,使得xa≡xk(mod  n)x^a\equiv x^k\left(\mod n\right) 。 因为xx 的阶数是rr ,所以这个和等效于所有满足a≡k(mod  r)a\equiv k\left(\mod r\right) 的aa 。 写作a=br+ka=br+k ,我们发现上面的概率是

我们可以忽略exp⁡(2πikc/q)\exp(2\pi ikc/q) 的项,因为它可以从总和中分解出来并且大小为11 。我们也可以用{rc}q\lbrace rc\rbrace_q 替换rcrc ,其中 {rc}q\left\{rc\right\}_q 是与rc(mod  q)rc\left(\mod q\right) 同余,并且在−q/2<{rc}q≤q/2-q/2<\lbrace rc\rbrace_q\leq q/2 的范围内。 这给我们留下了表达式

现在我们将证明,如果{rc}q\left\{rc\right\}_q 足够小,那么这个和中的所有幅度将几乎在相同的方向上,给出一个很大的概率。 如果 {rc}q\left\{rc\right\}_q , 相对于qq 很小,我们可以使用变量t=b/qt=b/q 的变化,并用积分近似这个和

如果∣{rc}q∣≤r/2\rvert\left\lbrace rc\right\rbrace_q\rvert\leq r/2 ,这个量可以被证明为渐近下界为4/(π2r2)4/\left(\pi^2r^2\right) ,因此至少有1/3r21/3r^2 。看到给定状态∣c,xk(mod  n)⟩\rvert c,x^k\left(\mod n\right)\rangle 的概率至少为1/3r21/3r^2 ,如果

也就是说,如果有一个dd

除以rqrq ,重新排列得到

我们知道cc 和qq 。 因为q≥2n2q\geq2n^2 ,最多有一个分数d/rd/r 且r<nr<n 满足上述不等式。 因此,我们可以通过将c/qc/q 四舍五入到分母小于nn 的最接近的分数来获得最低项的分数d/rd/r 。 这个分数可以通过使用c/qc/q 的连续分数展开在多项式时间内找到,它通过分数找到c/qc/q 的所有最佳近似值。

如果我们有最低分数d/rd/r ,并且如果dd 恰好与rr 互质,这将给我们rr 。我们现在将计算状态数∣c,xk(mod  n)⟩\rvert c,x^k\left(\mod n\right)\rangle ,这使我们能够计算rr 这样。 与rr 互质的有ϕ(r)\phi\left(r\right) 个可能值,其中ϕ\phi 是欧拉的ϕ\phi 函数。 这些分数d/rd/r 中的每一个都接近一个分数 c/qc/q ,其中∣c/q−d/r∣≤1/2q\rvert c/q-d/r\rvert\leq1/2q 。xkx^k 也有rr 个可能的值,因为rr 是xx 的阶。 因此,有rϕ(r)r\phi\left(r\right) 个状态 ∣c,xk(mod  n)⟩\rvert c,x^k\left(\mod n\right)\rangle 将使我们能够获得rr 。 由于这些状态中的每一个都以至少1/3r21/3r^2 的概率出现,因此我们以至少ϕ(r)/3r\phi\left(r\right)/3r 的概率获得rr 。 使用ϕ(r)/r>k/log⁡\phi\left(r\right)/r>k/\log 的定理对于某些固定的kk ,这表明我们发现rr 至少有k/log⁡logrk/\log logr 时间的一部分,所以通过只重复这个实验O(1oglogr)O\left(1oglogr\right) 次,我们确信有很高的成功概率。

请注意,在排序算法中,我们没有使用乘法(mod  n)(\mod n) 的许多属性。 事实上,如果我们有一个置换ff 映射集合{0,1,2,...,n−1}\lbrace0,1,2,...,n-1\rbrace 到自身中,使得其kthkth 迭代f(k)(a)f^{\left(k\right)}\left(a\right) 可以在log⁡n\log n 和log⁡k\log k 中以时间多项式计算,相同的算法将能够找到元素aa 在ff 下的阶, 即,最小rr 使得 f(r)(a)=af^{(^r)}\left(a\right)=a 。

7.离散对数:一般情况

对于一般情况,我们首先找到一个光滑的数字qq ,使qq 接近pp ,即p≤q≤2pp\leq q\leq2p (见引理3.2)。

接下来,我们做与简单情况相同的事情,即统一选择aa 和bb (mod  p−1)\left(\mod p-1\right) ,然后计算gax−b(mod  p)g^ax^{-b}\left(\mod p\right) 。这样我们的机器就处于状态

和以前一样,我们使用傅里叶变换AqA_q ,发送a→ca\xrightarrow{}c 和b→d(mod  q)b\xrightarrow{}d\left(\mod q\right) ,幅度为1qexp⁡(2πi(ac+bd)/q){1\over q}\exp\lparen2\pi i\left(ac+bd\right)/q) ,给我们状态

请注意,我们现在有两个模数要处理,p−1p-1 和qq 。 虽然这使得追踪事情变得更加混乱,但我们仍然可以使用类似于简单案例的算法来获得rr 。 用y≡gk(mod  p)y\equiv g^k\left(\mod p\right) 观察状态∣c,d,y⟩\rvert c,d,y\rangle 的概率几乎和以前一样,

(a,b)\left(a,b\right) 的和使a−rb≡k(mod  p−1)a-rb\equiv k\left(\mod p-1\right) 。我们现在利用这个关系

并代入上述表达式以获得幅度

这个幅度的平方的绝对值是观察到状态∣c,d,gk(mod  p)⟩\rvert c,d,g^k\left(\mod p\right)\rangle 的概率。 我们现在来分析这个表达式。 首先,可以从所有项中取出exp⁡(2πrikc/q)\exp\left(2\pi rikc/q\right) 的因子并忽略,因为它不会改变概率。 接下来,我们将指数分成两部分并分解出bb 以获得

其中

并且

这里的{z}q\left\{z\right\}_q 是指 z(mod  q)z\left(\mod q\right) 的余数,其中 −q/2<{z}q≤q/2-q/2<\left\{z\right\}_q\leq q/2 。 我们将证明,如果我们得到足够“好”的输出,那么我们仍然可以推导出rr ,而且,得到“好”的输出的机会是恒定的。 这个想法是,如果

其中jj 是最接近T/qT/q 的整数,那么当bb 在00 到p−2p-2 之间变化时,Eq.(7.6)中的第一个指数项的相位最多只在单位圆的一半上变化。此外,如果

那么∣V∣\rvert V\rvert 总是最多q/20q/20 ,因此Eq.(7.6)中的第二个指数项的相位永远不会比exp⁡(πi/10)\exp(\pi i/10) 离11 远。通过结合这两个观察,我们将表明,如果两个条件都成立,那么对应项对概率的贡献是显著的。此外,这两个条件将以恒定的概率成立,和一个合理的cc 的样本,其中条件(7.9)成立将允许我们推断rr 。

我们现在给出每个良好输出的概率的下界,即满足条件(7.9)和(7.10)的输出。我们知道当bb 取值为00 到p−2p-2 时,exp⁡(2πiU/q)\exp\left(2\pi iU/q\right) 的相位取值为00 到2πiW2\pi iW ,其中

jj 如式(7.9)所示。因此,式(7.6)中第一个指数的振幅在方向上的分量

至少为cos⁡(2π∣W/2−Wb/(p−2)∣)\cos\left(2\pi\rvert W/2-Wb/\left(p-2\right)\rvert\right) 。现在,根据条件(7.10)。由于第二个指数exp⁡(2πiV/q)\exp\left(2\pi iV/q\right) ,相位最多可以变化πi/10\pi i/10 。应用这种变化的方式来最小化方向上的分量(7.12),我们得到这个方向上的分量至少是cos⁡(2π∣W/2−Wb/(p−2)+π/10)\cos\left(2\pi\rvert W/2-Wb/\left(p-2\right)+\pi/10\right) 。因为p<qp<q ,从条件(7.9),∣W∣≤1/2\rvert W\rvert\leq1/2 ,把所有内容放在一起,得到同时满足条件(7.9)和(7.10)的状态∣c,d,y⟩\rvert c,d,y\rangle 的概率至少为

或者至少是137/q2137/q^2 。

我们现在将计算满足条件 (7.9) 和 (7.10) 的的成对数(c,d)\left(c,d\right) 。 使 (7.9) 成立的对(c,d)\left(c,d\right) 的数量正是可能的cc 的数量,因为对于每个cc 恰好有一个dd 使得 (7.9) 成立(将分数四舍五入到最接近的整数以获得这个dd )。 (7.10) 成立的cc 的数量约为q/10q/10 。 因此,有q/10q/10 对 (c,d) 满足这两个条件。 乘以p−1p-1 ,它是可能的yy 的数量,得到大约pq/10pq/10 个状态∣c,d,y⟩\rvert c,d,y\rangle 。将此计算与每个良好状态概率的下限相结合,我们得出获得任何良好状态的概率 状态至少为p/80qp/80q ,或至少1/1601/160 (因为q<2pq<2p )。

我们现在想从一对c,dc,d 中恢复rr 使得

其中这个方程是从条件 (7.9) 除以qq 得到的。 首先要注意的是,rr 上的乘数是分母为p−1p-1 的分数,因为qq 均分c(p−1)−{c(p−1)}qc\left(p-1\right)-\left\{c\left(p-1\right)\right\}_q 。因此,我们只需要将d/qd/q 四舍五入到最接近1/(p−1)1/\left(p-1\right) 的倍数,并除以(mod  p−1)\left(\mod p-1\right)

找到一个候选rr 。为了证明这个实验只需要重复多项式次数来找到正确的rr ,只需要更多的细节。 问题是我们不能除以一个与p−1p-1 不互质的数。

对于离散对数算法的一般情况,我们不知道c′c^{\prime} 的所有可能值都是合理似然生成的;我们只知道其中的十分之一。这个额外的难度使得下一个步骤比前两个算法中相应的步骤更难。 如果我们知道rr 模除p−1p-1 的所有素数的余数,我们可以使用中国剩余定理在多项式时间内恢复rr 。 我们只能找到大于 20 的素数的余数,但通过一些额外的工作,我们仍然能够求出rr 。

我们所拥有的是每个好的(c,d)\left(c,d\right) 对的生成的概率至少为137p/q>1/16q137p/q>1/16q ,并且至少十分之一可能的cc 位于好的(c,d)\left(c,d\right) 对中。由方程式 (7.15)可知,这些cc 通过四舍五入到1/(p−1)1/\left(p-1\right) 的最接近整数倍数,从c/qc/q 映射到c′/(p−1)c^{\prime}/\left(p-1\right) 。此外,好的 cc 正是c/qc/q 接近c′/(p−1)c^{\prime}/(p-1) 的那些。因此,每个好的cc 都恰好对应于一个c′c^{\prime} 。我们想证明,对于任何素数pαip{\alpha\atop i} 除以p−1p-1 。一个随机的好c′c^{\prime} 不太可能包含pip_i 。如果我们愿意接受算法的大常数,我们可以忽略20以下的素数幂;如果我们知道rr 模所有超过20的素数幂,我们可以尝试20以下素数的所有可能的残差,而运行时间只有(大)常数因子增加。因为至少有十分之一的cc 是好的(c,d)(c,d) 对,所以至少有十分之一的cc 是好的。因此,对于素数幂pαiip{\alpha i\atop i} ,随机的好的c′c^{\prime} 可被pαiip{\alpha i\atop i} 整除,概率最多为10/pαi10/p{\alpha\atop i} 。如果我们没有好的c′c^{\prime} ,那么拥有超过20的素数幂除以所有这些概率的概率最多是

其中总和是所有大于 20 且除以p−1p-1 的素数的总和。这个总和(在所有大于 20 的整数上)在t=2t=2 时收敛,并且随着tt 每进一步增加 1,该总和至少下降 2 倍; 因此对于一些大常数tt 它小于1/21/2 。

回想一下,每个好的c′c^{\prime} 是从任何实验中以至少1/16q1/16q 的概率获得的。 由于有q/10q/10 个好的c′c^{\prime} ,经过 160t 次实验,我们很可能会从所有好的c′c^{\prime} 中等概率地获得tt 个好的c′c^{\prime} 样本。 因此,我们将能够找到一组dd ,使得除p−1p-1 的所有素数幂pαiip{\alpha i\atop i} 与这些dd 中的至少一个相对素数。 对于每个小于 20 的素数pp ,因此我们最多有 20 种余数模pip_i 的可能性,其中αi\alpha_i 是p−1p-1 的素数分解中素数pp 的指数。因此,我们可以尝试所有可能的余数模幂小于 20 的素数:对于每种可能性,我们可以使用中国剩余定理计算相应的rr ,然后检查它是否是所需的离散对数。

该算法并没有使用ZpZ_p 的很多性质,因此我们可以使用相同的算法来求其他域上的离散对数,例如ZpαZ_{p^{\alpha}} 。 我们需要的是我们知道生成器的顺序,并且我们可以在多项式时间内乘以和取元素的逆。

如果要对这个算法进行编程(必须等到建立量子计算机之后),有很多方法可以提高本文中所示的效率。

致谢

我要感谢 Jeff Lagarias 在离散对数算法的第一个版本中发现并修复了一个严重错误。 我还要感谢Charles Bennett、Gilles Brassard、Andrew Odlyzko、Dan Simon、Umesh Vazirani 以及其他的作者,感谢他们进行富有成效的讨论,对本文的早期草稿进行更正和改进,以及本文所引用的参考文献。




---煤油灯科技victorlamp.com翻译整理---

完整附件下载:Shor1994.pdf

你可能也喜欢这些文章