量子计算中有三个反复出现的思想:干涉可以揭示函数的整体承诺结构;纠缠可以产生超出经典共享随机性模型的关联;冗余编码可以保护量子信息,而无需读出未知概率幅。每个结论都依赖精确的模型。下面分别研究一个例子,并说明其局限。
Simon 的隐藏异或掩码
定义 2.5.1
(Simon 承诺与预言机)
函数 满足 Simon 承诺,是指存在非零 ,使得
目标是通过查询可逆预言机 找出 。下文中 表示逐位点积模 , 是 上的正交子空间。
因此每个函数值恰有两个原像,且两者都相差同一个未知掩码。尽管 是二对一的,该预言机仍置换基态,因而是酉变换。
命题 2.5.2
(Simon 样本落在正交子空间内)
从 开始,对第一个寄存器作用 ,查询 ,再对第一个寄存器作用 并测量它。测量结果 在 的 维子空间 上均匀分布。
证明
(原像配对与奇偶性抵消)
第一层 Hadamard 门和查询之后,状态为 。测量第二个寄存器得到某个值 ;在这个条件下,第一个寄存器为
由于 ,且模 时 ,第二层 Hadamard 门之后, 的概率幅为
当 时它为零;当 时,其模平方为 。第二寄存器取任何值都得到同一分布,因此每次运行都从 维子空间 均匀抽样。测量第二寄存器有助于推导,但也可以省略:直接舍弃它,第一寄存器的分布相同。
证明透视
隐藏掩码如何进入证明
承诺只用了一次:它说明某个值的两个原像是 与 ,且 相同。点积的双线性使平移 变成相对符号 ,而未知的代表元 只出现在整体符号 中,它不影响概率。这就是为什么分布不依赖所见到的函数值 。
Hadamard 变换恰好消去相对符号为负的结果;剩下的样本是方程,并非掩码本身。没有承诺就没有共同的 ,也就没有抵消的规律,下面的反例会说明这一点。必须重复抽样,直到样本张成 ,从而确定它的一维正交补。
重复运行得到线性方程 ,再通过 上的高斯(Gauss)消元法求解。样本 不提供信息,重复样本也可能线性相关。
命题 2.5.3
(由样本恢复掩码)
若样本 张成 ,则 是对所有 满足 的唯一非零解 。对 个独立样本,它们未能张成 的概率至多为 。
证明
(正交补与并集界)
若样本张成 ,任何解 都与整个 正交。在 上点积是非退化的,所以 的维数为 且包含 ;因此它就是 ,唯一的非零解便是掩码。
若样本未能张成 ,它们落在一个真子空间内,因此落在 上某个非零线性泛函的核中。这样的泛函有 个。对固定的一个,其核的元素个数是 的一半,所以每个均匀样本落入其中的概率为 , 个独立样本全部落入的概率为 。对这些泛函使用并集界即得结论。
因此 次查询可达到常数成功概率,继续取样可提高成功率。经典查询下界指的是相同的承诺黑箱模型;查询次数本身不包括实现具体预言机的代价。
例题 2.5.4
(三比特掩码的样本)
当 、,可能的输出为 000、001、110、111,概率均为 。由 和 得到两个独立方程 、;唯一非零解是 110。一次运行通常不足以确定掩码。
常见错误
(单个样本不是掩码)
样本 只满足 ;它是关于 的一个方程,并非 本身。在三比特例子中,样本 完全有效,却不同于 ,而样本 完全不带信息。样本只是偶然地等于掩码,如下面的双比特例子。必须等方程组只剩下一个非零解,才输出掩码。
一个完整的双比特预言机计算
例题 2.5.5
(双比特预言机的完整电路)
取 ,令 。函数表把 映到 ,把 映到 。因此每对原像相差 ,符合承诺。在隐藏掩码问题中,学习者并不直接得到此表;这里列出它是为了检验电路。
两个寄存器均从 出发,经过第一层 Hadamard 门和预言机后,状态为
每项乘积的第一个态属于输入寄存器。对它作用 , 保持不变,而 变成 。因此联合态为
第一寄存器中没有 或 。 和 各以概率 出现:对每个结果,两个对应的输出寄存器态正交,故概率幅的模平方相加。样本 给出 ;再用承诺 ,便确定 。样本 不给任何限制。这个例子的样本恰好等于掩码,但一般并非如此。
每次重新制备并独立运行, 次后至少见到一次 的概率是 。所以本例三次查询后,从样本方程确定掩码的概率为 。这个概率来自测量结果,并非对 的随机选择;它也依赖学习者使用非零掩码的承诺。若所有样本均为零时采用猜测策略,其成功概率会不同,并取决于未知掩码的模型和猜测方式。
快速检查
(改用 。找出掩码和两个可能样本。如果前两次独立样本都是 ,仅凭样本数据能确定掩码吗?)
解答 · 答案
原像对是 和 ,故 。由 得 或 ,各以概率 出现。两个零样本只给出方程 ,三个非零双比特掩码都与这些样本方程相容。这里展示的函数表能确定掩码,但算法只获准查询预言机,并不直接获知函数表。
承诺不能被悄悄略去。下面的例子对一个不是二对一的函数运行同一电路,说明样本此时不能确定任何掩码。
反例模式
没有承诺就没有掩码可找
命题:无论 是什么函数,电路都只会从某个超平面 ()中抽样。取 ,即 、,它不是二对一的。第二寄存器以概率 显示 ,此时第一寄存器为 。经 后, 的概率幅是 除以 ,概率为 。第二寄存器以概率 显示 ,第一寄存器为 ,四个结果的概率均为 。合起来,结果 的概率分别为 。四个字符串都会出现,所以样本张成 ,使所有样本满足 的唯一解是 。没有任何非零掩码与数据相容。上面的命题需要二对一承诺。
CHSH 与非定域关联的含义
定义 2.5.6
(局域策略与 CHSH 表达式)
在 CHSH 实验中,Alice 和 Bob 分别接收输入比特 ,并输出符号 。确定性的局域策略预先指定 。局域隐变量策略是确定性策略的概率混合,其中输入选择与共享隐变量独立,且每一方的输出只依赖本方输入和隐变量。CHSH 表达式为
定理 2.5.7
(经典 CHSH 界)
对每个局域隐变量策略,。
证明
(确定性赋值与取平均)
由于 都是 , 和 中恰有一个非零,且等于 ;另一个括号为 ,所以每个确定性赋值都有 。局域隐变量策略是这些赋值的混合,绝对值为 的量的期望,其绝对值至多为 。
现在双方共享 ,并取可观测量
它们均为厄米(Hermitian)算子,且特征值为 。
定理 2.5.8
(超过经典界的量子策略)
在 上取这些可观测量,CHSH 期望为 。
证明
(四个关联量)
代入可观测量,
在 上, 和 的期望均为 ,所以 。
若输入均匀随机,游戏要求双方输出相同符号,唯独 时要求相反符号。获胜概率为 ;量子策略得到 ,经典局域策略至多为 。
常见错误
(非定域关联不是信号传递)
违反不等式排除了上述局域隐变量解释,并不违反无信号原则。这里每一方的边缘输出均匀随机;单独观察它,无法读出远方选择的输入。比较关联仍需经典通信,所以这种违反不能用来传送消息。
保护一个量子比特免受比特翻转
定义 2.5.9
(三比特翻转码)
此码把 编码成三个量子比特:
编码电路从 开始,以第一个比特为控制、依次对另外两个比特作用受控非门。其错误校验子(syndrome)是可交换奇偶算子 和 的特征值对。
常见错误
(编码不是复制)
编码态并不是三个 的副本:结果一般是纠缠态,而三个副本会包含八个基态项,系数如 。未知态不能被复制,这正是此冗余要靠关联来建立的原因。
假设错误被承诺为无错误或某个单比特翻转 。四种情况的特征值对为:
| 错误 | ||
|---|---|---|
| 无 | ||
定理 2.5.10
(单比特翻转的纠正)
对这四种情况中的每一种,编码态都是 和 的共同特征向量,特征值如上表,且这四个值对互不相同。作用校验子所指明的 即可恢复 。
证明
(码字及其补的奇偶性)
基态 是 的特征向量,特征值为 ;也是 的特征向量,特征值为 。 的两项互为按位取补,而把所有位取补不改变每对位的奇偶性。因此两项有相同的校验子,该状态是特征向量。取其中一项来读: 给出 ; 给出 ; 给出 ; 给出 。四个校验子互不相同,所以校验子确定发生了哪个 ;又因 ,再作用一次就恢复 。对所有 校验子都相同,所以测量它不会透露 的任何信息。
例题 2.5.11
(第一个比特翻转的校验子)
对 ,项 有 、。项 有 、。两项都给出校验子 ,正是 那一行,再作用 就恢复 。在无错误这个边界情形,两项都给出 ,不作任何纠正。
对 ,两个基态项对两个奇偶算子的特征值均为 。因此错误校验子能识别错误,却不区分 项和 项;再作用 即恢复编码态。校验子测量揭示的是承诺范围内发生了哪个错误,而非编码的计算基值。
此码能纠正一个比特翻转,却不能纠正任意单比特错误。
反例模式
比特翻转码不能纠正相位错误
命题:三比特码能在任何单比特错误之后恢复编码态。取 。此时 ,它与无错误状态具有相同的两个 校验子,所以解码器不作任何纠正,相对相位的改变就保留下来。输入 ()时,编码的加态变成与之正交的编码减态。该命题只在错误被承诺为比特翻转时成立。纠正一般错误需要同时检测相位错误的编码和校验子方案;容错操作还需控制编码、量子门和校验子提取本身引入的错误。
练习与解答
快速检查
(在 、 的 Simon 承诺下,列出可能的样本 。)
解答 · 答案
在 上,条件 给出 000、010、101、111,概率均为 。
快速检查
(对确定性符号 、,化简 CHSH 表达式。任何 的选择能使其绝对值超过 吗?)
解答 · 答案
,所以无论 如何选择,其绝对值恰为 2。
快速检查
(三比特码中发生 会产生什么校验子?如何修正?)
解答 · 答案
奇偶值对是 ;再作用 ,利用 即可恢复。