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:2009.13309

Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs

Ryszard Kukulski, Adam Glos

Published Sep 28, 2020• 1 citation
arXivHTMLPDF

Abstract

This comment is to correct the proof of optimality of quantum spatial search for Erdős-Rényi graphs presented in `Spatial Search by Quantum Walk is Optimal for Almost all Graphs' (https://doi.org/10.1103/PhysRevLett.116.100501). The authors claim that if $p\geq \frac{\log^{3/2}(n)}{n}$, then the CTQW-based search is optimal for almost all graphs. Below we point the issues found in the main paper, and propose corrections, which in fact improve the result to $p=ω(\log(n)/n)$ in case of transition rate $γ= 1/λ_1$. In the case of the proof for simplified transition rate $1/(np)$ we pointed a possible issue with applying perturbation theory.

DOI
10.48550/arxiv.2009.13309

Related papers

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

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

The optimal search on graph by continuous-time quantum walks

Xi Li, Hanwu Chen, Ruan, Yue +3 more

Chakraborty and Leonardo have shown that a spatial search by quantum walk is optimal for almost all graphs. However, we observed that on some graphs, certain states cannot be searched optimally. We present a method for constructing an optimal graph that searches an arbitrary state and provides the optimal condition. We also analyze the monotonicity of the search performance and conclude that the search performance can be improved by adding edges.

arXiv:1711.01765•Nov 6, 2017•0 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

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

Quantum walk search on Kronecker graphs

Thomas G. Wong, Konstantin Wünscher, Joshua Lockhart +1 more

Kronecker graphs, obtained by repeatedly performing the Kronecker product of the adjacency matrix of an ``initiator'' graph with itself, have risen in popularity in network science due to their ability to generate complex networks with real-world properties. We explore spatial search by continuous-time quantum walk on Kronecker graphs. Specifically, we give analytical proofs for quantum search on first-, second-, and third-order Kronecker graphs with the complete graph as the initiator, showing that search takes Grover's $O(\sqrt{N})$ time. Numerical simulations indicate that higher-order Kronecker graphs with the complete initiator also support optimal quantum search.

arXiv:1804.10560•Physical Review A•Jul 31, 2018•14 citations
This comment is to correct the proof of optimality of quantum spatial search for Erdős-Rényi graphs presented in `Spatial Search by Quantum Walk is Optimal for Almost all Graphs' (https://doi.org/10.1103/PhysRevLett.116.100501). The authors claim that if p≥log⁡3/2(n)np\geq \frac{\log^{3/2}(n)}{n}p≥nlog3/2(n)​, then the CTQW-based search is optimal for almost all graphs. Below we point the issues found in the main paper, and propose corrections, which in fact improve the result to p=ω(log⁡(n)/n)p=ω(\log(n)/n)p=ω(log(n)/n) in case of transition rate γ=1/λ1γ= 1/λ_1γ=1/λ1​. In the case of the proof for simplified transition rate 1/(np)1/(np)1/(np) we pointed a possible issue with applying perturbation theory.
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.
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.
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.
Kronecker graphs, obtained by repeatedly performing the Kronecker product of the adjacency matrix of an ``initiator'' graph with itself, have risen in popularity in network science due to their ability to generate complex networks with real-world properties. We explore spatial search by continuous-time quantum walk on Kronecker graphs. Specifically, we give analytical proofs for quantum search on first-, second-, and third-order Kronecker graphs with the complete graph as the initiator, showing that search takes Grover's O(N)O(\sqrt{N})O(N​) time. Numerical simulations indicate that higher-order Kronecker graphs with the complete initiator also support optimal quantum search.