Abstract Quantum search via continuous-time quantum walk on truncated simplex lattices is an important example of the quantum search on the structured database. In this letter, when the search target is a set of the marked vertices, the run time of the quantum search and the critical jumping rates are derived. Quantum search with the partial information of the location of the marked vertex is also discussed. Furthermore, with the edge weights suitably adjusted, the three-stage search process can be optimized into a two-stage quantum search algorithm on the second-order truncated simplex lattice.
Abstract Quantum search via continuous-time quantum walk on truncated simplex lattices is an important example of the quantum search on the structured database. In this letter, when the search target is a set of the marked vertices, the run time of the quantum search and the critical jumping rates are derived. Quantum search with the partial information of the location of the marked vertex is also discussed. Furthermore, with the edge weights suitably adjusted, the three-stage search process can be optimized into a two-stage quantum search algorithm on the second-order truncated simplex lattice.
First-order truncated simplex lattices have been used as interesting data structures to explore the properties of quantum search such as the effect of connectivity on search speed [D. A. Meyer and T. G. Wong, Phys. Rev. Lett. 114, 110503 (2015)]. In this paper, we further discuss quantum search algorithms for truncated simplex lattices. We first propose a multistage quantum algorithm for an rth-order truncated simplex lattice with N vertices based on the numerical calculation up to the fifth-order lattice, which requires an (r+1)-stage search process and consumes a run time $\mathrm{\ensuremath{\Theta}}({N}^{(2r+1)/(2r+2)})$ in general. Furthermore, with edge weights suitably adjusted (which increases the connectivity according to certain definitions), we merge the multistage search process into a single stage and achieve a fast quantum search algorithm with an optimal run time $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$ for first-order truncated simplex lattices, which we conjecture is generally true for any-order lattice. Under small noise of the lattice structure, both our multistage and our single-stage search algorithms are quite robust.
The simplex of complete graphs, also known as the first-order truncated simplex lattice, is a network of M+1 identical complete graphs, each with M vertices, such that each clique contains an edge or bridge to every other clique. It contains N=M(M+1) vertices, and previous asymptotic results using a continuous-time quantum walk to search this graph for a single marked vertex have either numerically demonstrated an optimal runtime of O(N), or analytically proved a deterministic success probability of 1, but not both, even when the bridges are weighted. In this paper, we give the first analytical proof of optimal quantum search on this graph, proving that it occurs when the weight of the bridges equals M. In addition, we numerically show that the optimal runtime is achieved more broadly whenever the weight is at least M. Furthermore, the algorithm is also deterministic when the weight scales between M and M, and this is the first example of quantum search on the simplex of complete graphs that is both asymptotically optimal and deterministic. In addition, for weights where the algorithm is nondeterministic, we give a way to find the marked vertex by inspecting neighboring vertices. Finally, while it is known that connectivity is not a reliable indicator of fast quantum search when comparing different graph families, we show that it is also unreliable within the graph family of weighted simplex of complete graphs.
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is O(N) with an asymptotic probability of 1+ o (1), where N is the number of vertices.
Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:
Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.
Continuous-time quantum walks are natural tools for spatial search, where one searches for a marked vertex in a graph. Sometimes the structure of the graph causes the walker to get trapped, such that the probability of finding the marked vertex is limited. We give an example with two linked cliques, proving that the captive probability can be liberated by increasing the weights of the links. This allows the search to succeed with probability 1 without increasing the energy scaling of the algorithm. Further increasing the weights, however, slows the runtime, so the optimal search requires weights that are neither too weak nor too strong.