Arbitrarily large polynomial speed-up in quantum search with prior knowledge
Przemysław Sadowski · arXiv (Cornell University) · 2015
The aim of this work is to develop a framework for realising quantum network algorithms with the use of prior knowledge about the structure of the network. In particular we consider a network that consists of different types of edges, such that the transitions between nodes result in extra edge-dependent phase shift. We combine amplitude amplification and phase estimation to develop an algorithm for exploring such networks. We show that in such model one is able to perform quantum search algorithms with arbitrarily large polynomial speed-up compared to the quantum search that neglects the extra phase shift. We get hyperbolic decay of the search complexity with exponential growth of the nodes degree.