作用于 个基态的傅里叶(Fourier)变换,矩阵看似有指数级大小。它特殊的相位结构却允许用二次数量级的基本旋转构造电路。要理解这一点,必须追踪哪个位承载输入的哪个小数部分:除非重新解释输出,否则颠倒这些位会改变酉算子。
分解傅里叶和
定义 2.3.1
(n 个量子比特上的量子傅里叶变换)
设 、。量子傅里叶变换是 个量子比特上的酉算子 ,满足
写 、,所以 是最低有效位。对 ,定义二进制小数 。
矩阵有 个元素,但每个输出位可以分别求和。
定理 2.3.2
(傅里叶变换的乘积形式)
在上述记号下,
各因子由最高有效输出位排到最低有效输出位。
证明
(逐个输出位求和)
展开 ,其中 。则
对所有 求和就是对相互独立的各位 求和,而分别依赖不同变量的函数之积的和,等于各自求和后再相乘。因此
权重为 的输出位所对应因子的相位只依赖 模 的值。满足 的项 贡献整数,可以舍去。其余各项给出 。 时是 , 时是 ,即上面显示的次序。
上述张量顺序中,最高有效输出位在前。因此二进制小数的顺序与输入线路相反。
构造电路
定义 2.3.3
(相位门与受控相位门)
对整数 ,令 。受控 将 乘以 ,并保持这两条线路的其他三个计算基态不变。
线路按输入位的权重编号,依次执行:
- 对 ,在第 条线路施加 Hadamard 门。
- 紧接该门,对每个 ,施加以第 条线路为控制、第 条线路为目标的受控 。
- 所有这些块完成后,用 个交换门反转线路顺序。
定理 2.3.4
(傅里叶变换的精确电路)
上述电路含 个 Hadamard 门、 个受控旋转和 个交换门;在定义所采用的正指数约定下,它作为酉映射等于 。
证明
(对基态输入逐条线路计算)
对一个基态输入处理线路 时,较低编号的控制线路尚未改变。Hadamard 门使 项获得相位 ;各旋转贡献 。于是该线路的因子为
交换前,这些因子按 递减排列,与 的乘积顺序相反。交换门把它们放回上述顺序。由于电路和 在每个计算基向量上都相同,线性性保证它们在任何输入态上相同,包括纠缠态或叠加态。证明使用上述正指数约定;逆变换将门的次序反转并把每个门替换为其伴随。
证明透视
电路证明的各个假设用在哪里
这个论证有三个运作部分。第一,次序 使每条控制线路 在被使用时仍处于输入态 ,所以旋转角度只依赖输入位,而不依赖已被变换的线路。第二,角度 的选取使控制位 恰好加上二进制小数的 一项。第三,交换门只修正乘积的排列次序,并不改变任何相位。
计算是对基态输入进行的,证明的是两个线性映射相等,而不是假定输入已知为某个基态。一旦它们在一组基上的作用相同,线性性就决定了它们在任意叠加态上的作用。关于尚未改变的控制位的描述属于基态计算;不应把它理解为对这些位作测量。
例题 2.3.5
(三个位的相位)
当 、 时,输入为 。反转之前,从最高到最低有效位的线路因子分别带有相位 、 和 。反转之后,
相对相位 是 的相反数;替换它会改变状态,而不只是改变整体相位。若省略输出交换门,上式的张量因子顺序反转,因而必须相应解释位标号。
例题 2.3.6
(两个位的追踪)
取 、,即 。先处理线路 。它的 Hadamard 门给出 ,而以处于 的线路 为控制的受控 把 项乘以 。该线路的因子是 ,与相位 吻合。线路 随后只受一个 Hadamard 门作用,成为 。交换前的状态是 ;交换后
直接计算, 对 的系数为 ,两者一致。
例题 2.3.7
(最小情形 )
时没有受控旋转,因为对 不可能有 ;交换门数为 。电路只是一个 Hadamard 门。乘积形式给出 ,所以单个量子比特上的量子傅里叶变换就是 Hadamard 门。
概念视角结构
把循环移位变成相位的变换
设 ,。由定义得 ,其中 ,即 。傅里叶变换就是使循环移位对角化的基变换,这也是它对周期结构敏感的原因。
每个基态输入的输出都是乘积形式,容易让人以为所有输出都是乘积态;输入一旦是叠加态,这个推断就不成立。
反例模式
乘积态之和不一定是乘积态
命题:既然对每个基态输入 都是乘积态,那么对每个输入 , 也都是乘积态。当 时,基态输入 确实产生上面的乘积态。但输入 的输出,在 顺序下的系数为 ,这是因为 、。其 系数矩阵的行列式 非零,故输出是纠缠态。线性性并不意味着乘积态的和仍是乘积态;该命题只对基态输入成立。
常见错误
(忘记位反转)
没有最后的交换门,上述电路并不实现 。当 、 时,正确的输出是 ,而不加交换门的电路输出 。这是两个不同的状态,并非只差一个整体相位。不加交换门的电路是位反转的傅里叶变换,只有在后续步骤重新标记线路时才可以接受。
门数与近似旋转
共有 个 Hadamard 门、 个受控旋转和 个交换门。把每个旋转和交换门各算作一个理想门,得到 门;交换门也可分解为三个 CNOT 门。这是电路大小的计数,不意味着固定有限门集中的任意旋转都可以零代价合成。
命题 2.3.8
(省略小旋转)
设 为整数。省略所有满足 的受控 ,保留其他门和最后的交换门,将所得酉算子记为 。对算子范数 ,
证明
(对省略的门裂项求和)
逐个把省略的门替换为恒等门。裂项求和与算子范数的酉不变性把总差值限制在各门差值之和以内。受控 的差值为 。每条目标线路对每个 至多省略一个旋转,而无限尾和为 。对至多 条目标线路求和即得所述界。
对任何归一化输入,两个输出态向量之差的欧氏(Euclidean)范数也不超过同一数值。保留下来的受控旋转至多 个。取 ,就使此界不超过 。该估计假设保留的门是理想门;用固定门集近似它们会增加额外误差,必须另行计入。
测量不是经典傅里叶表
对计算基输入 ,在计算基中测量 ,得到每个 的概率均为 ,因为各振幅的模均为 。任意输入不一定具有这种均匀性: 将均匀叠加态 映为 ,测量结果必为零。相位信息需要后续干涉才能发挥作用;一次测量不能揭示整个复数傅里叶振幅向量。这并不是说该变换无用,而是说明外围算法必须如何利用它。
常见错误
(把输出当成傅里叶系数表)
对未知态施加电路后,一次测量只返回一个以概率 抽得的下标 ,并不返回 个复数 。要得到这张表,需要大量重复制备,而且相位仍会丢失。因此二次数量级的门数并不给出快速的经典傅里叶变换。
练习与解答
快速检查
(当 、 时,按输出顺序写出 的两个因子。)
解答 · 答案
此时 、。第一个因子的相位是 ,第二个是 ,所以 。
快速检查
(当 时,精确电路使用多少个受控旋转和交换门?)
解答 · 答案
受控旋转有 个,交换门有 个。
快速检查
(为什么在同一线路约定下,省略最后交换门的电路严格来说不是上述 ?)
解答 · 答案
输出线路中的傅里叶因子顺序相反;需要交换门或明确重新解释位标号。
快速检查
(当 、 时,给出上面的一般算子范数误差界。)
解答 · 答案
。这个界是空泛的:任意两个酉算子之差的算子范数至多为 ,小于 。更大的 可以改善上述估计。