Quantum Information & Computation
Volume 25, Issue 4
RESEARCH ARTICLE Open access

Conserved Quantities in Linear and Nonlinear Quantum Search

David A. Meyer, Thomas G. Wong

Author affiliations
  • David A. Meyer1
  • Thomas G. Wong2
  1. Department of Mathematics, University of California, San Diego, 9500 Gilman Drive, La Jolla, CA, USA
  2. Department of Physics, Creighton University, 2500 California Plaza, Omaha, NE, USA

pp. 315-328 · 10.2478/qic-2025-0017

Read PDF View on Reference Global
On this page

Abstract

In this tutorial, which contains some original results, we bridge the fields of quantum computing algorithms, conservation laws, and many-body quantum systems by examining three algorithms for searching an unordered database of size N using a continuous-time quantum walk, which is the quantum analogue of a continuous-time random walk. The first algorithm uses a linear quantum walk, and we apply elementary calculus to show that the success probability of the algorithm reaches 1 when the jumping rate of the walk takes some critical value. We show that the expected value of its Hamiltonian H0 is conserved. The second algorithm uses a nonlinear quantum walk with effective Hamiltonian H(t) = H0 + λ | ψ |2, which arises in the Gross-Pitaevskii equation describing Bose-Einstein condensates. When the interactions between the bosons are repulsive, λ > 0, and there exists a range of fixed jumping rates such that the success probability reaches 1 with the same asymptotic runtime of the linear algorithm, but with a larger multiplicative constant. Rather than the effective Hamiltonian, we show that the expected value of H0+12λ∣ψ∣2{H_0} + {1 \over 2}\lambda |\psi {|^2} is conserved. The third algorithm utilizes attractive interactions, corresponding to λ < 0. In this case, there is a time-varying critical function for the jumping rate γc (t) that causes the success probability to reach 1 more quickly than in the other two algorithms, and we show that the expected value of H(t)/[ γc (t) N ] is conserved.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum walk
  • spatial search
  • complete graph
  • conservation laws
  • Gross-Pitaevskii equation
  • Bose-Einstein condensate

Suggested citation

David A. Meyer, Thomas G. Wong (2025). Conserved Quantities in Linear and Nonlinear Quantum Search. Quantum Information & Computation, 25(4), 315-328. https://doi.org/10.2478/qic-2025-0017

Download BibTeX

References (26)

  1. D.J. Griffiths and D.F. Schroeter (2018). Introduction to Quantum Mechanics, Cambridge University Press, 3rd edition.DOI: 10.1017/9781316995433Google Scholar
  2. A.M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D.A. Spielman (2003). Exponential Algorithmic Speedup by a Quantum Walk, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC ’03, 59–68. ACM, New York.DOI: 10.1145/780542.780552Google Scholar
  3. A.M. Childs and J. Goldstone (2004). “Spatial search by quantum walk”. Physical Review A, 70, 022314.DOI: 10.1103/PhysRevA.70.022314Google Scholar
  4. E. Farhi, J. Goldstone and S. Gutmann (2008). “A quantum algorithm for the Hamiltonian NAND tree”. Theory of Computing, 4, 169–190.DOI: 10.4086/toc.2008.v004a008Google Scholar
  5. J. Kempe (2003). “Quantum random walks: An introductory overview”. Contemporary Physics, 44, 307–327.DOI: 10.1080/00107151031000110776Google Scholar
  6. A. Ambainis (2003). “Quantum walks and their algorithmic applications”. International Journal of Quantum Information, 01, 507–518.DOI: 10.1142/S0219749903000383Google Scholar
  7. S.E. Venegas-Andraca (2012). “Quantum walks: A comprehensive review”. Quantum Information Processing, 1015–1106.DOI: 10.1007/s11128-012-0432-5Google Scholar
  8. G.D. Molfetta (2024). Quantum Walks, Limits, and Transport Equations, Bristol: Institute of Physics Publishing.DOI: 10.1088/978-0-7503-5744-9Google Scholar
  9. T.G. Wong (2022). “Unstructured search by random and quantum walk”. Quantum Information & Computing, 22, 53–85.DOI: 10.26421/QIC22.1-2-4Google Scholar
  10. L.K. Grover (1996). A Fast Quantum Mechanical Algorithm for Database Search, in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC ’96, 212–219. ACM, New York.DOI: 10.1145/237814.237866Google Scholar
  11. S.N. Bose (1924). “Plancks gesetz und lichtquantenhypothese”. Zeitschrift für Physik, 26.DOI: 10.1007/BF01327326Google Scholar
  12. A. Einstein (1924). Zur quantentheorie des einatomigen idealen gases, Wiss: Sitzungsber. K. Preuss. Akad., 261.Google Scholar
  13. A. Einstein (1925). Quantentheorie des einatomigen idealen gases. Zweite abhandlung, Wiss: Sitzungsber. Preuss. Akad., 3.Google Scholar
  14. E. Gross (1961). “Structure of a quantized vortex in boson systems”. Il Nuovo Cimento (1955–1965), 20, 454–477.DOI: 10.1007/BF02731494Google Scholar
  15. L. Pitaevskii (1961). “Vortex lines in an imperfect Bose gas”. Soviet Physics JETP-USSR, 13, 451–454.Google Scholar
  16. F. Dalfovo, S. Giorgini, L.P. Pitaevskii and S. Stringari (1999). “Theory of Bose-Einstein condensation in trapped gases”. Reviews of Modern Physics, 71, 463-512.DOI: 10.1103/RevModPhys.71.463Google Scholar
  17. O. Morsch and M. Oberthaler (2006). “Dynamics of Bose-Einstein condensates in optical lattices”. Reviews of Modern Physics, 78, 179-215.DOI: 10.1103/RevModPhys.78.179Google Scholar
  18. J. Rogel-Salazar (2013). “The Gross-Pitaevskii equation and Bose–Einstein condensates”. European Journal of Physics, 34, 247.DOI: 10.1088/0143-0807/34/2/247Google Scholar
  19. M. Ebrahimi Kahou and D.L. Feder (2013). “Quantum search with interacting Bose-Einstein condensates”. Physical Review A, 88, 032310.DOI: 10.1103/PhysRevA.88.032310Google Scholar
  20. D.A. Meyer and T.G. Wong (2013). “Nonlinear quantum search using the Gross-Pitaevskii equation”. New Journal of Physics, 15, 063014.DOI: 10.1088/1367-2630/15/6/063014Google Scholar
  21. J. Janmark, D.A. Meyer and T.G. Wong (2014). “Global symmetry is unnecessary for fast quantum search”. Physical Review Letters, 112, 210502.DOI: 10.1103/PhysRevLett.112.210502Google Scholar
  22. J.L. Roberts, N.R. Claussen, S.L. Cornish, E.A. Donley, E.A. Cornell and C.E. Wieman (2001). “Controlled collapse of a Bose-Einstein condensate”. Physical Review Letters, 86, 4211–4214.DOI: 10.1103/PhysRevLett.86.4211Google Scholar
  23. T. Chen, N. Pavlovic and N. Tzirakis (2010). “Energy conservation and blowup of solutions for focusing Gross–Pitaevskii hierarchies”. Annales de l’Institut Henri Poincare (C) Analyse Non Lineaire, 27, 1271–1290.DOI: 10.1016/j.anihpc.2010.06.003Google Scholar
  24. D. Mendelson, A.R. Nahmod, N. Pavlovic and G. Staffilani (2019). “An infinite sequence of conserved quantities for the cubic Gross-Pitaevskii hierarchy on R”. Transactions of American Mathematical Society, 371, 5179–5202.DOI: 10.1090/tran/7726Google Scholar
  25. H. Koch and X. Liao (2021). “Conserved energies for the one dimensional Gross-Pitaevskii equation”. Advances in Mathematics, 377, 107467.DOI: 10.1016/j.aim.2020.107467Google Scholar
  26. H. Koch and X. Liao (2023). “Conserved energies for the one dimensional Gross-Pitaevskii equation: Low regularity case”. Advances in Mathematics, 420, 108996.DOI: 10.1016/j.aim.2023.108996Google Scholar