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

170

｜

第

10

章

10.3

　求解布尔可满足性问题的一般方法

当然，公主的谜题是布尔可满足性问题应用于猫科动物的一个特例。我们用来解决这个谜

题的方法可以很好地推广到其他使用

QPU

解决布尔可满足性问题的场景，步骤如下。

1.

将布尔语句从可满足性问题转换为必须同时满足的多个子句的形式（该语句是多个独立

子句的

AND

结果）

7

。

2.

使用强度逻辑表示每个单独的子句，不过这样做将需要一些临时量子比特。根据经验，

由于大多数量子比特将涉及多个子句，因此每个逻辑子句有一个临时量子比特是很有

用的。

3.

将整个

QPU

寄存器（包含用于表示语句所有输入变量的量子比特）初始化为均匀叠加

态（使用

HAD

），并将所有临时寄存器初始化为

|

0

⟩

态。

4.

使用图

5-25

给出的强度逻辑方法来逐个构建每个子句中的逻辑门，并将每个逻辑子句

的输出值存储于一个临时量子比特中。

5.

一旦实现了所有子句，就在所有临时量子比特之间执行相位逻辑

AND

运算，以组合不同

的子句。

6.

反计算所有的强度逻辑运算，将临时量子比特恢复为它们的初始状态。

7.

在编码了输入变量的

QPU

寄存器上执行镜像子例程。

8.

根据振幅放大方程式（方程式

6-2

），重复上述步骤，重复次数按需确定。

9.

通过读取

QPU

寄存器来获取最终的振幅放大结果。

接下来，我们给出两个应用此方法的示例，其中第二个示例将展示当试图满足的语句实际

上无法满足时（没有输入组合可以产生输出

1

），这个方法将如何起作用。

10.3.1

　实践

：

一个可满足的

3-SAT

问题

思考下面这个

3-SAT

问题：

(a ...