Spatial search on Johnson graphs by discrete-time quantum walk
Open Access
- 1 June 2022
- journal article
- research article
- Published by IOP Publishing in Journal of Physics A: Mathematical and Theoretical
- Vol. 55 (25) , 255304
Abstract
The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.Keywords
Funding Information
- Conselho Nacional de Desenvolvimento Científico e Tecnológico (308923/2019-7)
- Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro (E-26/202.872/2018)
- KAKENHI (JP20K03551)
This publication has 14 references indexed in Scilit:
- Discrete-time quantum walk search on Johnson graphsQuantum Information Processing, 2019
- Discretization of continuous-time quantum walks via the staggered model with HamiltoniansNatural Computing, 2018
- Partition-based discrete-time quantum walksQuantum Information Processing, 2018
- Spatial Search by Quantum Walk is Optimal for Almost all GraphsPhysical Review Letters, 2016
- The staggered quantum walk modelQuantum Information Processing, 2015
- Spectral and asymptotic properties of Grover walks on crystal latticesJournal of Functional Analysis, 2014
- Quantum Walk Algorithm for Element DistinctnessSIAM Journal on Computing, 2007
- Space searches with a quantum robot2002
- Quantum computation and decision treesPhysical Review A, 1998
- Quantum random walksPhysical Review A, 1993