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

160

第 10章

量子搜索

在第

6

章中，我们看到了振幅放大（

AA

）原语如何将寄存器的相位差转换为可检测的强度

差。回想一下，在介绍

AA

原语时，我们假设应用程序将提供一个子例程来翻转

QPU

寄存

器中的值的相位。举一个简单的例子，我们使用翻转电路作为占位符，它简单地翻转单个

已知寄存器值的相位。本章将详细介绍几种相位翻转技术，它们基于与众不同的逻辑结果。

量子搜索

（

quantum search

，

QS

）是一种特殊的技术，用于修改翻转子例程，以便通过

AA

原语从

QPU

寄存器中可靠地读取某类问题的解。换句话说，

QS

实际上只是

AA

的一个应

用，它提供一个非常重要的子例程

1

来标记寄存器相位中某类问题的解。

QS

能够解决的一类问题是反复求解子例程，其解要么为“是”，要么为“否”。这种解通

常是传统布尔逻辑语句的输出

2

。这类问题的一个典型的应用场景是在数据库中搜索特定

的值。简单地想象一下，有这样一个布尔函数，当且仅当输入是我们正在搜索的数据库

元素时返回

1

。它其实是量子搜索的典型应用，用到的算法就是著名的

格罗弗搜索算法

（

Grover

’

s search algorithm

），以其发现者的名字命名。通过应用量子搜索技术，格罗弗搜

索算法只通过

()ON

次查询就可以在数据库中找到一个元素，而传统算法通常需要

O

(

N

)

次查询。

然而，格罗弗搜索算法要求数据库是非结构化的，而这在实际应用中实属罕见，并且难以

实现。

注

1

：

在文献中，根据某种逻辑函数翻转相位的函数被称为

oracle

，其含义与在传统计算机科学中类似。我

们在此选择了更容易理解的术语，但在第 ...