|In this work we study a realisation of the quantum search algorithm on Apollonian network. We show that such networks are sufficient for search tasks due to the small-world and scale-free properties. In particular we present a strategy that allows to design efficient measurement rules regardless of the localization of the marked node. We derive the optimal measurement step for the repeatable search approach and we estimate the complexity of the introduced algorithm. We show that it is possible to obtain quadratic speed-up observed in the Grover's algorithm quadratically reducing the complexity of the network at the same time.