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:1508.01327 · Physical Review Letters

Spatial Search by Quantum Walk is Optimal for Almost all Graphs

Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, Yasser Omar

Published Mar 11, 2016• 163 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.116.100501

Related papers

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

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices.

arXiv:2203.14384•ACM Transactions on Quantum Computing•Nov 27, 2024•5 citations

Optimality of spatial search via continuous-time quantum walks

Shantanav Chakraborty, Leonardo Novo, Jérémie Roland

One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.

arXiv:2004.12686•Physical Review A•Sep 14, 2020•37 citations

Vertices cannot be hidden from quantum spatial search for almost all random graphs

Adam Glos, Aleksandra Krawiec, Ryszard Kukulski +1 more

In this paper, we show that all nodes can be found optimally for almost all random Erdős–Rényi $$\mathcal G(n,p)$$ graphs using continuous-time quantum spatial search procedure. This works for both adjacency and Laplacian matrices, though under different conditions. The first one requires $$p=\omega (\log ^8(n)/n)$$ , while the second requires $$p\ge (1+\varepsilon )\log (n)/n$$ , where $$\varepsilon >0$$ . The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the $$\Vert \cdot \Vert _\infty $$ norm. At the same time for $$p<(1-\varepsilon )\log (n)/n$$ , the property does not hold for any matrix, due to the connectivity issues. Hence, our derivation concerning Laplacian matrix is tight.

arXiv:1709.06829•Quantum Information Processing•Feb 22, 2018•17 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

Deterministic spatial search using alternating quantum walks

S. Marsh, Jingbo B. Wang

This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an $N$-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.

arXiv:2104.03806•Physical Review A•Aug 24, 2021•15 citations
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.
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 quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is O(N)O(\sqrt {N})O(N​) with an asymptotic probability of 1+ o (1), where N is the number of vertices.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of nnn nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n)O(\sqrt{n})O(n​) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
In this paper, we show that all nodes can be found optimally for almost all random Erdős–Rényi G(n,p)\mathcal G(n,p)G(n,p) graphs using continuous-time quantum spatial search procedure. This works for both adjacency and Laplacian matrices, though under different conditions. The first one requires p=ω(log⁡8(n)/n)p=\omega (\log ^8(n)/n)p=ω(log8(n)/n) , while the second requires p≥(1+ε)log⁡(n)/np\ge (1+\varepsilon )\log (n)/np≥(1+ε)log(n)/n , where ε>0\varepsilon >0ε>0 . The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the ∥⋅∥∞\Vert \cdot \Vert _\infty ∥⋅∥∞​ norm. At the same time for p<(1−ε)log⁡(n)/np<(1-\varepsilon )\log (n)/np<(1−ε)log(n)/n , the property does not hold for any matrix, due to the connectivity issues. Hence, our derivation concerning Laplacian matrix is tight.
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.
This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an NNN-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.