量子计算机编程：从入门到实践

舒尔分解算法

｜

199

如前所述，

QPU

在这里只做了部分工作。

Shor()

函数调用另外两个函数。第一个函数是

ShorQPU()

，它利用

QPU

（或其模拟）来帮助查找函数的

重复周期

。第二个函数是

ShorLogic()

，

它的工作是使用在

CPU

上运行的传统软件执行的。稍后，我们将更详细地讨论这些函数。

我们在示例中所用的

ShorLogic()

仅用于说明目的。尽管说起来很简单，但

它做的事情不简单——它可以处理非常大的数。全规模舒尔分解算法是当前

的研究热点。

本章接下来将以易于理解的方式介绍标准的舒尔分解算法。但是请注意，我们所介绍的并

不是最高效的实现，而且实际情况可能会因

QPU

硬件而异。

12.2

　算法说明

让我们从

ShorQPU()

函数开始。我们将在没有数论证明的情况下断言一个有用的事实

2

，那

就是如果我们能够解决在整数变量

x

变化的情况下，找出函数

a

x

mod(

N

)

的重复周期这一

看似无关的问题，就有可能找出使一个数

N

=

pq

的质因数

p

和

q

。这里的

N

仍然是我们要

分解的数，

a

被称为

互质

（

coprime

）。互质的值可以是任意素数。

如果找出

a

x

mod(

N

)

重复周期的想法听起来很模糊，请不要担心。它的意思是，当你更改

x

的值时，

a

x

mod(

N

)

返回的数字序列最终会重复自身，如图

12-1

所示。

为简单起见，我们选择

2

作为互质。除了因为它是最小的素数，这种选择还

具有其他优点，如

a

x

的

QPU

实现可以通过简单地移位来实现。这是一个很

好的选择，它适合本章涉及的情况，但并不适合其他情况。

分解15 分解35

每4个值重复一次 ...