Top

Quantum Information Processing

Published in:

01-10-2016

Laplacian versus adjacency matrix in quantum walk search

Authors: Thomas G. Wong, Luís Tarrataca, Nikolay Nahimov

Published in: Quantum Information Processing | Issue 10/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A quantum particle evolving by Schrödinger’s equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace’s operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.

previous article Obtaining a linear combination of the principal components of a matrix on quantum computers

next article Quantum computation for large-scale image classification

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Schrödinger, E.: An undulatory theory of the mechanics of atoms and molecules. Phys. Rev. 28, 1049–1070 (1926)ADSCrossRefMATH

Griffiths, D.J.: Introduction to Quantum Mechanics. Prentice Hall, New Jersey (2005)

Bloch, I.: Ultracold quantum gases in optical lattices. Nat. Phys. 1, 23–30 (2005)CrossRef

Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915–928 (1998)ADSMathSciNetCrossRef

Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004)ADSMathSciNetCrossRef

Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by a quantum walk. Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing. STOC ’03, pp. 59–68. ACM, New York, NY, USA (2003)

Farhi, E., Goldstone, J., Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree. Theory Comput. 4(8), 169–190 (2008)MathSciNetCrossRefMATH

Bose, S., Casaccino, A., Mancini, S., Severini, S.: Communication in XYZ all-to-all quantum networks with a missing link. Int. J. Quantum Inf. 07(04), 713–723 (2009)CrossRefMATH

Alvir, R., Dever, S., Lovitz, B., Myer, J., Tamon, C., Xu, Y., Zhan, H.: Perfect state transfer in Laplacian quantum walk. J. Algebraic Combin. 43, 801–826 (2016)

10.

Ackelsberg, E., Brehm, Z., Chan, A., Mundinger, J., Tamon, C.: Laplacian state transfer in coronas. Linear Algebra Appl. 506, 154–167 (2016)

11.

Wong, T.G.: Grover search with lackadaisical quantum walks. J. Phys. A: Math. Theor. 48(43), 435304 (2015)ADSMathSciNetCrossRefMATH

12.

Janmark, J., Meyer, D.A., Wong, T.G.: Global symmetry is unnecessary for fast quantum search. Phys. Rev. Lett. 112, 210502 (2014)ADSCrossRef

13.

Meyer, D.A., Wong, T.G.: Connectivity is a poor indicator of fast quantum search. Phys. Rev. Lett. 114, 110503 (2015)ADSCrossRef

14.

Wong, T.G.: Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Inf. Process. 15(4), 1411–1443 (2016)

15.

Wong, T.G., Ambainis, A.: Quantum search with multiple walk steps per oracle query. Phys. Rev. A 92, 022338 (2015)ADSCrossRef

16.

Wong, T.G.: Faster quantum walk search on a weighted graph. Phys. Rev. A 92, 032320 (2016) arXiv:1508.01327v3

17.

Novo, L., Chakraborty, S., Mohseni, M., Neven, H., Omar, Y.: Systematic dimensionality reduction for quantum walks: optimal spatial search and transport on non-regular graphs. Sci. Rep. 5, 13304 (2015)ADSCrossRef

18.

Chakraborty, S., Novo, L., Ambainis, A., Omar, Y.: Spatial search by quantum walk is optimal for almost all graphs. Phys. Rev. Lett. 116, 100501 (2016)

19.

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortsch. Phys. 46(4–5), 493–505 (1998)ADSCrossRef

20.

Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, New York (1995)CrossRefMATH

21.

von Schelling, H.: Auf der spur des zufalls. Deutsches Statistisches Zentralblatt 26, 137–146 (1934)MATH

22.

von Schelling, H.: Coupon collecting for unequal probabilities. Amer. Math. Mon. 61(5), 306–311 (1954)MathSciNetCrossRefMATH

23.

Flajolet, P., Gardy, D., Thimonier, L.: Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Appl. Math. 39, 207–229 (1992)MathSciNetCrossRefMATH

24.

Wong, T.G.: Diagrammatic approach to quantum search. Quantum Inf. Process. 14(6), 1767–1775 (2015)ADSMathSciNetCrossRefMATH

Title: Laplacian versus adjacency matrix in quantum walk search
Authors: Thomas G. Wong
Luís Tarrataca
Nikolay Nahimov
Publication date: 01-10-2016
Publisher: Springer US
Published in: Quantum Information Processing / Issue 10/2016
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-016-1373-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 10/2016

Scattering-induced quantum correlation in electronic waveguides with static magnetic impurities

Application of generalized operator representation in the time evolution of quantum systems

Generation of atomic NOON states via shortcuts to adiabatic passage

Physical synthesis of quantum circuits using templates

Bayesian Nash equilibria using extended Werner-like states

Differential geometric treewidth estimation in adiabatic quantum computation