Deutsch–Jozsa 与 Grover 等算法常从预言机 出发。但布尔(Boolean)函数可能丢失信息:AND 将四个输入映射为一个输出位。这样的函数如何成为酉电路的一部分?方法是保留输入,并把结果异或到单独的目标位。接下来的反计算则不经测量地清除临时结果。
设 是确定性布尔函数。我们使用计算基字符串、异或 ,以及 、受控非门和 Toffoli 门。Toffoli 门将 映为 ,保持两个控制位不变。这些门置换计算基态,因此都是酉的。
为什么预言机可逆
定义 9.3.1
(位预言机)
对布尔函数 ,位预言机是作用于 个输入量子比特和一个目标量子比特的算子,在计算基态上定义为
无论 是否多对一,对每个基态应用 (1) 两次都会回到原态:。它是置换,因此酉。它不是单独将 映为 。若两个不同输入有相同输出,即使把输出填充回 个量子比特,后一个映射也会把正交输入态变成同一个态,因而不可能酉。
命题 9.3.2
(位预言机是酉的并产生相位回踢)
对每个布尔函数 , 都是酉的,且 。令 ,则
证明
(置换,以及目标位翻转的特征向量)
映射 是自身的逆,因此是计算基态的置换, 是置换矩阵,从而酉。对 (2),展开 。若 ,这就是 ;若 ,它是 。
由线性性,这个相位作用于叠加态的每个分支。这是相位回踢,不是对所有 值的测量。
从布尔电路构造预言机
假设给定一个计算 的无环经典电路,按拓扑顺序有 个 AND 或 NOT 门以及一个指定输出线。输入和先前门的输出可反复用作控制。为每个门预留一个初始为零的干净工作位。要把两条不同的先前线路的 AND 写入新工作位,使用 Toffoli 门。若两个输入来自同一线路,则用受控非门,因为 。要把 NOT 写入新工作位,先以 为控制施加受控非门,再对工作位施加 。两种情况下控制位不变,新位都保存所需门值。
定理 9.3.3
(由含干净工作空间的经典电路构造预言机)
设一个含 个 AND 或 NOT 门的无环经典电路计算 。则存在一个由 中至多 个门和 个工作位组成的电路,对每个 有
所以只要工作位初始为干净状态,它就实现 ,并使工作位恢复干净。
证明
(计算、复制、反计算)
所有门计算后,可逆电路 的作用为
其中 保存全部门值;指定输出是这些值之一或某条输入线。同一电路对叠加态按线性性作用。电路 只作用于输入和工作寄存器;单独的目标位 在 和 期间不参与。现在从输出线向 施加受控非门,再按相反门序运行 。对每个基态输入 得到
不作用于目标位,因此复制出的结果保留下来。(4) 由线性性推广到任意叠加,并在干净工作空间子空间上实现 (1)。反计算不是通过测量擦除,而是已知可逆计算的逆操作。
每个经典 AND 或 NOT 门至多使用两个上述可逆门计算其值。因此 至多用 个门, 至多用 个门,再加一个输出受控非门及 个干净工作位:总计至多 个所列门。
这是在将 Toffoli 视为一个门的门集下的上界;若使用不同的量子基本门集,还需考虑其分解。它也假设经典电路已经给出。 作为置换的存在本身并不使任意 的预言机廉价。
证明透视
计算、复制、反计算每一步用到什么
紧接 运行 ,会同时清除工作空间和已计算的答案,因为 。不显然的一步是中间那个受控非门:它作用于目标位,而 和 都不碰目标位,所以它把 记录在一个能熬过反计算的寄存器上。这里用到两个假设。第一,工作寄存器初始为 ,所以 恰好产生 , 又恰好把它撤销。第二, 中每个门都不改变其控制位,所以复制发生时输出线仍保存 。线性性再把基态上的计算推广到叠加态。若工作寄存器不干净,(3) 就不成立,见下面的反例。
AND 例题
例题 9.3.4
(只用一个工作位的 AND)
对 ,一个工作位 即可。令 ,先对 用 Toffoli,再由 到 使用受控非门,最后再次对 用 Toffoli。变换为
当 时目标位翻转,其余三个基态输入则不翻转。若 ,诱导的相位映射为对角映射,仅 带负号,而工作位返回 。输入含有其他分支时,此符号是可观测的相对相位;单独作用于 时,它是全局相位。
例题 9.3.5
(用两个工作位的 NAND)
取 ,共 个门。先用 Toffoli 对 把 写入 。再把 NOT 写入 :由 到 施加受控非门,然后对 施加 。接着由 到 施加受控非门复制结果,再按相反顺序运行前面三个门。当 :,,所以 不变,而 。当 :,,所以 翻转,而 。两种情况下反计算都使 。电路共用 个门,不超过上界 。
例题 9.3.6
(边界情形:AND 的两个输入是同一条线)
对 ,Toffoli 规则需要两个不同的控制位,所以改用受控非门。先由 到工作位 施加受控非门,把 写入 ;再由 到 施加受控非门复制;最后撤销第一步。于是 ,即 ,工作位干净。
常见错误
反例模式
工作寄存器不干净会破坏预言机
看似合理的说法:不论工作位原来是什么,计算—复制—反计算电路都实现 。对 AND 电路,取 和输入 (即 、)。第一个 Toffoli 使 ;由 到 的受控非门令 ;第二个 Toffoli 令 保持为 。输出为 ,但 要求 。脏工作位虽返回一,其值却错误地影响了目标位。保证 (4) 要求工作寄存器初始为 。
常见错误
(丢弃工作空间不等于反计算)
对 施加受控非门,得到 。对第二个量子比特取偏迹后,第一个为 ,而不是 。此时在 基上测量第一个量子比特,得到 的概率只有 ,而不是一。这个简单复制类似于依赖输入的垃圾 :丢弃纠缠的工作寄存器可能移除相干性,并改变后续干涉计算。
常见错误
(把线路多次用作控制并不克隆量子态)
同一线路多次用作控制,也不会克隆任意未知量子态。受控非门可以把计算基位复制到干净目标位,但作用于叠加态时可能使寄存器纠缠,正如上一个例子所示。
练习与解答
快速检查
(即使 ,为什么 仍酉?)
看输入寄存器发生了什么。
解答 · 答案
二元组 保留了 ,而异或是自身的逆;(1) 是基态置换。
快速检查
(在 AND 例子中, 会怎样变化?)
追踪工作位和目标位经过三个门的变化。
解答 · 答案
目标位 翻转为 ,得到 :第一个 Toffoli 令 ,受控非门令 ,第二个 Toffoli 令 。
快速检查
(尽管 、受控非门和 Toffoli 都是自身的逆,为什么 仍须按相反门序运行?)
回想 。
解答 · 答案
门的乘积取逆时需要反转因子顺序;每个因子自身可逆,并不使它们彼此对易。
快速检查
( 的门数界是否意味着每个布尔函数都有关于 的多项式规模预言机?)
想想 是什么。
解答 · 答案
不能。该界以已给出的规模为 的电路为条件; 本身可能关于 指数增长。