Quantum Monte Carlo randomized algorithm for the Feedback Arc Set problem

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 P opt ≥ 1 2 (Lemma Lemma 3.1 ), with the optimal arc identified with probability ɛ ≥ 1 − ɛ in ɛ N = O ( Δ − 2 log ( a / ɛ ) ) 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 log 2 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 ∗ ( 1 . 72 8 n ) time and exponential space.