.png){kind=icon}
返回
Quantum Monte Carlo randomized algorithm for the Feedback Arc Set problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.array.2026.101011.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
反馈弧集（FAS）作为已知为NP完全的问题，是图论中的一个基本挑战，也是离散优化中最具代表性的问题之一。其应用广泛，包括错误信息检测与移除、编译器中的代码优化以及细胞凋亡等生物过程。本研究引入两种简单循环量子电路：(1) 一种纯量子蒙特卡洛算法，其最优弧量子位测量|1⟩的每轮边缘概率Ppt≥1/2（引理3.1），通过经验-argmax决策规则（定理3.3），在N=O(4^{-2}log(a/E))轮中以概率≥1-E识别最优弧；(2) 一种带放大构造的量子蒙特卡洛分离预言机（MCAC），经验上保持相同的单轮边缘概率。两种算法均以O(|A|)空间和O(1)电路深度解决FAS问题——端到端包括QRAM数据加载为O(log n)——其中O(1)深度由相位反转预言机的NOT门变体实现，而C-NOT门变体因串行控制结构具有O(|A|)深度。当输入非简单循环时，流程需额外进行O((c+1)(n+e))时间的先验步骤或O(n log² n)时间的后验步骤在CRCW PRAM上。变分部分的数据加载开销由工作QRAM分摊。若|C|不随n指数增长，使先验步骤保持多项式，两种量子方法均优于经典算法及当前最优间接量子方法（运行时间为O*(1.728^n)且需指数空间）。
Keyword:
Feedback arc set
NP-complete problem
Quantum circuit Monte Carlo randomized
algorithm
Variational algorithm
Polynomial time algorithm
