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

216

｜

第

12

章

12.3.8

　步骤

8

：

检查结果

一个数的质因数可能很难找到，但一旦找到答案就很容易验证。我们可以很容易地验证

3

和

5

都是素数，而且是

15

的因数（因此甚至不需要在

ShorLogic()

中检查第二个值

8

）。

成功了！

12.4

　使用细节

本章介绍了一个典型的复杂算法的简化版本。在我们的舒尔分解算法中，为了便于说明，

我们简化了一些方面，但这是以算法的通用性为代价的。我们不会去深入挖掘，只是在这

里做了一些必要的简化。更多信息也可以从在线示例代码中找到。

12.4.1

　求模

之前已经提到过，在对

a

x

mod(

N

)

的

QPU

计算中，函数求模部分以某种方式被自动处理。

这是我们想要分解的特定数字带来的巧合，可惜这并非普遍的情况。回想一下，我们通过

移位将

work

寄存器乘以

2

的幂。如果简单地从值

1

开始，然后移动

4

次，那么我们应该得

到

16

（

2

4

= 16

）。但是，由于我们只使用了

4

位的数字，并且允许循环移位，因此得到的

不是

16

，而是

1

，这也正是我们在乘法运算之后执行

mod(15)

所得到的结果。

如果尝试分解

21

，你可以验证这个技巧也有效。可是，在较大（但仍然相对较小）的数字

上（如

35

），它失效了。对于这些更普遍的情况，我们能做些什么？

当传统计算机计算一个数的模时，例如

1024 % 35

，它首先执行整数除法，然后返回余数。

执行整数除法所需的传统逻辑门的数量

非常大

，其

QPU

实现远远超出了本书范畴。

不过有一种计算模的方法可以解决这个问题，它的实现不那么复杂，非常适合

QPU

运算。

假设我们要为某个值