Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph

Alan Bojić

Abstract


The maximum clique in an undirected graph is the largest subset of  a set of graph's vertices where each pair of elements in the subset is connected. In this paper I would like to propose an algorithm for quantum computers that finds a maximum clique in an arbitrary undirected graph. An algorithm has O(|V|2|V|/2) worst case time complexity and O(2|V|/2) best case time complexity. Algorithm's space complexity for each case is O(|V|). An algorithm is based on a version of Grover's  quantum algorithm for finding element in an unsorted list in which there can be an unknown number of solutions.


Keywords


quantum computing, quantum algorithm, maximum clique

Full Text:

PDF


Journal of Information and Organizational Sciences (Online)
ISSN 1846-9418 (online)
ISSN 1846-3312 (print)