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:1709.06829 · Quantum Information Processing

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

Adam Glos, Aleksandra Krawiec, Ryszard Kukulski, Zbigniew Puchała

Published Feb 22, 2018• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s11128-018-1844-7

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

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

Ryszard Kukulski, Adam Glos

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.

arXiv:2009.13309•Sep 28, 2020•1 citation

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

Of shadows and gaps in spatial search

Ada Chan, Chris D. Godsil, Christino Tamon +1 more

Spatial search occurs in a connected graph if a continuous-time quantum walk on the adjacency matrix of the graph, suitably scaled, plus a rank-one perturbation induced by any vertex will unitarily map the principal eigenvector of the graph to the characteristic vector of the vertex. This phenomenon is a natural continuous-time analogue of Grover search. The spatial search is said to be optimal if it occurs with constant fidelity and in time inversely proportional to the shadow of the target vertex on the principal eigenvector. Extending a result of Chakraborty \etal ({\em Physical Review A}, {\bf 102}:032214, 2020), we prove a simpler characterization of optimal spatial search. Based on this characterization, we observe that some families of distance-regular graphs, such as Hamming and Grassmann graphs, have optimal spatial search. We also show a matching lower bound on time for spatial search with constant fidelity, which extends a bound due to Farhi and Gutmann for perfect fidelity. Our elementary proofs employ standard tools, such as Weyl inequalities and Cauchy determinant formula.

arXiv:2204.04355•Quantum Information and Computation•Sep 1, 2022•4 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

Spatial search for a general multi-vertex state on graph by continuous-time quantum walks

Xi Li, Hanwu Chen, Yue Ruan +3 more

In this work, we consider the spatial search for a general marked state on graphs by continuous time quantum walks. As a simplest case, we compute the amplitude expression of the search for the multi-vertex uniform superposition state on hypercube, and find that the spatial search algorithm is optimal for the two-vertex uniform state. However, on general graphs, a common formula can't be obtained for searching a general non-uniform superposition state. Fortunately, a Laplacian spectrum condition which determines whether the associated graph could be appropriate for performing the optimal spatial search is presented. The condition implies that if the proportion of the maximum and the non-zero minimum Laplacian eigenvalues is less or equal to 1+sqrt(1/2), then the spatial search is optimal for any general state. At last, we apply this condition to three kind graphs, the induced complete graph, the strongly regular graph and the regular complete multi-partite graphs. By the condition, one can conclude that these graphs will become suitable for optimal search with properly setting their graph parameters.

arXiv:1804.03042•Apr 9, 2018•0 citations
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.
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.
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.
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.
Spatial search occurs in a connected graph if a continuous-time quantum walk on the adjacency matrix of the graph, suitably scaled, plus a rank-one perturbation induced by any vertex will unitarily map the principal eigenvector of the graph to the characteristic vector of the vertex. This phenomenon is a natural continuous-time analogue of Grover search. The spatial search is said to be optimal if it occurs with constant fidelity and in time inversely proportional to the shadow of the target vertex on the principal eigenvector. Extending a result of Chakraborty \etal ({\em Physical Review A}, {\bf 102}:032214, 2020), we prove a simpler characterization of optimal spatial search. Based on this characterization, we observe that some families of distance-regular graphs, such as Hamming and Grassmann graphs, have optimal spatial search. We also show a matching lower bound on time for spatial search with constant fidelity, which extends a bound due to Farhi and Gutmann for perfect fidelity. Our elementary proofs employ standard tools, such as Weyl inequalities and Cauchy determinant formula.
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.
In this work, we consider the spatial search for a general marked state on graphs by continuous time quantum walks. As a simplest case, we compute the amplitude expression of the search for the multi-vertex uniform superposition state on hypercube, and find that the spatial search algorithm is optimal for the two-vertex uniform state. However, on general graphs, a common formula can't be obtained for searching a general non-uniform superposition state. Fortunately, a Laplacian spectrum condition which determines whether the associated graph could be appropriate for performing the optimal spatial search is presented. The condition implies that if the proportion of the maximum and the non-zero minimum Laplacian eigenvalues is less or equal to 1+sqrt(1/2), then the spatial search is optimal for any general state. At last, we apply this condition to three kind graphs, the induced complete graph, the strongly regular graph and the regular complete multi-partite graphs. By the condition, one can conclude that these graphs will become suitable for optimal search with properly setting their graph parameters.