CCA³-SGAD: Quantum Amplitude Amplification for Combinatorial Search on Sparse Graphs

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 W[1]-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 W[1]-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.