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

Graph comparison via nonlinear quantum search

Mitchell Chiew, K. de Lacy, Chao‐Hua Yu, S. Marsh, Jingbo B. Wang

Published Aug 20, 2019• 10 citations
arXivHTMLPDF
DOI
10.1007/s11128-019-2407-2

Related papers

Quantum Graphs and Optimization

Sovan Samanta

Studies in computational intelligence•Jan 1, 2025•0 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

Quantum Search: Decoding on a Graph

Sanjeev Naguleswaran, L.B. White

•Jan 1, 2005•0 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

Quantum search of matching on signed graphs

Etsuo Segawa, Yusuke Yoshie

arXiv:2007.07223•Quantum Information Processing•May 1, 2021•6 citations

Quantum search with interacting Bose-Einstein condensates

Mahdi Ebrahimi Kahou, David L. Feder

One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a graph containing a marked site. In many physical implementations, however, one might expect to have multiple particles. In interacting bosonic systems at zero temperature, the dynamics is well described by a discrete nonlinear Schr\"odinger equation. We investigate the role of nonlinearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. The analytical calculations reveal that the nonlinear search time scales with the size of the search space $N$ like $\sqrt{N}$, equivalent to the linear case, though with a different overall constant. The results indicate that interacting Bose-Einstein condensates at zero temperature could be natural systems for implementation of the quantum search algorithm.

arXiv:1303.3537•Physical Review A•Sep 11, 2013•12 citations
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.
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.
One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a graph containing a marked site. In many physical implementations, however, one might expect to have multiple particles. In interacting bosonic systems at zero temperature, the dynamics is well described by a discrete nonlinear Schr\"odinger equation. We investigate the role of nonlinearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. The analytical calculations reveal that the nonlinear search time scales with the size of the search space NNN like N\sqrt{N}N​, equivalent to the linear case, though with a different overall constant. The results indicate that interacting Bose-Einstein condensates at zero temperature could be natural systems for implementation of the quantum search algorithm.