arXiv · quant-ph· Yuhan Liu, Jose Carrasco, Jens Eisert, Armando Bellante·· 10 天前精选
阿贝尔 StateHSP 的样本与预言机查询复杂度达到最优
The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
arXiv:2609.35656v1阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Yuhan Liu, Jose Carrasco, Jens Eisert, Armando Bellante
首次提交：2026-09-29 01:21
研究任务与主要进展
基于论文摘要，作者确定了有限阿贝尔群 StateHSP 在样本模型和预言机查询模型中的最优复杂度，并提出在查询模型中使用 O(log(|G/H|)/√ε) 次正、逆查询的时间高效量子算法。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
本站判断
该工作围绕阿贝尔 StateHSP 的输入访问模型，给出查询模型下时间高效的量子算法，并同时给出匹配下界；其关键结论是，对态制备酉矩阵及其逆的相干查询带来关于精度 ε 的平方级改进。样本模型下的最优复杂度则表明这一优势依赖相干访问制备线路，实际应用价值还取决于相关问题的误差定义、查询实现成本和资源开销。
来源：arXiv · quant-ph · arxiv.org