量子模拟的不可快进定理

形式陈述

取整数 $N\ge1$ 。在相干稀疏位置/条目oracle模型中，存在范数为1、每行至多两个非零条目的Hermitian矩阵族，使得在时间 $t=\Theta(N)$ 后把演化模拟到常数误差，必须使用 $\Omega(N)=\Omega(t)$ 次oracle查询。[1, Theorem 3]

这是Hamiltonian模拟的最坏情形不可快进定理。下面给出完整归约：模拟器若对这些输入只用 $o(t)$ 次访问，就能以 $o(N)$ 次bit查询计算 $N$ 位输入的奇偶，违背有界错误量子查询下界。

我们使用算子误差至多 $1/4$ 的模拟保证；只要求对本文指定初态的输出迹距离至多 $1/4$ ，归约也足够。困难族的Hilbert空间维数为 $2(N+1)$ ，可补零到最近的二次幂，只需 $O(\log N)$ 个qubit。

结论不是说每个已知Hamiltonian都需要线性于时间的门数。特殊对角结构、显式谱分解或更强的输入oracle可能允许快进；必须保留“存在困难族”和“规定访问模型”这两个量词。

直觉

把一条路径做成会在确定时间完整传到末端的量子系统。每跨过一条边，就根据一个隐藏输入bit决定是否翻转额外标签。

走完全部边以后，末端标签正好等于所有bit的奇偶。路径每个局部邻居只依赖一个bit，因而查询Hamiltonian的一小块并没有偷偷提供整串奇偶。若模拟能跳过长时间传播而只问很少局部问题，就等于免费算出了奇偶。

两条带标签0与1的加权路径在输入bit为1处交叉，初态沿前缀奇偶路径在指定时间传到末端，末端标签等于全部输入bit的异或。

蓝边标出初始顶点所在的连通路径，灰边属于另一条路径；线条交叉而没有节点时不连接。蓝边不表示中间时刻依次确定停在各顶点，实际传播一般经过位置叠加。

例子与边界

先造一条能完美传输的加权路径

在基 $|0\rangle,\ldots,|N\rangle$ 上，定义

K=\sum_{j=0}^{N-1}w_j \bigl(|j+1\rangle\langle j|+|j\rangle\langle j+1|\bigr), \qquad w_j=\frac{\sqrt{(N-j)(j+1)}}N.

为什么这组权重有特殊作用？只在证明中考虑 $N$ 个qubit的对称态 $|D_j\rangle$ ：它是所有恰有 $j$ 个1的计算基串的等权叠加。由Pauli 比特翻转组成的算子 $N^{-1}\sum_{r=1}^NX_r$ 保持对称子空间，用固定重量字符串计数得到相邻矩阵元为

\frac{\binom Nj(N-j)}{N\sqrt{\binom Nj\binom N{j+1}}} =\frac{\sqrt{(N-j)(j+1)}}N=w_j.

所以它在该子空间上的矩阵正是 $K$ 。各 $X_r$ 对易，范数上界为1，而 $|+\rangle^{\otimes N}$ 给特征值1，因此 $\|K\|=1$ 。

取

T=\frac{\pi N}{2}.

有

e^{-iT N^{-1}\sum_rX_r} =\bigotimes_{r=1}^Ne^{-i\pi X_r/2} =(-i)^N X^{\otimes N}.

它把 $|D_0\rangle$ 送到 $(-i)^N|D_N\rangle$ ，故

e^{-iTK}|0\rangle=(-i)^N|N\rangle. \tag{1}

这里用 $N$ 个qubit只是证明一个 $N+1$ 阶矩阵恒等式；模拟实例本身仍只使用 $O(\log N)$ 个qubit，不需要真的制备这批Dicke态。

把隐藏bit接到每条边

给定未知 $x=(x_1,\ldots,x_N)\in\{0,1\}^N$ ，增加标签 $b\in\{0,1\}$ 。令

H_x=\sum_{j=0}^{N-1}\sum_{b=0}^1w_j \left(|j+1,b\oplus x_{j+1}\rangle\langle j,b| +|j,b\rangle\langle j+1,b\oplus x_{j+1}|\right).

每个顶点最多有左右两个邻居，矩阵实对称且2稀疏。设前缀奇偶 $p_j=x_1\oplus\cdots\oplus x_j$ 、 $p_0=0$ ，置换

D_x|j,b\rangle=|j,b\oplus p_j\rangle

满足 $H_x=D_x(K\otimes I)D_x^\dagger$ 。它仅用于证明相似性，不要求算法免费计算这些前缀。因此 $\|H_x\|=1$ ，并由式 (1) 得

e^{-iTH_x}|0,0\rangle=(-i)^N|N,p_N\rangle. \tag{2}

例如 $N=4$ 、输入1011时，前缀标签依次为 $0,1,1,0,1$ ；权重为 $1/2,\sqrt6/4,\sqrt6/4,1/2$ ，时间 $T=2\pi$ 。末端标签为1，等于四位异或。

一次Hamiltonian查询究竟读了几个输入bit

对位置 $|j,b\rangle$ ，右邻居是 $|j+1,b\oplus x_{j+1}\rangle$ ，左邻居是 $|j-1,b\oplus x_j\rangle$ ；边界缺失邻居用固定虚槽和零值表示。权重只依赖已知 $j,N$ ，不依赖其他输入bit。

给定bit oracle $O_x|i,z\rangle=|i,z\oplus x_i\rangle$ ，可把所需 $x_i$ 查询到一个临时位，算出邻居并异或写入输出，再用一次bit查询清除临时位。因此一次可逆邻居查询最多用两次 $O_x$ 。

条目值查询也一样：先检查两个顶点的层号是否相邻；若相邻，只需查询跨过的那一位，判定标签异或是否匹配，再写入已知权重。临时bit查询与反查询合计两次。无效位置可用固定合法bit索引作占位查询并不写输出，最后清除；这样对叠加地址仍是完整酉实现。

即使模拟器要求这些XOR型oracle的逆或受控版本，也可只在输出写入步骤加控制，同样保持常数次bit调用。不能把一个Hamiltonian查询暗中翻译成读取全部前缀。

推论与应用

从模拟误差到PARITY算法

若模拟器使用 $q$ 次稀疏oracle查询，并在初态 $|0,0\rangle$ 上产生距式 (2) 理想态至多 $1/4$ 的输出，那么测末端标签得到 $p_N$ 的概率至少 $3/4$ 。

把每次Hamiltonian访问替换成上面的两次bit查询，得到至多 $2q$ 次查询的奇偶算法。量子PARITY的有界错误查询下界是 $N/2$ ，所以

2q\ge N/2,\qquad q\ge N/4=\frac{T}{2\pi}.

这证明了所述线性时间下界，且明确包含接口归约的常数开销。

为核对下界的来源，可用量子查询多项式方法： $Q$ 次bit查询后的接受概率是次数至多 $2Q$ 的实多项式。把它线性换成近似奇偶符号 $\chi(x)=(-1)^{\sum_i x_i}$ 的多项式 $r(x)$ ，若错误率严格小于 $1/2$ ，则均匀平均 $\mathbb E[\chi r]>0$ 。将比特编码为 $z_i=(-1)^{x_i}$ 后，Walsh 字符正交性说明任何次数小于 $N$ 的多线性多项式都与 $\chi=\prod_i z_i$ 正交，因此必须 $2Q\ge N$ 。

有限位宽不提供逃生门

权重中的平方根可按已知 $j,N$ 计算到足够精度。若每条边权重误差至多 $\eta$ ，且保持对称写入，则每行误差绝对和至多 $2\eta$ ，所以矩阵算子误差至多 $2\eta$ ；时间 $T$ 上的演化误差至多 $2T\eta$ 。

选 $\eta=O(1/T)$ 就把额外误差压成足够小的常数，只需 $O(\log N)$ 位精度。范数仍有常数上界，并可按已知上界重新缩放到不超过1，时间只相应调整常数尺度。因而线性查询下界不依赖一个不可实现的无限精度数值接口。

结论不排除什么

如果 $H$ 是已知对角矩阵，且能高效相干计算对角元，那么可能直接对每个基态施相位 $e^{-itH_{jj}}$ ；时间很大时，主要代价可以变成角度算术位数。这不违反最坏情形定理，因为该族提供了隐藏路径实例没有的结构。

同样，若输入直接提供任意 $e^{-iHt}$ 或高次幂的单位成本oracle，就已经改变了访问模型。不可快进定理提醒我们：在相位估计、线性系统或行走算法中，长时间受控演化的成本不能只靠把它画成一个方框而消失。

参考资料

[1] Dominic W. Berry, Graeme Ahokas, Richard Cleve and Barry C. Sanders, Efficient Quantum Algorithms for Simulating Sparse Hamiltonians, 2006作者版，§IV Theorem 3与Fig.1：加权路径、隐藏奇偶和查询归约。本页将Hamiltonian显式缩放到范数1，并用对称子空间展开完美传输恒等式及可逆oracle成本。

形式陈述 ​

先造一条能完美传输的加权路径 ​

把隐藏bit接到每条边 ​

一次Hamiltonian查询究竟读了几个输入bit ​

从模拟误差到PARITY算法 ​

有限位宽不提供逃生门 ​

结论不排除什么 ​