arXiv:2611.12746 · v1

$\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize

EQP⊆IP 不相对化

首次提交 2026-11-10 01:28

版本更新 2026-11-10 01:28

雷达观测 2026-11-10 15:22

摘要

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.

作者备注：50 pages, 1 figure, 2 tables