Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph
|
| Title | Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph |
| Authors | |
| 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. |
| Publisher | University o Zagreb, Faculty of Organization and Informatics, Varaždin |
| Date | 2012-12-13 |
| Source | Journal of Information and Organizational Sciences Vol 36, No 2 (2012) |