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:2410.03269 · Physica Scripta

Impact of bivariate gaussian potentials on quantum walks for spatial search

Franklin de Lima Marquezino, Raqueline A. M. Santos

Published Feb 4, 2025• 1 citation
arXivHTMLPDF

Abstract

Abstract Quantum search algorithms are crucial for exploring large solution spaces, but their robustness to environmental perturbations, such as noise or disorder, remains a critical challenge. We examine the impact of biased disorder potentials modeled by a bivariate Gaussian distribution function on the dynamics of quantum walks in spatial search problems. Building on the Ambainis-Kempe-Rivosh (AKR) model for searching on a two-dimensional grid, we incorporate potential fields to investigate how changes in standard deviation and normalization of the bivariate Gaussian function impact the performance of the search algorithm. Our results show that the quantum walk closely mirrors the AKR algorithm when the standard deviation is small but exhibits a rapid decay in success probability as the standard deviation increases. This behavior demonstrates how the bivariate Gaussian can effectively model a noisy oracle within the AKR algorithm. Additionally, we compare the AKR-based model with an alternative quantum walk model using a Hadamard coin and standard shift. These findings contribute to understanding the robustness of quantum walk search algorithms, and provide insights into how quantum walks can be applied to optimization algorithms.

DOI
10.1088/1402-4896/adb223

Related papers

Quantum walks on two-dimensional grids with multiple marked locations

Nikolajs Nahimovs, Alexander Rivosh

The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of $k$ marked locations for which the number of steps of the algorithm differs by $Ω(\sqrt{k})$ factor. Second, we present two configurations of $k$ and $\sqrt{k}$ marked locations having the same number of steps and probability to find a marked location.

arXiv:1507.03788•Jul 14, 2015•3 citations

Quantum Spatial Search with Electric Potential: Long-Time Dynamics and Robustness to Noise

Thibault Fredon, Julien Zylberman, Pablo Arnault +1 more

We present various results on the scheme introduced in a previous work, which is a quantum spatial-search algorithm on a two-dimensional (2D) square spatial grid, realized with a 2D Dirac discrete-time quantum walk (DQW) coupled to a Coulomb electric field centered on the the node to be found. In such a walk, the electric term acts as the oracle of the algorithm, and the free walk (i.e., without electric term) acts as the “diffusion” part, as it is called in Grover’s algorithm. The results are the following. First, we run long time simulations of this electric Dirac DQW, and observe that there is a second localization peak around the node marked by the oracle, reached in a time O(N), where N is the number of nodes of the 2D grid, with a localization probability scaling as O(1/lnN). This matches the state-of-the-art 2D-DQW search algorithms before amplitude amplification We then study the effect of adding noise on the Coulomb potential, and observe that the walk, especially the second localization peak, is highly robust to spatial noise, more modestly robust to spatiotemporal noise, and that the first localization peak is even highly robust to spatiotemporal noise.

arXiv:2210.13920•Entropy•Dec 5, 2022•4 citations

Quantum Walks on Two-Dimensional Grids with Multiple Marked Locations

Nikolajs Nahimovs, Alexander Rivosh

The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations. In this paper, we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of [Formula: see text] marked locations for which the number of steps of the algorithm differs by a factor of [Formula: see text]. Second, we present two configurations of [Formula: see text] and [Formula: see text] marked locations having the same number of steps and probability of finding a marked location.

International Journal of Foundations of Computer Science•Jun 1, 2018•3 citations

Noise-resilient spatial search with lackadaisical quantum walks

Gabriel Mauricio Oswald Vieira, Nelson Maculan, Franklin de Lima Marquezino

Abstract Quantum walks are a powerful framework for the development of quantum algorithms, with lackadaisical quantum walks (LQWs) standing out as an efficient model for spatial search. In this work, we investigate how broken-link decoherence affects the performance of LQW-based search on a two-dimensional toroidal grid. We show through numerical simulations that while decoherence drives the loopless walk toward a uniform distribution and eliminates its search capability, the inclusion of self-loops significantly mitigates this effect. In particular, even under noise, the marked vertex remains identifiable with probability well above uniform, demonstrating that self-loops enhance the robustness of LQWs in realistic scenarios. These findings extend the known advantages of LQWs from the noiseless setting to noisy environments, consolidating self-loops as a valuable resource for designing resilient quantum search algorithms.

arXiv:2508.13462•Quantum Information Processing•May 20, 2026•0 citations

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.

•May 16, 2018•15 citations

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•10 citations
Abstract Quantum search algorithms are crucial for exploring large solution spaces, but their robustness to environmental perturbations, such as noise or disorder, remains a critical challenge. We examine the impact of biased disorder potentials modeled by a bivariate Gaussian distribution function on the dynamics of quantum walks in spatial search problems. Building on the Ambainis-Kempe-Rivosh (AKR) model for searching on a two-dimensional grid, we incorporate potential fields to investigate how changes in standard deviation and normalization of the bivariate Gaussian function impact the performance of the search algorithm. Our results show that the quantum walk closely mirrors the AKR algorithm when the standard deviation is small but exhibits a rapid decay in success probability as the standard deviation increases. This behavior demonstrates how the bivariate Gaussian can effectively model a noisy oracle within the AKR algorithm. Additionally, we compare the AKR-based model with an alternative quantum walk model using a Hadamard coin and standard shift. These findings contribute to understanding the robustness of quantum walk search algorithms, and provide insights into how quantum walks can be applied to optimization algorithms.
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of kkk marked locations for which the number of steps of the algorithm differs by Ω(k)Ω(\sqrt{k})Ω(k​) factor. Second, we present two configurations of kkk and k\sqrt{k}k​ marked locations having the same number of steps and probability to find a marked location.
We present various results on the scheme introduced in a previous work, which is a quantum spatial-search algorithm on a two-dimensional (2D) square spatial grid, realized with a 2D Dirac discrete-time quantum walk (DQW) coupled to a Coulomb electric field centered on the the node to be found. In such a walk, the electric term acts as the oracle of the algorithm, and the free walk (i.e., without electric term) acts as the “diffusion” part, as it is called in Grover’s algorithm. The results are the following. First, we run long time simulations of this electric Dirac DQW, and observe that there is a second localization peak around the node marked by the oracle, reached in a time O(N), where N is the number of nodes of the 2D grid, with a localization probability scaling as O(1/lnN). This matches the state-of-the-art 2D-DQW search algorithms before amplitude amplification We then study the effect of adding noise on the Coulomb potential, and observe that the walk, especially the second localization peak, is highly robust to spatial noise, more modestly robust to spatiotemporal noise, and that the first localization peak is even highly robust to spatiotemporal noise.
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations. In this paper, we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of [Formula: see text] marked locations for which the number of steps of the algorithm differs by a factor of [Formula: see text]. Second, we present two configurations of [Formula: see text] and [Formula: see text] marked locations having the same number of steps and probability of finding a marked location.
Abstract Quantum walks are a powerful framework for the development of quantum algorithms, with lackadaisical quantum walks (LQWs) standing out as an efficient model for spatial search. In this work, we investigate how broken-link decoherence affects the performance of LQW-based search on a two-dimensional toroidal grid. We show through numerical simulations that while decoherence drives the loopless walk toward a uniform distribution and eliminates its search capability, the inclusion of self-loops significantly mitigates this effect. In particular, even under noise, the marked vertex remains identifiable with probability well above uniform, demonstrating that self-loops enhance the robustness of LQWs in realistic scenarios. These findings extend the known advantages of LQWs from the noiseless setting to noisy environments, consolidating self-loops as a valuable resource for designing resilient quantum search algorithms.
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.
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.