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

166

｜

第

10

章

这些状态分别对逻辑赋值语句

(a=0, b=0, c=1)

、

(a=1, b=0, c=1)

和

(a=1, b=1, c=1)

进行

编码，只有它们是满足图

10-3

所示的原始布尔语句的逻辑输入。

10.2

　解决逻辑谜题

至此，我们知道了如何标记满足布尔语句的值的相位。利用新掌握的能力，我们可以使用

AA

原语来解决

布尔可满足性问题

，即判断输入值是否满足给定的布尔语句。这正是我们

通过相位逻辑所学到的！

布尔可满足性是计算机科学中的一个重要问题

5

，它被应用于模型检测、人工智能规划和软

件验证等场景。为了理解这个问题（以及如何解决它），我们将看一看

QPU

如何帮助我们

解决一个没什么经济效益却很有趣的布尔可满足性问题：逻辑谜题！

小猫和老虎

在一座很远很远的岛上，曾经住着一位公主，她非常想要一只小猫作为她的生日礼物。公

主的父亲——国王——虽然不反对她的想法，但他想知道女儿对于养宠物的决定是否是认

真的。因此，他在女儿过生日时给她出了一道谜题，如图

10-6

所示

6

。

图 10-6：生日谜题

在她生日的那一天，公主收到了两个盒子，但她最多只能打开其中一个。每个盒子装的既

可能是她梦寐以求的小猫，也可能是一只凶猛的老虎。还好盒子上贴有文字如下的标签。

盒子 A 上的标签

至少有一个盒子里有一只小猫。

盒子 B 上的标签

另一个盒子里有一只老虎。

注

5

：

布尔可满足性是第一个被证明为

NP

完全问题。

N

-SAT

是包含

N

个字面量布尔语句子句的布尔可满足

性问题，当

N

>2

时是

NP

完全的。第

14

章会提供更多关于基本计算复杂度的信息，还会推荐用于深 ...