Top

Quantum Information Processing

Published in:

01-08-2023

Odd-periodic Grover Walks

Author: Yusuke Yoshie

Published in: Quantum Information Processing | Issue 8/2023

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

search-config

AI-assisted search

Off

Abstract

The Grover walk is one of the most well-studied quantum walks on graphs. In this paper, we investigate its periodicity to reveal the relationship between the quantum walk and the underlying graph, focusing particularly on the characterization of graphs exhibiting a periodic Grover walk. Graphs having a periodic Grover walk with periods of 2, 3, 4, and 5 have previously been characterized. It is expected that graphs exhibiting a periodic Grover walk with odd period correspond to cycles with odd length. We address that problem and are able to perfectly characterize the class of graphs exhibiting an odd-periodic Grover walk by using a combinatorial method.

previous article Homomorphic polynomial public key encapsulation over two hidden rings for quantum-safe key encapsulation

next article Noise analysis for the Sorkin and Peres tests performed on a quantum computer

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

Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theory Comput. 1, 47–79 (2005)MathSciNetCrossRefMATH

Aharonov, Y., Davidvich, L., Zagury, N.: Quantum random walks. Phys. Rev. A 48, 1687–1690 (1993)ADSCrossRef

Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs, Proceedings of the 33rd annual ACM symposium on theory of computing, ACM, (2001), 50–59

Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster, Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithm, (2005), 1099–1108

Barr, K.E., Proctor, T.J., Allen, D., Kendon, V.M.: Periodicity and perfect state transfer in quantum walks on variants of cycles. Quantum Inf. Comput. 14, 417–438 (2014)MathSciNet

Bose, S.: Quantum communication through an unmodulated spin chain. Phys. Rev. Lett. 91, 207901 (2003)ADSCrossRef

Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, New York (2012)CrossRefMATH

Emms, D.M., Hancock, E.R., Severini, S., Wilson, R.C.: A matrix representation of graphs and its spectrum as a graph invariant. Electron. J. Comb. 13, R34 (2006)MathSciNetCrossRefMATH

Godsil, C.: State transfer on graphs. Discret. Math. 312, 129–147 (2012)MathSciNetCrossRefMATH

10.

Gudder, S.: Quantum Probability. Academic Press, Cambridge (1998)MATH

11.

Higuchi, Yu., Konno, N., Sato, I., Segawa, E.: Periodicity of the discrete-time quantum walk on finite graph. Interdiscip. Inf. Sci. 23, 75–86 (2017)MathSciNetMATH

12.

Higuchi, Yu., Segawa, E.: Quantum walks induced by Dirichlet random walks on infinite trees. J. Phys. A Math. Theor. 51, 075303 (2017)ADSMathSciNetCrossRefMATH

13.

Iwamoto, M.: Periodicity of the discrete-time quantum walk on graphs (Japanese), Master thesis, Ehime University. (2018)

14.

Kendon, V.M., Tamon, C.: Perfect state transfer in quantum walks on graphs. J. Comput. Theor. Nanosci. 8, 422–433 (2011)CrossRef

15.

Konno, N., Shimizu, Y., Takei, M.: Periodicity for the Hadamard walk on cycle. Interdiscip. Inf. Sci. 23, 1–8 (2017)MathSciNetMATH

16.

Kubota, S., Segawa, E., Taniguchi, T., Yoshie, Y.: Periodicity of Grover walks on generalized Bethe trees. Linear Algebra Appl. 554, 371–391 (2018)MathSciNetCrossRefMATH

17.

Kubota, S., Segawa, E., Taniguchi, T., Yoshie, Y.: A quantum walk induced by Hoffman graphs and its periodicity. Linear Algebra Appl. 579, 217–236 (2019)MathSciNetCrossRefMATH

18.

Manouchehri, K., Wang, J.: Physical Implementation of Quantum Walks. Springer-Verlag, Berlin (2014)CrossRefMATH

19.

Panda, A., Benjamin, C.: Order from chaos in quantum walks on cyclic graphs. Phys. Rev. A 104(1), 012204 (2021)ADSMathSciNetCrossRef

20.

Portugal, R.: Quantum Walks and Search Algorithms. Springer-Verlag, New York (2013)CrossRefMATH

21.

Rivlin, T.J.: The Chebyshev Polynomials. Wiley, New-York (1974)MATH

22.

Saito, K.: Periodicity for the Fourier quantum walk on regular graphs. Quantum Inf. Comput. 19, 23–34 (2018)MathSciNet

23.

Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A 67, 052307 (2003)ADSCrossRef

24.

Szegedy, M.: Quantum speed-up of Markov chain based algorithms, Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, (2004), 32–41

25.

Venegas-Andraca, S.E.: Quantum Walks for Computer Scientists. Morgan and Claypool, San Rafael (2008)CrossRef

26.

Watrous, J.: Quantum simulations of classical random walks and undirected graph connectivity. J. Comput. Syst. Sci. 62, 376–391 (2001)MathSciNetCrossRefMATH

27.

Yoshie, Y.: Characterizations of graphs to induce periodic Grover walk. Yokohama Math. J. 63, 9–23 (2017)MathSciNetMATH

28.

Yoshie, Y.: Periodicities of Grover walks on distance-regular graphs. Graphs Comb. 35, 1305–1321 (2019)MathSciNetCrossRefMATH

Title: Odd-periodic Grover Walks
Author: Yusuke Yoshie
Publication date: 01-08-2023
Publisher: Springer US
Published in: Quantum Information Processing / Issue 8/2023
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-023-04078-y

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 8/2023

Entanglement measure based on optimal entanglement witness

Quantum correlation dynamics of a three-qubit XXZ spin chain with spin–orbit coupling in the presence of intrinsic decoherence

Entanglement of two quantum dots with dipole–dipole interaction coupled to a cavity in plasmonic waveguide system

Quantum meaningful visual cryptography

Optimal sufficient requirements on the embedded Ising problem in polynomial time

Nonequilibrium effects on quantum temporal steering