Robust Quantum Circuit for Clique Problem with Intermediate Qudits

Abstract

Clique problem has a wide range of applications due to its pattern matching ability. There are various formulation of clique problem like $k$-clique problem, maximum clique problem, etc. The $k$-Clique problem, determines whether an arbitrary network has a clique or not whereas maximum clique problem finds the largest clique in a graph. It is already exhibited in the literature that the $k$-clique or maximum clique problem (NP-problem) can be solved in an asymptotically faster manner by using quantum algorithms as compared to the conventional computing. Quantum computing with higher dimensions is gaining popularity due to its large storage capacity and computation power. In this article, we have shown an improved quantum circuit implementation for the $k$-clique problem and maximum clique problem (MCP) with the help of higher-dimensional intermediate temporary qudits for the first time to the best of our knowledge. The cost of state-of-the-art quantum circuit for $k$-clique problem is colossal due to a huge number of $n$-qubit Toffoli gates. We have exhibited an improved cost and depth over the circuit by applying a generalized $n$-qubit Toffoli gate decomposition with intermediate ququarts (4-dimensional qudits).

arXiv comment19 pages, 22 figures

References in corpus (20)

• Community detection in graphs
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum random walks - an introductory overview
• Tight bounds on quantum searching
• Qudits and high-dimensional quantum computing
• An example of the difference between quantum and classical random walks
• Multi-valued Logic Gates for Quantum Computation
• Experimental realization of Dicke states of up to six qubits for multiparty quantum networking
• The General Quantum Interference Principle and the Duality Computer
• Fixed-point quantum search with an optimal number of queries
• Phase matching in quantum searching
• Deterministic Preparation of Dicke States
• Decomposing the generalized Toffoli gate with qutrits
• Asymptotically Improved Circuit for $d$-ary Grover's Algorithm with Advanced Decomposition of $n$-qudit Toffoli Gate
• Quantum speed-up in solving the maximal clique problem
• Generalized Toffoli gate decomposition using ququints: Towards realizing Grover's algorithm with qudits
• Finding Small and Large k-Clique Instances on a Quantum Computer
• A Query-based Quantum Eigensolver
• Quantum Algorithms for the Triangle Problem
• Circuit Design for Clique Problem and Its Implementation on Quantum Computer

Cited by in corpus (1)

• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods