Faster quantum concentration via Grover's search.

One of the most important challenges in information networks is to gather data from a larger set of nodes to a smaller set of nodes. This can be done via the use of a concentrator architecture in the connection topology. This paper is a proof-of-concept that demonstrates a quantum-based controller in large interconnection networks can asymptotically perform this task faster. We specifically present quantum algorithms for routing concentration assignments on full capacity fat-and-slim concentrators, bounded fat-and-slim concentrators, and regular fat-and-slim concentrators. Classically, the concentration assignment takes O (n) time on all these concentrators, where n is the number of inputs. Powered by Grover's quantum search algorithm, our algorithms take O (n c ln ⁡ c) time, where c is the capacity of the concentrator. Thus, our quantum algorithms are asymptotically faster than their classical counterparts, when c ln 2 ⁡ c = o (n). In general, c = n μ , satisfies c ln 2 ⁡ c = o (n) , implying a time complexity of O (n 0.5 (1 + μ) ln ⁡ n) , for any μ , 0 < μ < 1. [ABSTRACT FROM AUTHOR]