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• 2 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

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•4 citations

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

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•8 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

Circuit Synthesis of Maximum Clique Problem using Combinatorial Approach of Classical-Quantum Hybrid Model.

Arpita Sanyal, Amit Saha, Banani Saha +1 more

In the Maximum Clique Problem, the objective is to find a clique whose size is maximum among all the cliques of an arbitrary undirected and unweighted graph. Maximum Clique Problem resembles with minimum vertex cover problem, independent set problem. As it is an NP-hard problem, no polynomial time algorithms can be found. As these problems have several important practical applications such as information retrieval, community detection in network, spatial data mining etc, it is of great interest to try to synthesis the circuit of Maximum Clique Problem. In classical computing any brute-force solution to the Maximum Clique Problem requires an exponential increase of time with the size of the problem (i.e., with time complexity of $O(2^n)$). In this paper, Maximum Clique Problem has been solved using combinatorial approach of Grover's search algorithm. An algorithm has been proposed that auto-generates the circuit for any given undirected and unweighted graph which makes the approach generalized in nature for Maximum Clique Problem. Computational speed up is achieved by using our approach with the help of quantum mechanical effect that is quantum superposition. We have simulated the proposed circuit using IBM's QISkit platform and verified its correctness.

•Mar 10, 2020•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 .
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.
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.
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.
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.
In the Maximum Clique Problem, the objective is to find a clique whose size is maximum among all the cliques of an arbitrary undirected and unweighted graph. Maximum Clique Problem resembles with minimum vertex cover problem, independent set problem. As it is an NP-hard problem, no polynomial time algorithms can be found. As these problems have several important practical applications such as information retrieval, community detection in network, spatial data mining etc, it is of great interest to try to synthesis the circuit of Maximum Clique Problem. In classical computing any brute-force solution to the Maximum Clique Problem requires an exponential increase of time with the size of the problem (i.e., with time complexity of O(2n)O(2^n)O(2n)). In this paper, Maximum Clique Problem has been solved using combinatorial approach of Grover's search algorithm. An algorithm has been proposed that auto-generates the circuit for any given undirected and unweighted graph which makes the approach generalized in nature for Maximum Clique Problem. Computational speed up is achieved by using our approach with the help of quantum mechanical effect that is quantum superposition. We have simulated the proposed circuit using IBM's QISkit platform and verified its correctness.