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

Global Symmetry is Unnecessary for Fast Quantum Search

Jonatan Janmark, DAVID A. MEYER, Thomas G. Wong

Published May 28, 2014• 87 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.112.210502

Related papers

Completeness is Unnecessary for Fast Nonlinear Quantum Search

DAVID A. 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

Quantum Search on Strongly Regular Graphs

Jonatan Janmark

In 1996, Farhi & Gutmann presented a continuous time analogue of Grover’s algorithm which was later interpreted as search by a quantum random walk on the complete graph. Similar work has since then been done on hypercubes and periodic lattices. We investigate the same search algorithm but for a new type of graphs called strongly regular graphs. The problem is solved by a, in this context, new technique involving degenerate perturbation theory. The result is that the search is optimal on all strongly regular graphs when the number of vertices N is large. However, different kinds of strongly regular graphs perform different when N is not large. Analyzing this provides some insight into what properties of graphs that are important for quantum search. Apart from the results, an important takeaway is the degenerate perturbation theory technique that was used to solve the problem and might be useful in solving other similar problems. In the thesis, an alternative solution to the complete graph case is given using this method. Also, the fact that strongly regular graphs proved to be convenient to analyze in these kinds of settings suggests that they can be used in other similar problems.

•Jan 1, 2013•1 citation

Connectivity is a Poor Indicator of Fast Quantum Search

DAVID A. MEYER, Thomas G. Wong

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.

arXiv:1409.5876•Physical Review Letters•Mar 18, 2015•84 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•0 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•22 citations

Quantum walk search with time-reversal symmetry breaking

Thomas G. Wong

We formulate Grover's unstructured search algorithm as a chiral quantum walk, where transitioning in one direction has a phase conjugate to transitioning in the opposite direction. For small phases, this breaking of time-reversal symmetry is too small to significantly affect the evolution: the system still approximately evolves in its ground and first excited states, rotating to the marked vertex in time $π\sqrt{N} / 2$. Increasing the phase does not change the runtime, but rather changes the support for the 2D subspace, so the system evolves in its first and second excited states, or its second and third excited states, and so forth. Apart from the critical phases corresponding to these transitions in the support, which become more frequent as the phase grows, this reveals that our model of quantum search is robust against time-reversal symmetry breaking.

arXiv:1504.07375•Journal of Physics A Mathematical and Theoretical•Sep 14, 2015•17 citations
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 \ensuremathΘ(N)\mathrm{\ensuremath{\Theta}}(\sqrt{N})\ensuremathΘ(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.
In 1996, Farhi & Gutmann presented a continuous time analogue of Grover’s algorithm which was later interpreted as search by a quantum random walk on the complete graph. Similar work has since then been done on hypercubes and periodic lattices. We investigate the same search algorithm but for a new type of graphs called strongly regular graphs. The problem is solved by a, in this context, new technique involving degenerate perturbation theory. The result is that the search is optimal on all strongly regular graphs when the number of vertices N is large. However, different kinds of strongly regular graphs perform different when N is not large. Analyzing this provides some insight into what properties of graphs that are important for quantum search. Apart from the results, an important takeaway is the degenerate perturbation theory technique that was used to solve the problem and might be useful in solving other similar problems. In the thesis, an alternative solution to the complete graph case is given using this method. Also, the fact that strongly regular graphs proved to be convenient to analyze in these kinds of settings suggests that they can be used in other similar problems.
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.
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.
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.
We formulate Grover's unstructured search algorithm as a chiral quantum walk, where transitioning in one direction has a phase conjugate to transitioning in the opposite direction. For small phases, this breaking of time-reversal symmetry is too small to significantly affect the evolution: the system still approximately evolves in its ground and first excited states, rotating to the marked vertex in time πN/2π\sqrt{N} / 2πN​/2. Increasing the phase does not change the runtime, but rather changes the support for the 2D subspace, so the system evolves in its first and second excited states, or its second and third excited states, and so forth. Apart from the critical phases corresponding to these transitions in the support, which become more frequent as the phase grows, this reveals that our model of quantum search is robust against time-reversal symmetry breaking.