Quantum search of many vertices on the joined complete graph

The quantum search on the graph is a very important topic. In this work, we develop a theoretic method on searching of single vertex on the graph [Phys. Rev. Lett. 114 110503 (2015)], and systematically study the search of many vertices on one low-connectivity graph, the joined complete graph. Our results reveal that, with the optimal jumping rate obtained from the theoretical method, we can find such target vertices at the time O(N), where N is the number of total vertices. Therefore, the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.