.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Feedback Arc Set (FAS), well known to be NP-complete, is a fundamental challenge in graph theory and one of the most quintessential problems in discrete optimization. Its applications are broad - including misinformation detection and removal, code optimization in compilers, and biological processes such as cell apoptosis. This work introduces two simple-cycle quantum circuits: (1) a pure Quantum Monte Carlo algorithm whose optimal-arc qubit measures |1 > with per-shot marginal probability Ppt >= 12 (Lemma Lemma 3.1), with the optimal arc identified with probability >= 1-E in N = O(4-2log(a/E)) shots via the empirical-argmax decision rule (Theorem Theorem 3.3), and (2) a Quantum Monte Carlo Separation Oracle with Amplification Construction (MCAC), which empirically preserves the same single-shot marginal. Both algorithms solve FAS in O(|A|) space and O(1) circuit depth - O(log n) end-to-end including QRAM data loading - where the O(1) depth is realized by the NOT-gate variant of the phase-inversion oracle, the C-NOT-gate variant having O(|A|) depth due to its serial control structure. When the input is not a simple cycle, the procedure additionally requires either an O((c+1)(n+e))-time a priori step or an O(n log2 n)-time a posteriori step on a CRCW PRAM. The data-loading overhead of the variational part is amortized by a working QRAM. Provided |C| does not grow exponentially in n, so that the a priori step remains polynomial, both quantum approaches outperform classical algorithms and the state-of-the-art indirect quantum method, which runs in O & lowast;(1.728n) time and exponential space.
Keywords:
Feedback arc set
NP-complete problem
Quantum circuit Monte Carlo randomized
algorithm
Variational algorithm
Polynomial time algorithm
Journal
IF:
4.5
Papers:
925
Citations:
1.2K
Organization
Cited Papers
No cited papers available