arXiv · quant-ph· Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich·· 8 天前精选
一般图最大权完美匹配的量子加速算法
A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
arXiv:2609.39457v1阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich
首次提交：2026-09-30 18:27
研究任务与主要进展
作者提出用于一般图整数边权最大权完美匹配的量子算法，运行时间为 Õ(nm^(2/3)logW)，在稠密区间 m≥n^(3/2) 时优于所述最佳经典组合算法的 Õ(m√n logW)。该方法基于 Duan、Pettie 和 Su 的经典框架，并用量子方法、经典过程的新分析和 QRAM 可实现的数据结构替代部分任务；摘要称其为该问题上首个相对最佳经典组合算法取得渐近改进的量子算法。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
本站判断
基于论文摘要，作者针对一般图整数边权的最大权完美匹配提出量子算法，在稠密图区间将时间复杂度写为 Õ(nm^(2/3)logW)，优于所述经典组合算法的 Õ(m√n logW)。作者称其是首个在该问题上超过最佳经典组合算法的量子算法；这一比较依赖稠密条件和 QRAM 初始化、访问及经典数据结构更新等开销的计入，摘要未提供证明全文、实验或独立复现细节。本站设想：可在相同图规模、边权范围和资源模型下，核验其端到端运行时间及相对经典组合算法的优势。
来源：arXiv · quant-ph · arxiv.org