We present CCA³-SGAD (Constraint-Compressed Adaptive Amplitude Amplification for Sparse Graph Anomaly Detection), a quantum algorithm for combinatorial search on sparse graphs where classical methods are W1-hard. Building on Brassard et al. (2000), we make two primary contributions: (1) We formally define Weighted Sparse Anomalous Subgraph Detection (WSASD) — a new problem class targeting power grid cascade detection, financial fraud ring identification, and epidemiological contact tracing — and prove it is W1-hard parameterised by k. (2) We derive the first formal crossover condition determining when quantum search beats the best classical algorithm that also employs the same heuristic, explicitly accounting for oracle construction cost. The algorithm requires substantially fewer resources than chemistry-scale fault-tolerant projections (364 logical qubits, 63,700 T-gates, 50 circuit repetitions). We provide multi-layer evidence including statevector simulation confirmation (Pearson r=0.9861), real-data validation on the public IEEE 118-bus test case, and hardware execution on IBM Heron r2.
Harsha Vardhan Routhu (Tue,) studied this question.