Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Quantum Information

Connectivity effects in the coined quantum walk search algorithm

Neil B. Lovett, Viv M. Kendon

Published Jan 1, 2011• 0 citations
Publisher

Abstract

We show numerically how the quantum walk search algorithm depends on both the spatial dimension and connectivity of the structure being searched. We investigate this using a simple form of tunnelling to interpolate between lattices.
DOI
10.1364/icqi.2011.qmi16

Related papers

The quantum walk search algorithm: factors affecting efficiency

Neil B. Lovett, Matthew Everitt, Robert M. Heath +1 more

We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.

arXiv:1110.4366•Mathematical Structures in Computer Science•May 16, 2018•17 citations

Spatial search via non-linear quantum walk

Mahdi Ebrahimi Kahou

One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.

•Jan 1, 2013•1 citation

Scaling hypothesis of a spatial search on fractal lattices using a quantum walk

Rei Sato, Tetsuro Nikuni, Shohei Watabe

A quantum spatial search problem on fractal lattices, such as Sierpinski carpets and Menger sponges, is studied numerically. The results confirmed various conjectures on the relationship between the number of oracle calls needed for a search with respect to the number of sites and spatial dimensions.

arXiv:1908.11827•Physical Review A•Feb 10, 2020•9 citations

Coined quantum walks on percolation graphs

Godfrey Leung, Paul Knott, Joe Bailey +1 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several quantum algorithms and have been used to model processes such as transport in spin chains and quantum chemistry. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well studied on regular structures and also shown to be sensitive to defects and imperfections in the lattice. As a simple example of a disordered system, we consider percolation lattices, in which edges or sites are randomly missing, interrupting the progress of the quantum walk. We use numerical simulation to study the properties of coined quantum walks on these percolation lattices in one and two dimensions. In one dimension (the line), we introduce a simple notion of quantum tunnelling and determine how this affects the properties of the quantum walk as it spreads. On two-dimensional percolation lattices, we show how the spreading rate varies from linear in the number of steps down to zero as the percolation probability decreases towards the critical point. This provides an example of fractional scaling in quantum-walk dynamics.

arXiv:1006.1283•New Journal of Physics•Dec 9, 2010•49 citations

Publisher’s Note: Spatial Search by Quantum Walk is Optimal for Almost All Graphs [Phys. Rev. Lett.116, 100501 (2016)]

Shantanav Chakraborty, Leonardo Novo, Andris Ambainis +1 more

This corrects the article DOI: 10.1103/PhysRevLett.116.100501.

Physical Review Letters•Jun 13, 2016•3 citations

Kvanttikävelyhakuoperaattorin tutkiminen ominaisvektorien avulla.

Niklas Keckman

Quantum walks are the quantum mechanical counterpart to classical random walks. Similarly to random walks, in quantum walks a walker moves on a graph structure from one node to another governed by some stochastic process. Unlike random walks, quantum walks exhibit quantum superposition. This allows the walker to be in multiple nodes simultaneously. Due to quantum superposition quantum walks have been applied to cryptography, optimization, graph theory and spatial search problems. The goal of a spatial search problem is to find a target node from a graph structure by moving from one node to another along the edges of the graph. On certain graph structures quantum walks are able to find the target node of the search faster than classical random walks. However, determining the speedup provided by the quantum walk can be difficult to do analytically, especially when there are multiple target nodes. Therefore, it is of importance to investigate numerical approaches for approximating the dynamics of quantum walks. This Bachelor's thesis concerns a heuristic method for analyzing the dynamics of discrete-time coined quantum walk (DTCQW) search algorithms used for finding a specific node or a set of nodes on a two-dimensional lattice graph. Instead of simulating the walk fully, the heuristic method uses the eigenvectors and eigenvalues of a unitary evolution operator that governs the walk dynamics to approximate the probability of the DTCQW search algorithm finding a node that is a target of the search. This work goes over two slightly different DTCQW search algorithms. One of these is a instance of the DTCQW search algorithm that has been investigated in previous literature (referred to as the standard DTCQW search algorithm). The other one is a slightly modified version of the standard DTCQW search algorithm (referred to as the modified DTCQW search algorithm) In this work, the method was first applied to the standard DTCQW search algorithm to compare the results to previously known analytical results. The goal of this was to showcase that by using the method one can arrive at similar results as with analytical approaches. In addition, the method was used to investigate the modified DTCQW search algorithm. This was done to give numerical showing that the modified DTCQW search algorithm is able to find certain target node formations with a higher probability than the standard DTCQW search algorithm. The results of this work show that the method can approximate the analytical results using only a couple of eigenvector-eigenvalue pairs of the unitary evolution operator. Therefore, it can be considered as a cost-efficient alternative for simulating the complete quantum walk. Using the method it can be seen that the modified search algorithm finds target nodes that are adjacent to each other in the graph structure with a high probability. Additionally, the results show that the modified search algorithm only has a small chance of finding target nodes that are not adjacent to other target nodes. This gives numerical showing that the modified search algorithm behaves differently from the standard search algorithm and could therefore be used for different applications.

•Jul 1, 2026•0 citations
We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.
One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.
Quantum walks, both discrete (coined) and continuous time, form the basis of several quantum algorithms and have been used to model processes such as transport in spin chains and quantum chemistry. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well studied on regular structures and also shown to be sensitive to defects and imperfections in the lattice. As a simple example of a disordered system, we consider percolation lattices, in which edges or sites are randomly missing, interrupting the progress of the quantum walk. We use numerical simulation to study the properties of coined quantum walks on these percolation lattices in one and two dimensions. In one dimension (the line), we introduce a simple notion of quantum tunnelling and determine how this affects the properties of the quantum walk as it spreads. On two-dimensional percolation lattices, we show how the spreading rate varies from linear in the number of steps down to zero as the percolation probability decreases towards the critical point. This provides an example of fractional scaling in quantum-walk dynamics.
Quantum walks are the quantum mechanical counterpart to classical random walks. Similarly to random walks, in quantum walks a walker moves on a graph structure from one node to another governed by some stochastic process. Unlike random walks, quantum walks exhibit quantum superposition. This allows the walker to be in multiple nodes simultaneously. Due to quantum superposition quantum walks have been applied to cryptography, optimization, graph theory and spatial search problems. The goal of a spatial search problem is to find a target node from a graph structure by moving from one node to another along the edges of the graph. On certain graph structures quantum walks are able to find the target node of the search faster than classical random walks. However, determining the speedup provided by the quantum walk can be difficult to do analytically, especially when there are multiple target nodes. Therefore, it is of importance to investigate numerical approaches for approximating the dynamics of quantum walks. This Bachelor's thesis concerns a heuristic method for analyzing the dynamics of discrete-time coined quantum walk (DTCQW) search algorithms used for finding a specific node or a set of nodes on a two-dimensional lattice graph. Instead of simulating the walk fully, the heuristic method uses the eigenvectors and eigenvalues of a unitary evolution operator that governs the walk dynamics to approximate the probability of the DTCQW search algorithm finding a node that is a target of the search. This work goes over two slightly different DTCQW search algorithms. One of these is a instance of the DTCQW search algorithm that has been investigated in previous literature (referred to as the standard DTCQW search algorithm). The other one is a slightly modified version of the standard DTCQW search algorithm (referred to as the modified DTCQW search algorithm) In this work, the method was first applied to the standard DTCQW search algorithm to compare the results to previously known analytical results. The goal of this was to showcase that by using the method one can arrive at similar results as with analytical approaches. In addition, the method was used to investigate the modified DTCQW search algorithm. This was done to give numerical showing that the modified DTCQW search algorithm is able to find certain target node formations with a higher probability than the standard DTCQW search algorithm. The results of this work show that the method can approximate the analytical results using only a couple of eigenvector-eigenvalue pairs of the unitary evolution operator. Therefore, it can be considered as a cost-efficient alternative for simulating the complete quantum walk. Using the method it can be seen that the modified search algorithm finds target nodes that are adjacent to each other in the graph structure with a high probability. Additionally, the results show that the modified search algorithm only has a small chance of finding target nodes that are not adjacent to other target nodes. This gives numerical showing that the modified search algorithm behaves differently from the standard search algorithm and could therefore be used for different applications.