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:1809.01969 · Physical Review A

Quantum spatial search on graphs subject to dynamical noise

Marco Cattaneo, Matteo A. C. Rossi, Matteo G. A. Paris, Sabrina Maniscalco

Published Nov 27, 2018• 27 citations
arXivHTMLPDF

Abstract

We address quantum spatial search on graphs and its implementation by continuous-time quantum walks in the presence of dynamical noise. In particular, we focus on search on the complete graph and on the star graph of order $N$, also proving that noiseless spatial search shows optimal quantum speedup in the latter, in the computational limit $N\ensuremath{\gg}1$. The noise is modeled by independent sources of random telegraph noise (RTN), dynamically perturbing the links of the graph. We observe two different behaviors depending on the switching rate of RTN: fast noise only slightly degrades performance, whereas slow noise is more detrimental and, in general, lowers the success probability. In particular, we still find a quadratic speedup for the average running time of the algorithm, while for the star graph with external target node, we observe a transition to classical scaling. We also address how the effects of noise depend on the order of the graphs and discuss the role of the graph topology. Overall, our results suggest that realizations of quantum spatial search are possible with current technology and indicate the star graph as the perfect candidate for the implementation by noisy quantum walks, owing to its simple topology and nearly optimal performance for just a few nodes also.

DOI
10.1103/physreva.98.052347

Related papers

Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation

Matteo A. C. Rossi, Marco Cattaneo, Matteo G. A. Paris +1 more

Abstract Continuous-time quantum walks may be exploited to enhance spatial search, i.e., for finding a marked element in a database structured as a complex network. However, in practical implementations, the environmental noise has detrimental effects, and a question arises on whether noise engineering may be helpful in mitigating those effects on the performance of the quantum algorithm. Here we study whether time-correlated noise inducing non-Markovianity may represent a resource for quantum search. In particular, we consider quantum search on a star graph, which has been proven to be optimal in the noiseless case, and analyze the effects of independent random telegraph noise (RTN) disturbing each link of the graph. Upon exploiting an exact code for the noisy dynamics, we evaluate the quantum non-Markovianity of the evolution, and show that it cannot be considered as a resource for this algorithm, since its presence is correlated with lower probabilities of success of the search.

arXiv:1811.04780•Quantum Measurements and Quantum Metrology•Dec 1, 2018•6 citations

Continuous-time quantum walks on dynamical percolation graphs

Claudia Benedetti, Matteo A. C. Rossi, Matteo G. A. Paris

We address continuous-time quantum walks on graphs in the presence of time- and space-dependent noise. Noise is modeled as generalized dynamical percolation, i.e. , classical time-dependent fluctuations affecting the tunneling amplitudes of the walker. In order to illustrate the general features of the model, we review recent results on two paradigmatic examples: the dynamics of quantum walks on the line and the effects of noise on the performances of quantum spatial search on the complete and the star graph. We also discuss future perspectives, including extension to many-particle quantum walk, to noise model for on-site energies and to the analysis of different noise spectra. Finally, we address the use of quantum walks as a quantum probe to characterize defects and perturbations occurring in complex, classical and quantum, networks.

arXiv:1812.06676•Europhysics Letters (EPL)•Jan 4, 2019•30 citations

Optimal Quantum Spatial Search on Random Temporal Networks

Shantanav Chakraborty, Leonardo Novo, Serena Di Giorgio +1 more

To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.

arXiv:1701.04392•Physical Review Letters•Nov 28, 2017•49 citations

Spatial Search by Quantum Walk is Optimal for Almost all Graphs

Shantanav Chakraborty, Leonardo Novo, Andris Ambainis +1 more

The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdös-Renyi random graphs, i.e., graphs of n vertices where each edge exists with probability p, search by CTQW is almost surely optimal as long as p≥log^{3/2}(n)/n. Consequently, we show that quantum spatial search is in fact optimal for almost all graphs, meaning that the fraction of graphs of n vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely, to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.

arXiv:1508.01327•Physical Review Letters•Mar 11, 2016•163 citations

Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk

Simon Apers, Shantanav Chakraborty, Leonardo Novo +1 more

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

arXiv:2112.12746•Physical Review Letters•Oct 14, 2022•65 citations

Spatial search by continuous-time quantum walks on renormalized Internet networks

Joonas Malmi, Matteo A. C. Rossi, Guillermo García-Pérez +1 more

We study spatial search with continuous-time quantum walks on real-world complex networks. We use smaller replicas of the Internet network obtained with a recent geometric renormalization method introduced by Garc\'{\i}a-P\'erez et al., Nat. Phys. 14, 583 (2018). This allows us to infer for the first time the behavior of a quantum spatial search algorithm on a real-world complex network. By simulating numerically the dynamics and optimizing the coupling parameter, we study the optimality of the algorithm and its scaling with the size of the network, showing that on average it is considerably better than the classical scaling $\mathcal{O}(N)$, but it does not reach the ideal quadratic speedup $\mathcal{O}(\sqrt{N})$ that can be achieved, e.g. in complete graphs. However, the performance of the search algorithm strongly depends on the degree of the nodes and, in fact, the scaling is found to be very close to optimal when we consider the nodes below the $99\mathrm{th}$ percentile ordered according to the degree.

arXiv:2205.02137•Physical Review Research•Dec 13, 2022•8 citations
We address quantum spatial search on graphs and its implementation by continuous-time quantum walks in the presence of dynamical noise. In particular, we focus on search on the complete graph and on the star graph of order NNN, also proving that noiseless spatial search shows optimal quantum speedup in the latter, in the computational limit N\ensuremath≫1N\ensuremath{\gg}1N\ensuremath≫1. The noise is modeled by independent sources of random telegraph noise (RTN), dynamically perturbing the links of the graph. We observe two different behaviors depending on the switching rate of RTN: fast noise only slightly degrades performance, whereas slow noise is more detrimental and, in general, lowers the success probability. In particular, we still find a quadratic speedup for the average running time of the algorithm, while for the star graph with external target node, we observe a transition to classical scaling. We also address how the effects of noise depend on the order of the graphs and discuss the role of the graph topology. Overall, our results suggest that realizations of quantum spatial search are possible with current technology and indicate the star graph as the perfect candidate for the implementation by noisy quantum walks, owing to its simple topology and nearly optimal performance for just a few nodes also.
Abstract Continuous-time quantum walks may be exploited to enhance spatial search, i.e., for finding a marked element in a database structured as a complex network. However, in practical implementations, the environmental noise has detrimental effects, and a question arises on whether noise engineering may be helpful in mitigating those effects on the performance of the quantum algorithm. Here we study whether time-correlated noise inducing non-Markovianity may represent a resource for quantum search. In particular, we consider quantum search on a star graph, which has been proven to be optimal in the noiseless case, and analyze the effects of independent random telegraph noise (RTN) disturbing each link of the graph. Upon exploiting an exact code for the noisy dynamics, we evaluate the quantum non-Markovianity of the evolution, and show that it cannot be considered as a resource for this algorithm, since its presence is correlated with lower probabilities of success of the search.
We address continuous-time quantum walks on graphs in the presence of time- and space-dependent noise. Noise is modeled as generalized dynamical percolation, i.e. , classical time-dependent fluctuations affecting the tunneling amplitudes of the walker. In order to illustrate the general features of the model, we review recent results on two paradigmatic examples: the dynamics of quantum walks on the line and the effects of noise on the performances of quantum spatial search on the complete and the star graph. We also discuss future perspectives, including extension to many-particle quantum walk, to noise model for on-site energies and to the analysis of different noise spectra. Finally, we address the use of quantum walks as a quantum probe to characterize defects and perturbations occurring in complex, classical and quantum, networks.
To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.
The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdös-Renyi random graphs, i.e., graphs of n vertices where each edge exists with probability p, search by CTQW is almost surely optimal as long as p≥log^{3/2}(n)/n. Consequently, we show that quantum spatial search is in fact optimal for almost all graphs, meaning that the fraction of graphs of n vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely, to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.
We study spatial search with continuous-time quantum walks on real-world complex networks. We use smaller replicas of the Internet network obtained with a recent geometric renormalization method introduced by Garc\'{\i}a-P\'erez et al., Nat. Phys. 14, 583 (2018). This allows us to infer for the first time the behavior of a quantum spatial search algorithm on a real-world complex network. By simulating numerically the dynamics and optimizing the coupling parameter, we study the optimality of the algorithm and its scaling with the size of the network, showing that on average it is considerably better than the classical scaling O(N)\mathcal{O}(N)O(N), but it does not reach the ideal quadratic speedup O(N)\mathcal{O}(\sqrt{N})O(N​) that can be achieved, e.g. in complete graphs. However, the performance of the search algorithm strongly depends on the degree of the nodes and, in fact, the scaling is found to be very close to optimal when we consider the nodes below the 99th99\mathrm{th}99th percentile ordered according to the degree.