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

Completeness is Unnecessary for Fast Nonlinear Quantum Search

DAVID A. MEYER, Thomas G. Wong

Published Feb 22, 2015• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1502.06281

Related papers

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

Global Symmetry is Unnecessary for Fast Quantum Search

Jonatan Janmark, DAVID A. 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•87 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

Constant-time quantum search with a many-body quantum system

Benjamin DalFavero, Alexander Meill, DAVID A. MEYER +2 more

The optimal runtime of a quantum computer searching a database is typically cited as the square root of the number of items in the database, which is famously achieved by Grover's algorithm. With parallel oracles, however, it is possible to search faster than this. We consider a many-body quantum system that naturally effects parallel queries, and we show that its parameters can be tuned to search a database in constant time, assuming a sufficient number of interacting particles. In particular, we consider Bose-Einstein condensates with pairwise and three-body interactions in the mean-field limit, which effectively evolve by a nonlinear Schr\"odinger equation with cubic and quintic nonlinearities. We solve the unstructured search problem formulated as a continuous-time quantum walk searching the complete graph in constant time. Depending on the number of marked vertices, however, the success probability can peak sharply, necessitating high precision time measurement to observe the system at this peak. Overcoming this, we prove that the relative coefficients of the cubic and quintic terms can be tuned to eliminate the need for high time-measurement precision by widening the peak in success probability or having it plateau. Finally, we derive a lower bound on the number of atoms needed for the many-body system to evolve by the effective nonlinearity.

arXiv:2408.05376•Physical Review A•Nov 7, 2024•2 citations

Time complexity of a monitored quantum search with resetting

Emma C. King, Sayan Roy, Francesco Mattiotti +3 more

Searching a database is a central task in computer science and is paradigmatic of transport and optimization problems in physics. For an unstructured search, Grover's algorithm predicts a quadratic speedup, with the search time $τ(N)=Θ(\sqrt{N})$ and $N$ the database size. Numerical studies suggest that the time complexity can change in the presence of feedback, injecting information during the search. Here, we determine the time complexity of the quantum analog of a randomized algorithm, which implements feedback in a simple form. The search is a continuous-time quantum walk on a complete graph, where the target is continuously monitored by a detector. Additionally, the quantum state is reset if the detector does not click within a specified time interval. This yields a non-unitary, non-Markovian dynamics. We optimize the search time as a function of the hopping amplitude, detection rate, and resetting rate, and identify the conditions under which time complexity could outperform Grover's scaling. The overall search time does not violate Grover's optimality bound when including the time budget of the physical implementation of the measurement. For databases of finite sizes monitoring can warrant rapid convergence and provides a promising avenue for fault-tolerant quantum searches.

quant-pharXiv:2601.20560•Jan 29, 2026•0 citations
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.
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.
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.
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.
The optimal runtime of a quantum computer searching a database is typically cited as the square root of the number of items in the database, which is famously achieved by Grover's algorithm. With parallel oracles, however, it is possible to search faster than this. We consider a many-body quantum system that naturally effects parallel queries, and we show that its parameters can be tuned to search a database in constant time, assuming a sufficient number of interacting particles. In particular, we consider Bose-Einstein condensates with pairwise and three-body interactions in the mean-field limit, which effectively evolve by a nonlinear Schr\"odinger equation with cubic and quintic nonlinearities. We solve the unstructured search problem formulated as a continuous-time quantum walk searching the complete graph in constant time. Depending on the number of marked vertices, however, the success probability can peak sharply, necessitating high precision time measurement to observe the system at this peak. Overcoming this, we prove that the relative coefficients of the cubic and quintic terms can be tuned to eliminate the need for high time-measurement precision by widening the peak in success probability or having it plateau. Finally, we derive a lower bound on the number of atoms needed for the many-body system to evolve by the effective nonlinearity.
Searching a database is a central task in computer science and is paradigmatic of transport and optimization problems in physics. For an unstructured search, Grover's algorithm predicts a quadratic speedup, with the search time τ(N)=Θ(N)τ(N)=Θ(\sqrt{N})τ(N)=Θ(N​) and NNN the database size. Numerical studies suggest that the time complexity can change in the presence of feedback, injecting information during the search. Here, we determine the time complexity of the quantum analog of a randomized algorithm, which implements feedback in a simple form. The search is a continuous-time quantum walk on a complete graph, where the target is continuously monitored by a detector. Additionally, the quantum state is reset if the detector does not click within a specified time interval. This yields a non-unitary, non-Markovian dynamics. We optimize the search time as a function of the hopping amplitude, detection rate, and resetting rate, and identify the conditions under which time complexity could outperform Grover's scaling. The overall search time does not violate Grover's optimality bound when including the time budget of the physical implementation of the measurement. For databases of finite sizes monitoring can warrant rapid convergence and provides a promising avenue for fault-tolerant quantum searches.