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

arXiv:2611.17061

Multi-particle quantum walk search on a two-dimensional lattice

Gonçalo Meneses, D. O. Oriekhov

Published Nov 12, 2026• 0 citations
arXivHTMLPDF

Abstract

In the present paper we study the formulation of a search problem and the efficiency of multi-particle quantum walk search algorithms. The discrete-time evolution of each particle in space is treated according to Grover's quantum walk evolution operator. We focus on the local interactions models, where the particles' states are modified only when two or more of them appear on the same grid site. The main focus is given to the two-dimensional grid in space. We study the dependence of the search algorithm asymptotic success time and probability on the interaction strength and the generated maximal entanglement between particles. We show that the interacting and non-interacting two- and three-particle search algorithm attains a constant factor improvement over the single-particle counterpart. In addition, we provide a new generalized model of interactions for multi-particle quantum walks.

DOI
10.48550/arxiv.2611.17061

Related papers

Generalized quantum walk search algorithm

Pulak Ranjan Giri

Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.

International Journal of Quantum Information•Jul 24, 2026•0 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

Optimality conditions for spatial search with multiple marked vertices

Mathieu Roget, Hachem Kadri, Giuseppe Di Molfetta

We contribute to fulfill the long-lasting gap in the understanding of the spatial search with multiple marked vertices. The theoretical framework is that of discrete-time quantum walks (QW), i.e., local unitary matrices that drive the evolution of a single particle on the lattice. QW based search algorithms are well understood when they have to tackle the fundamental problem of finding only one marked element in a $d\text{\ensuremath{-}}\text{dimensional}$ grid and it has been proven they provide a quadratic advantage over classical searching protocols. However, once we consider searching more than one element, the behavior of the algorithm may be affected by the spatial configuration of the marked elements and even the quantum advantage is no longer guaranteed. Here our main contribution is threefold: (i) we provide sufficient conditions for optimality for a multi-items QWSearch algorithm; (ii) we provide analytical evidence that almost, but not all spatial configurations with multiple marked elements are optimal; and (iii) we numerically show that the computational advantage with respect to the classical counterpart is not always certain and it does depend on the proportion of searched elements over the total number of grid points.

arXiv:2201.12937•Physical Review Research•Jul 11, 2023•4 citations

Discrete Time Multi-particle Grover Search

Christopher Um

Grover's algorithm is a quantum search algorithm that produces a quadratic speedup compared to its classical analog, a brute-force algorithm, and has a complexity of$\mathcal{O}(\sqrt{N})$. Past works have shown that Grover's algorithm can asymptotically be improved by generalizing the number of marked sites. I examine Grover's algorithm when the number of searching particles is generalized in discrete time setting, which allows to understand the search algorithm in terms of “interactions” between particles. I provide a novel design of Grover with appended interaction terms to analyze$\mathcal{O}$as$N\rightarrow\infty$. I utilize the eigenvalue perturbation theory to deduce the optimal interaction condition and show that the condition results in an asymptotic improvement denendent upon the number of particles.

International Conference on Communication and Electronics Systems (ICCES)•Jul 8, 2021•0 citations

Two-state quantum walk on two- and three-dimensional lattices

C. M. Chandrashekar

We present a new scheme for a discrete-time quantum walk on two- and three-dimensional lattices using a two-state particle. We use different Pauli basis as translational eigestates for different axis and show that the coin operation, which is necessary for one-dimensional walk is not a necessary requirement for two- and three- dimensional walk but can serve as an additional resource. Using this scheme, the probability distribution from Grover walk using four-state particle and other equivalent schemes on a square lattice using coin operation is reproduced. We also present the Hamiltonian form of evolution which can serve as a general framework to simulate, control, and study the dynamics in different physical systems.

arXiv:1103.2704•Mar 14, 2011•14 citations

Quantum walk search algorithm based on phase matching and circuit cmplementation

Hanwu Chen, Ke Li, Shengmei Zhao

As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.

Acta Physica Sinica•Jan 1, 2015•0 citations
In the present paper we study the formulation of a search problem and the efficiency of multi-particle quantum walk search algorithms. The discrete-time evolution of each particle in space is treated according to Grover's quantum walk evolution operator. We focus on the local interactions models, where the particles' states are modified only when two or more of them appear on the same grid site. The main focus is given to the two-dimensional grid in space. We study the dependence of the search algorithm asymptotic success time and probability on the interaction strength and the generated maximal entanglement between particles. We show that the interacting and non-interacting two- and three-particle search algorithm attains a constant factor improvement over the single-particle counterpart. In addition, we provide a new generalized model of interactions for multi-particle quantum walks.
Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.
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.
We contribute to fulfill the long-lasting gap in the understanding of the spatial search with multiple marked vertices. The theoretical framework is that of discrete-time quantum walks (QW), i.e., local unitary matrices that drive the evolution of a single particle on the lattice. QW based search algorithms are well understood when they have to tackle the fundamental problem of finding only one marked element in a $d\text{\ensuremath{-}}\text{dimensional}$ grid and it has been proven they provide a quadratic advantage over classical searching protocols. However, once we consider searching more than one element, the behavior of the algorithm may be affected by the spatial configuration of the marked elements and even the quantum advantage is no longer guaranteed. Here our main contribution is threefold: (i) we provide sufficient conditions for optimality for a multi-items QWSearch algorithm; (ii) we provide analytical evidence that almost, but not all spatial configurations with multiple marked elements are optimal; and (iii) we numerically show that the computational advantage with respect to the classical counterpart is not always certain and it does depend on the proportion of searched elements over the total number of grid points.
Grover's algorithm is a quantum search algorithm that produces a quadratic speedup compared to its classical analog, a brute-force algorithm, and has a complexity ofO(N)\mathcal{O}(\sqrt{N})O(N​). Past works have shown that Grover's algorithm can asymptotically be improved by generalizing the number of marked sites. I examine Grover's algorithm when the number of searching particles is generalized in discrete time setting, which allows to understand the search algorithm in terms of “interactions” between particles. I provide a novel design of Grover with appended interaction terms to analyzeO\mathcal{O}OasN→∞N\rightarrow\inftyN→∞. I utilize the eigenvalue perturbation theory to deduce the optimal interaction condition and show that the condition results in an asymptotic improvement denendent upon the number of particles.
We present a new scheme for a discrete-time quantum walk on two- and three-dimensional lattices using a two-state particle. We use different Pauli basis as translational eigestates for different axis and show that the coin operation, which is necessary for one-dimensional walk is not a necessary requirement for two- and three- dimensional walk but can serve as an additional resource. Using this scheme, the probability distribution from Grover walk using four-state particle and other equivalent schemes on a square lattice using coin operation is reproduced. We also present the Hamiltonian form of evolution which can serve as a general framework to simulate, control, and study the dynamics in different physical systems.
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.