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.
展开▼
机译:无向图中的最大集团是一组图的顶点的最大子集,其中子集中的每一对元素都相互连接。在本文中,我想提出一种用于量子计算机的算法,该算法可在任意无向图中找到最大团。算法具有O(| V | 2 | V | / 2)最坏情况时间复杂度和O(2 | V | / 2)最佳情况时间复杂度。每种情况下算法的空间复杂度为O(| V |)。一种算法基于格罗弗的版本?用于在未排序列表中查找元素的量子算法,其中可能存在未知数量的解。
展开▼