arXiv · quant-ph· Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber·· 6 天前
解码量子干涉在近似优化中建立可证明的量子优势
A provable quantum advantage for approximate optimization via decoded quantum interferometry
arXiv:2610.02145v2阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber
首次提交：2026-10-02 01:48
研究任务与主要进展
作者在成员查询预言机模型下证明，解码量子干涉（DQI）在折叠最优多项式交集任务中的近似比严格高于任何多项式时间经典算法。典型采样实例上，改进版DQI获得更高分数保证；码率为0.3时，DQI的期望分数约为0.85，而经典算法要以常数概率超过0.65需要超多项式数量的成员查询。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
来源：arXiv · quant-ph · arxiv.org