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
Quantum Information Processing
Published in: Quantum Information Processing 4/2018

01-04-2018

Partition-based discrete-time quantum walks

Authors: Norio Konno, Renato Portugal, Iwao Sato, Etsuo Segawa

Published in: Quantum Information Processing | Issue 4/2018

Log in

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

search-config
loading …

Abstract

We introduce a family of discrete-time quantum walks, called two-partition model, based on two equivalence-class partitions of the computational basis, which establish the notion of local dynamics. This family encompasses most versions of unitary discrete-time quantum walks driven by two local operators studied in literature, such as the coined model, Szegedy’s model, and the 2-tessellable staggered model. We also analyze the connection of those models with the two-step coined model, which is driven by the square of the evolution operator of the standard discrete-time coined walk. We prove formally that the two-step coined model, an extension of Szegedy model for multigraphs, and the two-tessellable staggered model are unitarily equivalent. Then, selecting one specific model among those families is a matter of taste not generality.
previous article Vertices cannot be hidden from quantum spatial search for almost all random graphs
next article Time-optimal control with finite bandwidth

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
Footnotes
1
A clique of G is a set of vertices that induces a complete subgraph of G.
 
Literature
1.
Ambainis, A.: Quantum walks and their algorithmic applications. Int. J. Quantum Inf. 1, 507–518 (2003)CrossRefMATH
2.
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithm, pp. 1099–1108 (2005)
3.
Ambainis, A., Portugal, R., Nahimov, N.: Spatial search on grids with minimum memory. Quantum Inf. Comput. 15, 1233–1247 (2015)MathSciNet
4.
Asboth, J.K., Oroszlany, L., Palyi, A.: A Short Course on Topological Insulators: Band-Structure Topology and Edge States in One and Two Dimensions, Lecture Notes in Physics, vol. 919. Springer, Berlin (2016)MATH
5.
Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, pp. 50–59 (2000)
6.
Cantero, M.J., Moral, L., Velázquez, L.: Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle. Linear Algebra Appl. 362, 29–56 (2003)MathSciNetCrossRefMATH
7.
Cantero, M.J., Grünbaum, F.A., Moral, L., Velázquez, L.: The CGMV method for quantum walks. Quantum Inf. Process. 11, 1149–1192 (2012)MathSciNetCrossRefMATH
8.
Carteret, H.A., Ismail, M.E.H., Richmond, B.: Three routes to the exact asymptotics for the one-dimensional quantum walk. J. Phys. A Math. Gen. 36, 8775 (2003)ADSMathSciNetCrossRefMATH
9.
10.
Feynman, R.F., Hibbs, A.R.: Quantum Mechanics and Path Integrals. McGraw-Hill Inc, New York (1965)MATH
11.
Gudder, S.: Quantum Probability. Academic Press Inc., New York (1988)MATH
12.
Higuchi, Yu., Konno, N., Sato, I., Segawa, E.: Quantum graph walks I: mapping to quantum walks. Yokohama Math. J. 59, 33–55 (2013)MathSciNetMATH
13.
Higuchi, Y., Konno, N., Sato, I., Segawa, E.: A remark on zeta functions of finite graphs via quantum walks. Pac. J. Math Ind. 6, 73–84 (2014)MathSciNetCrossRefMATH
14.
15.
Kitagawa, T., Rudner, M.S., Berg, E., Demler, E.: Exploring topological phases with quantum walks. Phys. Rev. A 82, 033429 (2010)ADSCrossRef
16.
Konno, N.: Quantum Walks, Lecture Notes in Mathematics. Springer, Berlin, Heidelberg (2008)
17.
18.
Matsue, K., Ogurisu, O., Segawa, E.: A note on the spectral mapping theorem of quantum walk models. Interdiscip. Inf. Sci. 23, 105–114 (2017)MathSciNet
19.
Matsuoka, L., Yokoyama, K.: Physical implementation of quantum cellular automaton in a diatomic molecule. J. Comput. Theor. Nanosci. 10, 1617–1620 (2013)CrossRef
20.
Manouchehri, K., Wang, J.: Physical Implementation of Quantum Walks. Springer, Berlin (2014)CrossRefMATH
21.
22.
23.
Peterson, D.: Gridline graphs: a review in two dimensions and an extension to higher dimensions. Discrete Appl. Math. 126, 223 (2003)MathSciNetCrossRefMATH
24.
Portugal, R.: Establishing the equivalence between Szegedy’s and coined quantum walks using the staggered model. Quantum Inf. Process. 15, 1387–1409 (2016)ADSMathSciNetCrossRefMATH
25.
26.
27.
28.
Portugal, R., Segawa, E.: Connecting coined quantum walks with Szegedy’s model. Interdiscip. Inf. Sci. 23, 119–125 (2017)MathSciNet
29.
Segawa, E.: Localization of quantum qalks induced by recurrence properties of random walks. J. Comput. Theor. Nanosci. 10, 1583–1590 (2013)CrossRef
30.
31.
Shenvi, N., Kempe, J., Whaley, K.: Quantum random-walk search algorithm. Phys. Rev. A 67, 052307 (2003)ADSCrossRef
32.
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 32–41 (2004)
Metadata
Title
Partition-based discrete-time quantum walks
Authors
Norio Konno
Renato Portugal
Iwao Sato
Etsuo Segawa
Publication date
01-04-2018
Publisher
Springer US
Published in
Quantum Information Processing / Issue 4/2018
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-017-1807-4

Other articles of this Issue 4/2018

Quantum Information Processing 4/2018 Go to the issue

OriginalPaper

Master Lovas–Andai and equivalent formulas verifying the two-qubit Hilbert–Schmidt separability probability and companion rational-valued conjectures

OriginalPaper

Quantum coherence behaviors of fermionic system in non-inertial frame

OriginalPaper

Separable decompositions of bipartite mixed states

OriginalPaper

Concurrence of three Jaynes–Cummings systems

OriginalPaper

Quantum correlations for bipartite continuous-variable systems

OriginalPaper

Control of single-photon routing in a T-shaped waveguide by another atom