2-Forrelation 的 IQP 电路
2-Forrelation问题为经典查询复杂度和量子查询复杂度提供了最优分离，同时也是用于在预言机条件下区分𝖡𝖰𝖯与𝖯𝖧复杂类的基础问题。这自然引出一个核心问题：解决该问题所需的最小量子资源是多少？研究团队证明，2-Forrelation问题可通过瞬时量子多项式时间（𝖨𝖰𝖯）电路求解——这是一种所有量子门均可交换的受限量子计算模型。具体而言，仅需两个具有两次量子查询能力的𝖨𝖰𝖯电路配合高效经典处理即可实现。对于带符号变体的2-Forrelation问题，单个𝖨𝖰𝖯电路及单次查询即已足够。该结论解答了Girish（arXiv:2510.06385）近期提出的关于交换量子计算能力的开放性问题，并由此证实在预言机O条件下(𝖡𝖯𝖯𝖨𝖰𝖯)O⊈𝖯𝖧O，强化了Raz与Tal（STOC 2019）的研究成果。 这些发现表明𝖨𝖰𝖯电路可应用于经典难解决策问题，为通过𝖨𝖰𝖯电路展示量子优势开辟了新路径，同时规避了采样任务相关的验证难题。研究团队还根据𝖨𝖰𝖯电路接受集的大小证明了其傅里叶增长边界。关键技术在于二次函数Q(x)=∑i
