计算与验证是不同任务
量子电路可以变换叠加态,再返回经典测量结果。复杂性理论研究的是这样一族计算:当输入长度增长时,其资源也按受控方式增长。另一个问题允许证明者提供一个量子态,帮助量子验证器接受“是”实例。验证器仍须对所有声称的见证拒绝“否”实例。
我们讨论判定问题,以语言 表示。电路作用于经典输入的基态编码。复杂性类的包含关系是对所有输入长度的陈述,不是关于某个固定大小的装置,也不是关于某次恰好成功的实验。
一致量子电路与 BQP
固定一个元素可计算的有限通用门集,例如包含 Hadamard、、受控非门和标准可逆经典门的门集。
定义 6.1.1
(多项式时间一致的电路族)
如果存在确定性经典算法,以 为输入,在关于 的多项式时间内输出 的描述,就称族 多项式时间一致。
因此电路的门数和线路数也是多项式级。电路对长度 固定;具体输入 放在输入线上。有限门集避免把具有无限精度的任意实数角度旋转当作一次免费操作。这里的通用是指近似通用。对满足通常逆门与通用性条件的标准固定有限门集,Solovay–Kitaev 定理 给出高效近似,其开销对精度倒数呈多对数增长。将多项式数量的门近似到足够小的逆多项式误差,可在多项式开销下保持常数判定间隔。这里引用这一门集等价结果,不作证明。
定义 6.1.2
(BQP)
若存在多项式时间一致、多项式大小的量子电路族,输入为 和多项式数量的 辅助量子比特,且指定输出量子比特满足
则称语言 属于 BQP。
接受指在计算基中测量指定输出量子比特,结果为 1。概率由电路和测量决定,不需要对输入假设某个概率分布。利用标准电路构造可推迟中间测量;这里的定义使用最终测量。这些常数表达固定间隔,并不要求答案完全精确。
例题 6.1.3
(奇偶性属于 BQP)
一个一致可生成的可逆电路可将 的奇偶性算入初始为零的输出位:从每个输入位向输出位依次施加受控非门。它必然接受奇校验字符串并拒绝偶校验字符串。因此奇偶性属于 BQP,但该例并未显示量子加速:这个问题用经典方法也很容易求解。
常见错误
(从定义中去掉一致性)
只要求多项式大小的电路而不要求一致生成,会使某些不可判定语言变成可高效判定。设 为任意集合,定义一元语言 。对每个 分别构造时,一个大小为 的电路可以检查输入是否为 ,并使用一个硬编码位表示 与否。若 不可计算,甚至不存在可计算电路生成器能作出这些选择。事实上,若电路可计算地生成、门元素可计算且具有有界误差间隔,就能得到判定 的算法:生成电路,并将其有限维接受概率近似到足够精度,即使模拟需要指数时间也无妨。只有多项式大小、没有一致生成要求,是另一种非一致资源模型。
量子见证与 QMA
固定多项式以限制见证长度 、辅助寄存器长度和验证电路大小。多项式时间一致的电路族 接收经典输入 、 个量子比特的见证态 和新鲜的零辅助寄存器。见证可以是其寄存器上的任意密度算子:它可以是混态,也可以在不同量子比特之间纠缠。若证明者保留与见证纠缠的外部系统,验证器收到的约化态也可能是混态。电路结束后测量指定输出量子比特;令 为结果为 1 的概率。
定义 6.1.4
(QMA)
若这样的验证器对每个经典输入 同时具有以下性质,则称语言 属于 QMA:
- 完备性: 若 ,存在见证 使 。
- 可靠性: 若 ,每个见证 都满足 。
量词次序很重要。“是”情形只需一个好状态;“否”情形必须抵抗任意状态,包括叠加态和混态。验证器必须一致生成且大小为多项式。定义不要求验证器能高效制备见证,也不提供寻找见证的方法。更一般地,承诺问题由互不相交的“是”输入集和“否”输入集组成;验证器只须在这两集合上满足相应条件,承诺之外的行为可以任意。对语言而言,“否”集合是“是”集合的补集。
对固定输入 ,接受概率可写为 ,其中 是见证寄存器上的正算子。其构造是:准备固定输入与辅助寄存器,用验证电路共轭输出接受投影,再对这些固定寄存器取相应矩阵元。由有限维谱定理,所有密度算子上的最大值是 的最大特征值,并且可由纯特征态达到。因此允许混态不改变存在性最优值,但可靠性仍必须覆盖所有状态。此数学刻画并不声称能高效对角化 。
反例模式
测试基态见证不等于可靠性
说法:若“否”实例上每个计算基见证都以至少 的概率被拒绝,则可靠性成立。令单量子比特见证的接受算子为 。可先测试是否为 ,成功时再以独立公平硬币决定是否接受,从而实现此算子。基态 各以 的概率被接受,符合 QMA“否”实例的 上界;但 以 的概率被接受,违反该界。即使测试所有计算基见证,也不能保证对任意量子见证的可靠性;该说法不成立,修正方法是界定 的最大特征值,这里是 。
基本包含关系
命题 6.1.5
(基本包含关系)
且 。
证明
(可逆模拟、被忽略的见证与经典见证)
对 BPP,将多项式时间随机经典算法表示为一致的多项式大小经典电路 ,其中 是多项式长度的均匀随机字符串。保留 并可逆地计算该电路;例如,用可逆门记录中间 Boolean 门的值。对每个随机位施加 Hadamard 门进行准备。所得状态的各分支由 标记且相互正交,测量输出便得到与经典算法完全相同的接受概率。因此 BPP BQP。确定性多项式时间计算是特例。
对于 BQP QMA,让验证器运行 BQP 电路并忽略一个固定大小的见证寄存器。在“是”实例上任何见证都可以;在“否”实例上每个见证都得到相同的拒绝界。
对于 NP QMA,设确定性多项式时间经典验证器 使用多项式长度见证。量子验证器采用由 控制的经典可逆置换电路,保持见证寄存器不变并将 算入输出。若 是“是”实例,将经典接受字符串编码为 即为被接受的量子见证。对固定 ,接受算子为 。因此任意密度算子 ,包括混态或纠缠见证,都满足 。“否”实例中所有 均为零,故所有量子见证都被拒绝。
例题 6.1.6
(可满足性验证器与相干见证)
取 。只有赋值 (即 )满足它,所以 。经典见证 以概率 被接受。相干见证 以概率 被接受,因为 。对不可满足的公式,例如 ,,每个量子见证都被拒绝。这通过 NP 证明可满足性语言属于 QMA;它并未证明量子计算机能够高效找到满足赋值。
常见错误
(把包含关系读成分离)
这些包含关系并未建立 、 或 。上面证明的箭头不能推出其中任何一个结论。预言机模型中的查询复杂性分离也必须保留预言机限定,不能自动当作无相对化复杂性类的分离。
误差放大与见证的微妙之处
命题 6.1.7
(BQP 的误差降低)
若某语言有间隔为 对 的 BQP 电路族,则对奇数 ,运行 个独立副本并取多数,在每个输入上的误差至多为 。
证明
(独立运行的多数)
可在同一经典输入上用新寄存器运行 个相互独立的副本,并在最终输出测量前通过可逆经典电路取多数。原成功概率至少为 时,由 Hoeffding 不等式,多数判断错误的概率至多为 。对“否”实例有类似界。取奇数 ,并使它按所需置信参数多项式增长,就能以多项式开销得到指数小的误差。这里的输入是可以复制的经典基态,并不是在克隆未知量子态。
例题 6.1.8
(三取多数:精确值与上界)
每次运行成功概率为 时,三取多数正确的概率为 。Hoeffding 上界 大于 ,在这里什么也说明不了:只有 足够大时该界才有用。要保证误差至多为 ,可取 ,它是奇数且 ;当 时 。
对 QMA,不能以作弊者提供独立见证为前提证明重复可靠。
定理 6.1.9
(QMA 的并行重复)
取 个见证寄存器,使见证长度变为 ,对每个寄存器各运行一次验证器,并在多数接受时接受。则在“是”实例上存在见证,被接受的概率至少为 ;在“否”实例上每个见证(无论是否纠缠)被接受的概率至多为 。
证明
(对角化单次接受算子)
固定 并对角化单次接受算子 。每次测试的接受效应为 、拒绝效应为 。这些效应分别作用于不同寄存器,因此多数接受算子在 的张量积特征基中为对角算子。“否”实例中可靠性使 的每个特征值至多为 ;每个基向量元组给出独立但不一定同分布的 Bernoulli 结果,各次接受概率至多为 。Hoeffding 不等式将其多数接受概率界在 以下,而任意纠缠密度算子只给出这些对角值的凸组合。“是”实例中最大特征值至少为 ,证明者可提供对应好特征向量的乘积态;这不是验证器克隆未知态。
证明透视
对角化如何排除纠缠的证明者
作弊的证明者可能把 个寄存器纠缠起来,使 次测试的结果不一定独立。不显然的一步是先对角化、再看见证:多数接受算子是相互对易的单次算子的函数,所以在乘积特征基中是对角的,任何见证的接受概率都是对角元的凸组合。每个对角元就是若干独立 Bernoulli 试验取多数的普通概率,可用 Hoeffding 不等式。可靠性只通过特征值界 被用到,而只对单个被测见证的界在这里不够用。没有这一步,就只能对独立见证论证。
Marriott 和 Watrous 的 Quantum Arthur-Merlin Games 给出更强结果:QMA 的完备性和可靠性误差可以用多项式验证器开销降到指数小,而不增加见证长度。这里引用该放大定理,不证明其构造。更强之处在于保持原见证长度。更一般地,只要完备性与可靠性阈值可高效指定且相距至少为逆多项式,就能以多项式开销放大。放大不会将量子见证变成经典见证。
两者都包含于经典的多项式空间计算之内,这限制了它们的大小。
自然的下一个问题
BQP 和 QMA 与经典类相比如何?
两者都包含于经典的多项式空间计算之内,这限制了它们的大小。
标准结果给出 以及 ,其中 是可由多项式时间概率算法判定的语言类,该算法的正确概率严格大于 。这些只是上界:目前并不知道 是否不同于 ,也不知道这两个量子类是否等于 。
练习与解答
快速检查
(一致电路族对每个“是”输入以概率 接受,对每个“否”输入以概率 接受。假设大小为多项式且辅助寄存器初始为零,它是否满足所述 BQP 阈值?)
与 和 比较。
解答 · 答案
可以:在所述一致性与资源假设下, 且 。
快速检查
(一个候选 QMA 验证器在某个“否”输入上以概率 接受一个被测试的见证。这足以证明可靠性吗?)
回想可靠性条件中的量词。
解答 · 答案
不够。可靠性必须对每个见证成立,而不只是一个;另一个状态可能以高概率被接受。
快速检查
(解释见证寄存器保持不变如何使 NP 到 QMA 验证器的接受算子成为对角算子,并控制相干见证的接受概率。)
在见证字符串的基中写出接受算子。
解答 · 答案
可逆验证器保持见证不变,接受算子为对角算子 。对每个密度算子,其接受概率为 ;在“否”实例上每一项都为零。
快速检查
(某验证器在一个见证量子比特上的接受算子为 。求所有密度算子上的最大接受概率,并给出达到它的见证。)
用最大特征值。
解答 · 答案
最大特征值为 ,由 达到。密度算子是纯态的凸组合,没有任何状态能超过最大特征值。
快速检查
(仅由 ,能否推出该包含是严格的,或 NP 包含于 BQP?)
想想单单一个包含关系能说明什么。
解答 · 答案
这两个结论都不能由该包含推出。单凭包含关系不能证明严格性,它本身也没有说明 NP 是否包含于 BQP。
快速检查
(对正整数 ,给出足够的奇数次 BQP 重复次数,使 Hoeffding 误差界至多为 。)
解 。
解答 · 答案
取 。它是奇数且 ,所以 。这是充分的界,不一定是最少的重复次数。
练习 6.1.10
(假设某“否”实例满足 。对三个并行验证器副本,证明即使见证是三寄存器纠缠态,至少两次接受的概率也至多为 。)
核心证明
解答(3)
- 1
对角化单次算子
关键一步
在 的张量积特征基中,三副本的多数接受算子是对角的,所以任何见证的接受概率都是对角元的凸组合。
- 2
界定一个对角元
一个基向量三元组给出独立的接受概率 。至少两次成功的概率对每个 逐坐标不减,所以至多等于 处的值:
依据: 的每个特征值至多为 。
- 3
对纠缠见证下结论
∎任何密度算子,无论是否纠缠,都给出这些对角值的凸组合,每个值至多为 ,所以接受概率至多为 。