Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM International Conference on Computing Frontiers (CF)

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

Simone Perriello

Published May 28, 2025• 3 citations
Publisher

Abstract

The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 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 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).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 .

DOI
10.1145/3719276.3725200

Related papers

Solving the Subset Sum Problem via Quantum Walk Search

Giacomo Lancellotti, Simone Perriello, Alessandro Barenghi +1 more

Quantum walk-based search algorithms have demonstrated an asymptotic quadratic speedup compared to classical search methods. Formulating a generic search problem as a (quantum) search over a graph makes the efficiency of the algorithm to be closely dependent on the properties of the graph itself. In this work, we present a complete implementation of a quantum walk search procedure on Johnson graphs, speeding up the solution of the Subset Sum Problem, a well-known computational problem with applications in resource allocation, scheduling, and cryptanalysis. We provide a detailed design of each sub-circuit, quantifying their costs in terms of gate count, circuit depth, and qubit width, and exhibit all figures of merit as a function of the problem parameters. Our approach includes two distinct implementations: one that minimizes qubit usage and another focused on optimizing circuit depth. We compare our solutions against the unstructured Grover based quantum search algorithm, demonstrating a reduction of the cost on terms of T-count and T-depth, for practically solvable instances. The proposed design serves as a foundational building block for the development of efficient quantum search algorithms that can be modeled on Johnson graphs, bridging the gap with existing theoretical complexity analyses.

IEEE Transactions on Computers•Oct 27, 2025•1 citation

Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem

Giacomo Lancellotti, Simone Perriello, Alessandro Barenghi +1 more

Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the T-count and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.

ACM/IEEE Design Automation Conference (DAC)•Jun 23, 2024•6 citations

Circuit design for clique problem and its implementation on quantum computer

Arpita Sanyal, Amit Saha, Banani Saha +1 more

Abstract Finding cliques in a graph has a wide range of applications due to its pattern matching ability. The k ‐clique problem, a subset of the clique problem, determines whether or not an arbitrary network has a clique of size k . Modern‐day applications include a variation of the k ‐clique problem that lists all cliques of size k . However, the quantum implementation of such a variation of the k ‐clique problem has not been addressed yet. In this work, apart from the theoretical solution of such a k ‐clique problem, practical quantum‐gate‐based implementation has been addressed using Grover's algorithm. In a classical‐quantum hybrid architecture, this approach is extended to build the circuit for the maximum clique problem. Our technique is generalised since the program automatically builds the circuit for any given undirected and unweighted graph and any chosen k . For a small k with regard to a big graph, the proposed solution to addressing the k ‐clique issue has shown a reduction in qubit cost and circuit depth when compared to the state‐of‐the‐art approach. A framework is also presented for mapping the automated generated circuit for clique problems to quantum devices. Using IBM's Qiskit, an analysis of the experimental results is demonstrated.

arXiv:2004.10596•IET Quantum Communication•Dec 9, 2021•12 citations

Quantum speedup in solving the maximal-clique problem

Weng-Long Chang, Qi Yu, Zhaokai Li +3 more

The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph $G$ with $n$ vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, $O(\sqrt{{2}^{n}})$ and $O({n}^{2})$. With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph $G$ with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.

arXiv:1803.11356•Physical Review A•Mar 29, 2018•18 citations

Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem

Yu. A. Biriukov, R. D. Morozov, I. V. Dyakonov +1 more

This paper addresses the problem of finding the densest $k$-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.

quant-pharXiv:2604.27782•May 1, 2026•0 citations

Hybrid and Quantum Graph Algorithms via Quantum Array Search: Applications to Hamiltonian Paths and Path Counting

Ethan Hunt, Hieu Nguyen, Dheeraj Sai Tukkugudam +2 more

In this paper, we introduce novel hybrid and quantum algorithms for fundamental graph problems, specifically the Hamiltonian Path Problem (HPP) and$\langle s, t\rangle$Path Counting Problem. By leveraging quantum array search techniques, rooted in amplitude amplification and applied in new and effective ways, we achieve significant reductions in time complexity compared to classical methods. We propose a quantum algorithm that solves the HPP on a special class of graphs known as clique trees in$O(\sqrt{n})$time. Additionally, we develop a hybrid quantum-classical algorithm for counting simple$\langle s, t\rangle$paths with a time complexity of$O\left(\binom{m}{n} \sqrt{n}\right)$for large$m$, improving over the classical baseline. Beyond these algorithmic contributions, we present a fixedparameter tractable (FPT) algorithm for identifying clique trees, enabling their structural properties to be efficiently leveraged. We also explore additional algorithmic results related to clique trees, including insights into their treewidth and chromatic number. Overall, our work demonstrates how quantum and hybrid approaches can offer practical advantages for solving challenging graph problems, specifically applications to Hamiltonian paths and path counting problems.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations
The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 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 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).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 .
Quantum walk-based search algorithms have demonstrated an asymptotic quadratic speedup compared to classical search methods. Formulating a generic search problem as a (quantum) search over a graph makes the efficiency of the algorithm to be closely dependent on the properties of the graph itself. In this work, we present a complete implementation of a quantum walk search procedure on Johnson graphs, speeding up the solution of the Subset Sum Problem, a well-known computational problem with applications in resource allocation, scheduling, and cryptanalysis. We provide a detailed design of each sub-circuit, quantifying their costs in terms of gate count, circuit depth, and qubit width, and exhibit all figures of merit as a function of the problem parameters. Our approach includes two distinct implementations: one that minimizes qubit usage and another focused on optimizing circuit depth. We compare our solutions against the unstructured Grover based quantum search algorithm, demonstrating a reduction of the cost on terms of T-count and T-depth, for practically solvable instances. The proposed design serves as a foundational building block for the development of efficient quantum search algorithms that can be modeled on Johnson graphs, bridging the gap with existing theoretical complexity analyses.
Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the T-count and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.
Abstract Finding cliques in a graph has a wide range of applications due to its pattern matching ability. The k ‐clique problem, a subset of the clique problem, determines whether or not an arbitrary network has a clique of size k . Modern‐day applications include a variation of the k ‐clique problem that lists all cliques of size k . However, the quantum implementation of such a variation of the k ‐clique problem has not been addressed yet. In this work, apart from the theoretical solution of such a k ‐clique problem, practical quantum‐gate‐based implementation has been addressed using Grover's algorithm. In a classical‐quantum hybrid architecture, this approach is extended to build the circuit for the maximum clique problem. Our technique is generalised since the program automatically builds the circuit for any given undirected and unweighted graph and any chosen k . For a small k with regard to a big graph, the proposed solution to addressing the k ‐clique issue has shown a reduction in qubit cost and circuit depth when compared to the state‐of‐the‐art approach. A framework is also presented for mapping the automated generated circuit for clique problems to quantum devices. Using IBM's Qiskit, an analysis of the experimental results is demonstrated.
The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph GGG with nnn vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O(2n)O(\sqrt{{2}^{n}})O(2n​) and O(n2)O({n}^{2})O(n2). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph GGG with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.
This paper addresses the problem of finding the densest kkk-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
In this paper, we introduce novel hybrid and quantum algorithms for fundamental graph problems, specifically the Hamiltonian Path Problem (HPP) and⟨s,t⟩\langle s, t\rangle⟨s,t⟩Path Counting Problem. By leveraging quantum array search techniques, rooted in amplitude amplification and applied in new and effective ways, we achieve significant reductions in time complexity compared to classical methods. We propose a quantum algorithm that solves the HPP on a special class of graphs known as clique trees inO(n)O(\sqrt{n})O(n​)time. Additionally, we develop a hybrid quantum-classical algorithm for counting simple⟨s,t⟩\langle s, t\rangle⟨s,t⟩paths with a time complexity ofO((mn)n)O\left(\binom{m}{n} \sqrt{n}\right)O((nm​)n​)for largemmm, improving over the classical baseline. Beyond these algorithmic contributions, we present a fixedparameter tractable (FPT) algorithm for identifying clique trees, enabling their structural properties to be efficiently leveraged. We also explore additional algorithmic results related to clique trees, including insights into their treewidth and chromatic number. Overall, our work demonstrates how quantum and hybrid approaches can offer practical advantages for solving challenging graph problems, specifically applications to Hamiltonian paths and path counting problems.