EQP⊆IP 不相对化
$\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize
Sinan Oral, Supartha Podder
AI 速读 基于摘要
作者构造递归预言机 O 与一元语言 L，使 L 属于 EQP^O 但不属于 IP^O∪PH^O，从而把 BQP 与 IP 的预言机分离强化到精确量子计算。
quant-ph · cs.CC
查看原文摘要
We construct a recursive oracle $O$ and a unary language $L\in\mathsf{EQP}^O\setminus(\mathsf{IP}^O\cup\mathsf{PH}^O)$, strengthening the $\mathsf{BQP}$ versus $\mathsf{IP}$ oracle separation of Bouland et al. to exact quantum computation. The separation is based on a variant of the Forrelation problem in which the normalized correlation of one Boolean function with the Fourier transform of another is promised to be exactly $+1/2$ or $-1/2$. The main technical contribution is a repair method that constructs distributions supported on these exact levels while preserving the indistinguishability needed for the $\mathsf{IP}$ and $\mathsf{PH}$ lower bounds. A uniform polynomial-time quantum algorithm distinguishes the two cases with certainty using only three oracle queries.