2015/02/22 by David Meyer, David A. Meyer, Thomas G. Wong +2 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1502.06281
6 pages, 6 figures
arxiv created 2015/02/22 · openalex publication_date 2015/02/22 · arxiv updated 2015/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)) 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.