Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2019 | OriginalPaper | Chapter

5. Quantum Walks

Authors : Franklin de Lima Marquezino, Renato Portugal, Carlile Lavor

Published in: A Primer on Quantum Computing

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Quantum walks are analogous to the classical random walks, and have important applications in quantum computation and quantum information. In this chapter, we give a gentle introduction to the first model of quantum walks—known as the coined model—, presented for the first time in 1993. Then, we consider the staggered model, which is much more recent and generalizes the most important types of quantum walks.

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
previous chapter Shor’s Algorithm for Integer Factorization
next chapter Conclusion and Further Remarks
Footnotes
1
If we measure the quantum walker after each step, then we recover the probability distribution of the classical random walker.
 
2
For the two-dimensional torus, we easily can adapt Eq. (5.13) by using modular arithmetics.
 
3
A clique a graph Γ(V, E) is a subset of V  such that any two vertices in the subset are adjacent, that is, a clique induces a complete subgraph.
 
4
It is possible to strengthen the power of the coined model by using the square of the evolution operator [3].
 
5
A line graph of a graph Γ (called root graph) is another graph L(Γ) so that each vertex of L(Γ) represents an edge of Γ and two vertices of L(Γ) are adjacent if and only if their corresponding edges share a common vertex in Γ.
 
6
A clique graph K(G) of a graph G is a graph such that every vertex represents a maximal clique of G and two vertices of K(G) are adjacent if and only if the corresponding maximal cliques in G share at least one vertex in common.
 
7
A k-colorable graph is the one whose vertices can be colored with at most k colors so that no two adjacent vertices share the same color.
 
8
At this point, it is highly recommended some computer algebra system, such as Sage (for those that prefer free software) or Mathematica or Maple.
 
9
In this context, Γ can be a multigraph.
 
Literature
1.
Abreu, A., Cunha, L., Fernandes, T., de Figueiredo, C., Kowada, L., Marquezino, F., Posner, D., Portugal, R.: The graph tessellation cover number: extremal bounds, efficient algorithms and hardness. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018: Theoretical Informatics, pp. 1–13. Springer, Cham (2018)
2.
3.
Konno, N., Portugal, R., Sato, I., Segawa, E.: Partition-based discrete-time quantum walks. Quantum Inf. Process. 17(4), 100 (2018)MathSciNetCrossRef
4.
Lawler, G.F., Limic, V.: Random Walk: A Modern Introduction, 1st edn. In: Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2010)CrossRef
5.
6.
Philipp, P., Portugal, R.: Exact simulation of coined quantum walks with the continuous-time model. Quantum Inf. Proc. 16(1), 14 (2017)MathSciNetCrossRef
7.
8.
Portugal, R., Santos, R.A.M., Fernandes, T.D., Gonçalves, D.N.: The staggered quantum walk model. Quantum Inf. Proc. 15(1), 85–101 (2016)MathSciNetCrossRef
9.
Portugal, R., de Oliveira, M.C., Moqadam, J.K.: Staggered quantum walks with Hamiltonians. Phys. Rev. A 95, 012,328 (2017)MathSciNetCrossRef
10.
Spitzer, F.: Principles of Random Walk, 2 edn. In: Graduate Texts in Mathematics. Springer, New York (1964)CrossRef
11.
Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Discret. Analiz. 3, 25–30 (1964)MathSciNet
Metadata
Title
Quantum Walks
Authors
Franklin de Lima Marquezino
Renato Portugal
Carlile Lavor
Copyright Year
2019
Book
A Primer on Quantum Computing

Print ISBN: 978-3-030-19065-1

Electronic ISBN: 978-3-030-19066-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-19066-8_5

Premium Partner

    Image Credits