Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies

The k-clique problem, which involves identifying complete subgraphs of size k within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography. As the number of nodes n grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations. This work introduces two quantum algorithms for solving the k -clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph j(n,k). By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs. We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets. Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2(5) to 2(20).