Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph
<p class="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 ar...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zagreb, Faculty of organization and informatics
2012-12-01
|
| Series: | Journal of Information and Organizational Sciences |
| Subjects: | |
| Online Access: | http://jios.foi.hr/index.php/jios/article/view/624 |
| _version_ | 1818732625743839232 |
|---|---|
| author | Alan Bojić |
| author_facet | Alan Bojić |
| author_sort | Alan Bojić |
| collection | DOAJ |
| description | <p class="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<sup>|V|/2</sup>) worst case time complexity and O(2<sup>|V|/2</sup>) 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.</p> |
| first_indexed | 2024-12-17T23:36:33Z |
| format | Article |
| id | doaj.art-f4976d0bdfea40d5badf4bb9e9134e07 |
| institution | Directory Open Access Journal |
| issn | 1846-3312 1846-9418 |
| language | English |
| last_indexed | 2024-12-17T23:36:33Z |
| publishDate | 2012-12-01 |
| publisher | University of Zagreb, Faculty of organization and informatics |
| record_format | Article |
| series | Journal of Information and Organizational Sciences |
| spelling | doaj.art-f4976d0bdfea40d5badf4bb9e9134e072022-12-21T21:28:32ZengUniversity of Zagreb, Faculty of organization and informaticsJournal of Information and Organizational Sciences1846-33121846-94182012-12-01362662Quantum Algorithm for Finding a Maximum Clique in an Undirected GraphAlan Bojić<p class="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<sup>|V|/2</sup>) worst case time complexity and O(2<sup>|V|/2</sup>) 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.</p>http://jios.foi.hr/index.php/jios/article/view/624quantum computing, quantum algorithm, maximum clique |
| spellingShingle | Alan Bojić Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph Journal of Information and Organizational Sciences quantum computing, quantum algorithm, maximum clique |
| title | Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph |
| title_full | Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph |
| title_fullStr | Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph |
| title_full_unstemmed | Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph |
| title_short | Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph |
| title_sort | quantum algorithm for finding a maximum clique in an undirected graph |
| topic | quantum computing, quantum algorithm, maximum clique |
| url | http://jios.foi.hr/index.php/jios/article/view/624 |
| work_keys_str_mv | AT alanbojic quantumalgorithmforfindingamaximumcliqueinanundirectedgraph |