arXiv · quant-ph· Stuart Wayland, Zackary Jorquera, Alexandra Kolla·· 6 天前精选
稠密双部扩展图上的经典双重量子Max-Cut算法
Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
arXiv:2610.03670v1阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Stuart Wayland, Zackary Jorquera, Alexandra Kolla
首次提交：2026-10-03 01:40
研究任务与主要进展
作者提出一个经典随机多项式时间算法，用于求解稠密平衡双部扩展图上的自旋1/2反铁磁Heisenberg模型，即量子Max-Cut，并可在关于n和1/ε的多项式时间内估计基态能量及任意基态边关联。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
本站判断
该工作针对双重量子Max-Cut的经典复杂性开放问题，提出适用于稠密平衡双部扩展图的经典随机多项式时间算法，并用于估计基态能量及任意基态边关联。技术增量在于利用完美匹配上的马尔可夫链和图的扩展性控制采样效率，但结论范围限于所述图类，当前材料仅包含论文摘要，证明细节与基线尚未提供。本站设想：可检验该方法对非平衡双部图和不同密度条件的适用范围及采样成本变化。
来源：arXiv · quant-ph · arxiv.org