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

Connectivity is a Poor Indicator of Fast Quantum Search

David Meyer, Thomas G. Wong

Published Mar 18, 2015• 88 citations
arXivHTMLPDF

Abstract

A randomly walking quantum particle evolving by Schrödinger's equation searches on d-dimensional cubic lattices in O(√N) time when d≥5, and with progressively slower runtime as d decreases. This suggests that graph connectivity (including vertex, edge, algebraic, and normalized algebraic connectivities) is an indicator of fast quantum search, a belief supported by fast quantum search on complete graphs, strongly regular graphs, and hypercubes, all of which are highly connected. In this Letter, we show this intuition to be false by giving two examples of graphs for which the opposite holds true: one with low connectivity but fast search, and one with high connectivity but slow search. The second example is a novel two-stage quantum walk algorithm in which the walking rate must be adjusted to yield high search probability.

DOI
10.1103/physrevlett.114.110503

Related papers

Global Symmetry is Unnecessary for Fast Quantum Search

Jonatan Janmark, David Meyer, Thomas G. Wong

Grover's quantum search algorithm can be formulated as a quantum particle randomly walking on the (highly symmetric) complete graph, with one vertex marked by a nonzero potential. From an initial equal superposition, the state evolves in a two-dimensional subspace. Strongly regular graphs have a local symmetry that ensures that the state evolves in a three-dimensional subspace but most have no global symmetry. Using degenerate perturbation theory, we show that quantum random walk search on known families of strongly regular graphs, nevertheless, achieves the full quantum speed-up of $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$, disproving the intuition that fast quantum search requires global symmetry.

arXiv:1403.2228•Physical Review Letters•May 28, 2014•89 citations

Completeness is Unnecessary for Fast Nonlinear Quantum Search

David Meyer, Thomas G. Wong

Although strongly regular graphs and the hypercube are not complete, they are "sufficiently complete" such that a randomly walking quantum particle asymptotically searches on them in the same $Θ(\sqrt{N})$ time as on the complete graph, the latter of which is precisely Grover's algorithm. We show that physically realistic nonlinearities of the form $f(|ψ|^2)ψ$ can speed up search on sufficiently complete graphs, depending on the nonlinearity and graph. Thus nonlinear (quantum) computation can retain its power even when a degree of noncompleteness is introduced.

arXiv:1502.06281•Feb 22, 2015•2 citations

Faster quantum walk search on a weighted graph

Thomas G. Wong

A randomly walking quantum particle evolving by Schr\"odinger's equation searches for a unique marked vertex on the ``simplex of complete graphs'' in time $\mathrm{\ensuremath{\Theta}}({N}^{3/4})$. We give a weighted version of this graph that preserves vertex transitivity, and we show that the time to search on it can be reduced to nearly $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$. To prove this, we introduce two extensions to degenerate perturbation theory: an adjustment that distinguishes the weights of the edges and a method to determine how precisely the jumping rate of the quantum walk must be chosen.

arXiv:1507.07590•Physical Review A•Sep 21, 2015•23 citations

Optimal spatial searches with long-range tunneling

Emma C. King, Moritz Linnebacher, Peter P. Orth +2 more

A quantum walk on a lattice is a paradigm of a quantum search in a database. The database qubit strings are the lattice sites, qubit rotations are tunneling events, and the target site is tagged by an energy shift. For quantum walks on a continuous time, the walker diffuses across the lattice and the search ends when it localizes at the target site. The search time T can exhibit Grover's optimal scaling with the lattice size N , namely, T ∼ N , on an all-connected, complete lattice. For finite-range tunneling between sites, instead, Grover's optimal scaling is warranted when the lattice is a hypercube of d > 4 dimensions. Here, we show that Grover's optimum can be reached in lower dimensions on lattices of long-range interacting particles, when the interaction strength scales algebraically with the distance r as 1 / r α and 0 < α < 3 d / 2 . For α < d the dynamics mimics the one of a globally connected graph. For d < α < d + 2 , the quantum search on the graph can be mapped to a short-range model on a hypercube with spatial dimension d s = 2 d / ( α − d ) , indicating that the search is optimal for d s > 4 . Our work identifies an exact relation between criticality of long-range and short-range systems, it provides a quantitative demonstration of the resources that long-range interactions provide for quantum technologies, and indicates when existing experimental platforms can implement efficient analog quantum search algorithms.

arXiv:2501.08148•Physical Review Research•Jul 8, 2025•6 citations

Spatial Search by Nonlinear Quantum Walk

David A. Meyer, Thomas G. Wong

Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size $Θ(N)$, for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.

quant-pharXiv:2606.01403•Jun 2, 2026•1 citation

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•169 citations
A randomly walking quantum particle evolving by Schrödinger's equation searches on d-dimensional cubic lattices in O(√N) time when d≥5, and with progressively slower runtime as d decreases. This suggests that graph connectivity (including vertex, edge, algebraic, and normalized algebraic connectivities) is an indicator of fast quantum search, a belief supported by fast quantum search on complete graphs, strongly regular graphs, and hypercubes, all of which are highly connected. In this Letter, we show this intuition to be false by giving two examples of graphs for which the opposite holds true: one with low connectivity but fast search, and one with high connectivity but slow search. The second example is a novel two-stage quantum walk algorithm in which the walking rate must be adjusted to yield high search probability.
Grover's quantum search algorithm can be formulated as a quantum particle randomly walking on the (highly symmetric) complete graph, with one vertex marked by a nonzero potential. From an initial equal superposition, the state evolves in a two-dimensional subspace. Strongly regular graphs have a local symmetry that ensures that the state evolves in a three-dimensional subspace but most have no global symmetry. Using degenerate perturbation theory, we show that quantum random walk search on known families of strongly regular graphs, nevertheless, achieves the full quantum speed-up of $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$, disproving the intuition that fast quantum search requires global symmetry.
Although strongly regular graphs and the hypercube are not complete, they are "sufficiently complete" such that a randomly walking quantum particle asymptotically searches on them in the same Θ(N)Θ(\sqrt{N})Θ(N​) time as on the complete graph, the latter of which is precisely Grover's algorithm. We show that physically realistic nonlinearities of the form f(∣ψ∣2)ψf(|ψ|^2)ψf(∣ψ∣2)ψ can speed up search on sufficiently complete graphs, depending on the nonlinearity and graph. Thus nonlinear (quantum) computation can retain its power even when a degree of noncompleteness is introduced.
A randomly walking quantum particle evolving by Schr\"odinger's equation searches for a unique marked vertex on the ``simplex of complete graphs'' in time $\mathrm{\ensuremath{\Theta}}({N}^{3/4})$. We give a weighted version of this graph that preserves vertex transitivity, and we show that the time to search on it can be reduced to nearly $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$. To prove this, we introduce two extensions to degenerate perturbation theory: an adjustment that distinguishes the weights of the edges and a method to determine how precisely the jumping rate of the quantum walk must be chosen.
A quantum walk on a lattice is a paradigm of a quantum search in a database. The database qubit strings are the lattice sites, qubit rotations are tunneling events, and the target site is tagged by an energy shift. For quantum walks on a continuous time, the walker diffuses across the lattice and the search ends when it localizes at the target site. The search time T can exhibit Grover's optimal scaling with the lattice size N , namely, T ∼ N , on an all-connected, complete lattice. For finite-range tunneling between sites, instead, Grover's optimal scaling is warranted when the lattice is a hypercube of d > 4 dimensions. Here, we show that Grover's optimum can be reached in lower dimensions on lattices of long-range interacting particles, when the interaction strength scales algebraically with the distance r as 1 / r α and 0 < α < 3 d / 2 . For α < d the dynamics mimics the one of a globally connected graph. For d < α < d + 2 , the quantum search on the graph can be mapped to a short-range model on a hypercube with spatial dimension d s = 2 d / ( α − d ) , indicating that the search is optimal for d s > 4 . Our work identifies an exact relation between criticality of long-range and short-range systems, it provides a quantitative demonstration of the resources that long-range interactions provide for quantum technologies, and indicates when existing experimental platforms can implement efficient analog quantum search algorithms.
Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size Θ(N)Θ(N)Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.
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.