Faster Quantum Concentration via Grover's Search

Abstract

We 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(\sqrt{nc}\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^{\mu },$ satisfies $c{\ln }^{2}c=o(n),$ implying a time complexity of $O(n^{0.5(1+\mu )}\ln n),$ for any $\mu ,0<\mu <1.$