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 1/2020

01-01-2020

Szegedy quantum walks with memory on regular graphs

Authors: Dan Li, Ying Liu, Yu-Guang Yang, Juan Xu, Jia-Bin Yuan

Published in: Quantum Information Processing | Issue 1/2020

Log in

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

search-config
loading …

Abstract

Quantum walks with memory (QWM) are types of modified quantum walks that record the walker’s latest path. The general model of coined QWM is presented in Li et al. (Phys Rev A 93:042323, 2016). In this paper, we present the general Szegedy QWM model and we describe its relationship with the coined QWM model. A coined QWM can be transformed into a Szegedy QWM, while a Szegedy QWM can be transformed into a coined QWM with any partition. These results may help in the analysis of the coined QWM. By transforming a coined QWM into a Szegedy QWM, the essential structure of the coined QWM is revealed. We give an example and we prove that two known QWMs are equal when they have a proper position-dependent coin operator.
previous article Partial distinguishability as a coherence resource in boson sampling
next article A weak limit theorem for a class of long-range-type quantum walks in 1d

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
Literature
1.
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: STOC’01 Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, p. 37. ACM, New York (2011)
2.
3.
Chou, C.I., Ho, C.L.: Localization and recurrence of a quantum walk in a periodic potential on a line. Chin. Phys. B 23, 110302 (2014)ADSCrossRef
4.
Li, M., Zhang, Y.S., Guo, G.C.: Average position in quantum walks with a U(2) coin. Chin. Phys. B 22, 030310 (2013)ADSCrossRef
5.
Xue, P., Sanders, B.C.: Two quantum walkers sharing coins. Phys. Rev. A 85, 022307 (2012)ADSCrossRef
6.
Di Franco, C., Mc Gettrick, M., Busch, T.: Mimicking the probability distribution of a two-dimensional. Phys. Rev. L 106, 080502 (2011)ADSCrossRef
7.
Di Franco, C., Mc Gettrick, M., Machida, T., Busch, T.: Alternate two-dimensional quantum walk with a single-qubit. Phys. Rev. A 84, 042337 (2011)ADSCrossRef
8.
9.
Li, D., Mc Gettrick, M., Zhang, W.W., Zhang, K.J.: One-dimensional quantum lazy walks and occupancy rate. Chin. Phys. B 24, 050305 (2015)ADSCrossRef
10.
Li, D., Zhang, J., Guo, F.Z., Huang, W., Wen, Q.Y., Chen, H.: Discrete interacting quantum walks and quantum hash scheme. Quant., Inf. Proc. 12, 1501 (2013)MathSciNetCrossRef
11.
Li, D., Yang, Y.G., Bi, J.L., Yuan, J.B., Xu, J.: Controlled alternate quantum walks based quantum hash function. Sci. Rep. 8, 225 (2018)ADSCrossRef
12.
Rohde, P.P., Schreiber, A., Stefanak, M., Jex, I., Silberhorn, C.: Multi-walker discrete time quantum walks on arbitrary graphs, their properties and their photonic implementation. New J. Phys. 13, 013001 (2011)ADSCrossRef
13.
Mayer, K., Tichy, M.C., Mintert, F., Konrad, T., Buchleitner, A.: Counting statistics of many-particle quantum walks. Phys. Rev. A 83, 062307 (2011)ADSCrossRef
14.
Zhang, R., Qin, H., Tang, B., Xue, P.: Disorder and decoherence in coined quantum walks. Chin. Phys. B 22, 110312 (2013)ADSCrossRef
15.
Zhang, R., Xu, Y.Q., Xue, P.: Disordered quantum walks in two-dimensional lattices. Chin. Phys. B 24, 010303 (2015)ADSCrossRef
16.
17.
Shenvi, N., Kempe, J., Birgitta Whaley, K.: Quantum random-walk search algorithm. Phys. Rev. A 67, 052307 (2003)ADSCrossRef
18.
Hein, B., Tanner, G.: Quantum search algorithms on a regular lattice. Phys. Rev. A 82, 012326 (2010)ADSCrossRef
19.
Berry, S.D., Wang, J.B.: Quantum-walk-based search and centrality. Phys. Rev. A 82, 042333 (2010)ADSCrossRef
20.
Tarrataca, L., Wichert, A.: Intricacies of quantum computational paths. Quant. Inf. Proc. 12, 1365 (2013)CrossRef
21.
Berry, S.D., Wang, J.B.: Two-particle quantum walks: entanglement and graph. Phys. Rev. A 83, 042317 (2011)ADSCrossRef
22.
Douglas, B.L., Wang, J.B.: Classical approach to the graph isomorphism problem using quantum walks. J. Phys. A 41, 075303 (2008)ADSMathSciNetCrossRef
23.
Rohde, P.P., Brennen, G.K., Gilchrist, A.: Quantum walks with memory provided by recycled coins and a memory of the coin-flip history. Phys. Rev. A 87, 052302 (2013)ADSCrossRef
24.
Mc Gettrick, M.: One dimensional quantum walks with memory. Quant. Inf. Comput. 10, 0509 (2010)MathSciNet
25.
26.
Konno, N., Machida, T.: Limit theorems for quantum walks with memory. Quant. Inf. Comput. 10, 1004 (2010)MathSciNetMATH
27.
Li, D., Mc Gettrick, M., Gao, F., Xu, J., Wen, Q.Y.: Generic quantum walks with memory on regular graphs. Phys. Rev. A 93, 042323 (2016)ADSMathSciNetCrossRef
28.
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: FOCS’04 Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p. 32 (2004)
29.
Portugal, R.: Establishing the equivalence between Szegedy’s and coined quantum walks using the staggered model. Quant. Inf. Proc. 15, 1387 (2016)MathSciNetCrossRef
30.
Konno, N., Portugal, R., Sato, I., Segawa, E.: Partition-based discrete-time quantum walks. Quant. Inf. Proc. 17, 100 (2018)MathSciNetCrossRef
31.
Liu, Y., Yuan, J.B., Duan, B.J., Li, D.: Quantum walks on graphs regular uniform hypergraphs. Sci. Rep. 8, 9548 (2018)ADSCrossRef
32.
Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proceeding SODA’06 Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, p. 880 (2006)
33.
Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413 (2007)MathSciNetCrossRef
34.
35.
Wang, G.: Quantum algorithms for approximating the effective resistances in electrical networks. Quant. Inf. Comput. 17(11 and 12), 987 (2017)
36.
Paparo, G.D., Muller, M., Comellas, F., Angel, M., Delgado, M.: Quantum google in a complex network. Sci. Rep. 3, 2773 (2013)ADSCrossRef
Metadata
Title
Szegedy quantum walks with memory on regular graphs
Authors
Dan Li
Ying Liu
Yu-Guang Yang
Juan Xu
Jia-Bin Yuan
Publication date
01-01-2020
Publisher
Springer US
Published in
Quantum Information Processing / Issue 1/2020
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-019-2534-9

Other articles of this Issue 1/2020

Quantum Information Processing 1/2020 Go to the issue

OriginalPaper

New EAQEC codes constructed from Galois LCD codes

OriginalPaper

Entanglement and coherence in quantum prisoner’s dilemma

OriginalPaper

Optimal estimation of parameters for scalar field in an expanding spacetime exhibiting Lorentz invariance violation

OriginalPaper

Broadcasting of entanglement via orthogonal and non-orthogonal state-dependent cloners

OriginalPaper

Classical access structures of ramp secret sharing based on quantum stabilizer codes

OriginalPaper

Explicit demonstration of initial state construction in artificial neural networks using NetKet and IBM Q experience platform