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

量子搜索

｜

175

到目前为止，情况不错！图

10-12

展示编码了输入值

a

、

b

、

c

的

3

个量子比特在整个计算

过程中是如何被转换的。注意，我们只考虑一次

AA

迭代，因为在一次

AA

迭代之后就能

明显地看到它是否有效果。

相位逻辑

振幅放大

图 10-12：用圆形表示法表示不可满足的 3-SAT 问题

如图

10-12

所示，没有任何效果！因为寄存器的

8

个可能值都不满足逻辑语句，所以没有

相位相对于任何其他值翻转。因此，

AA

迭代的镜像部分同样影响所有值。无论执行多少

次

AA

迭代，当读取这

3

个量子比特时，我们都将完全随机地获得

8

个值中的一个。

在读取操作中可能获得任意值，这一点使我们看起来似乎没有任何收获，但是无论读取的

是

a

、

b

和

c

的哪种组合，我们都可以尝试将它们输入到逻辑语句中。如果得到的结果是

0

，那么我们可以大胆地得出结论：该逻辑语句是不可满足的（否则我们会得到满足逻辑

语句的值）。

10.4

　加速传统算法

振幅放大的一个显著的特点是，在某些情况下，它不仅可以加速暴力破解算法，也可以对

最好的传统算法实现提供二次加速。

振幅放大可以加速带有

单边错误

（

one-sided error

）的算法。这些算法用来解决某些决策问

题，其中包含输出答案为“是”或“否”的子例程。如果问题的答案是“否”，则算法始

终输出“否”；如果问题的答案是“是”，则算法以概率

p

（

p

>0

）输出答案“是”。在前面

的

3-SAT

示例问题中，我们已经看到，算法只有在找到一个可满足的值时才给出“是”的

答案（方程式是可满足的）。

为了找到具有目标概率的解，传统算法必须重复其概率子例程若干次。如果算法的运行时 ...