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 6/2017

01-06-2017

Exceptional quantum walk search on the cycle

Authors: Thomas G. Wong, Raqueline A. M. Santos

Published in: Quantum Information Processing | Issue 6/2017

Log in

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

search-config
loading …

Abstract

Quantum walks are standard tools for searching graphs for marked vertices, and they often yield quadratic speedups over a classical random walk’s hitting time. In some exceptional cases, however, the system only evolves by sign flips, staying in a uniform probability distribution for all time. We prove that the one-dimensional periodic lattice or cycle with any arrangement of marked vertices is such an exceptional configuration. Using this discovery, we construct a search problem where the quantum walk’s random sampling yields an arbitrary speedup in query complexity over the classical random walk’s hitting time. In this context, however, the mixing time to prepare the initial uniform state is a more suitable comparison than the hitting time, and then, the speedup is roughly quadratic.
previous article Quantum image encryption scheme with iterative generalized Arnold transforms and quantum image cycle shift operations
next article Characterizing the Nash equilibria of a three-player Bayesian quantum game

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
Appendix
Available only for authorised users
Footnotes
1
\(f(x) = {\Theta }(g(x))\) means f is asymptotically bounded both above and below by g, so there exist positive constants \(c_1, c_2\), and \(x'\) such that \(c_1 g(x) \le f(x) \le c_2 g(x)\) for all \(x \ge x'\). It is related to the more familiar big-O notation, which is only an upper bound.
 
Literature
1.
2.
3.
Tulsi, A.: Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 78, 012310 (2008)ADSCrossRefMATH
4.
Magniez, F., Nayak, A., Richter, P.C., Santha, M.: On the hitting times of quantum versus random walks. Algorithmica 63(1), 91–116 (2012)MathSciNetCrossRefMATH
5.
Ambainis, A., Bačkurs, A., Nahimovs, N., Ozols, R., Rivosh, A.: Search by quantum walks on two-dimensional grid without amplitude amplification. In: Proceedings of the 7th Conference on Theory of Quantum Computation. Communication, and Cryptography, TQC 2012, pp. 87–97. Springer, Berlin (2013)
6.
Krovi, H., Magniez, F., Ozols, M., Roland, J.: Quantum walks can find a marked element on any graph. Algorithmica 74(2), 851–907 (2016)MathSciNetCrossRefMATH
7.
Ambainis, A., Kokainis, M.: Analysis of the extended hitting time and its properties. Poster given at the 18th Annual Conference on Quantum Information Processing (QIP 2015) in Sydney, Australia (2015)
8.
9.
10.
Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing. STOC ’01, pp. 50–59. ACM, New York, NY, USA (2001)
11.
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’05, pp. 1099–1108. SIAM, Philadelphia, PA, USA (2005)
12.
Ambainis, A., Rivosh, A.: Quantum walks with multiple or moving marked locations. In: Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM 2008, pp. 485–496. Springer, Nový Smokovec, Slovakia (2008)
13.
Nahimovs, N., Rivosh, A.: Quantum walks on two-dimensional grids with multiple marked locations. In: Proceedings of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM 2016, pp. 381–391. Springer, Harrachov, Czech Republic (2016)
14.
Nahimovs, N., Rivosh, A.: Exceptional configurations of quantum walks with Grover’s coin. In: Proceedings of the 10th International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. MEMICS 2015, pp. 79–92. Springer, Telč, Czech Republic (2016)
15.
Nahimovs, N., Santos, R.A.M.: Adjacent vertices can be hard to find by quantum walks. In: Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM 2017, pp. 256–267. Springer, Limerick, Ireland (2017)
16.
Prūsis, K., Vihrovs, J., Wong, T.G.: Stationary states in quantum walk search. Phys. Rev. A 94, 032334 (2016)ADSCrossRefMATH
17.
Szegedy, M.: Quantum speed-up of markov chain based algorithms. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. FOCS ’04, pp. 32–41. IEEE Computer Society, Washington, DC, USA (2004)
18.
19.
Portugal, R.: Hitting time. In: Quantum Walks and Search Algorithms, pp. 165–193. Springer, New York, New York, NY, USA (2013)
20.
Portugal, R., Santos, R.A.M., Fernandes, T.D., Gonçalves, D.N.: The staggered quantum walk model. Quantum Inf. Process. 15(1), 85–101 (2016)ADSMathSciNetCrossRefMATH
21.
Santos, R.A.M., Portugal, R.: Quantum hitting time on the cycle. In: Proceedings of the 3rd WECIQ Workshop/School of Computation and Quantum Information (2010)
22.
Wong, T.G., Ambainis, A.: Quantum search with multiple walk steps per oracle query. Phys. Rev. A 92, 022338 (2015)ADSCrossRef
23.
Wong, T.G., Tarrataca, L., Nahimov, N.: Laplacian versus adjacency matrix in quantum walk search. Quantum Inf. Process. 15(10), 4029–4048 (2016)ADSMathSciNetCrossRefMATH
24.
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH
25.
Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004)ADSCrossRef
26.
Marquezino, F.L., Portugal, R., Abal, G.: Mixing times in quantum walks on two-dimensional grids. Phys. Rev. A 82, 042341 (2010)ADSMathSciNetCrossRef
27.
28.
Santos, R.A.M.: Quantum Markov chains. Master’s thesis, National Laboratory for Scientific Computing (LNCC) (2010) (in Portuguese)
Metadata
Title
Exceptional quantum walk search on the cycle
Authors
Thomas G. Wong
Raqueline A. M. Santos
Publication date
01-06-2017
Publisher
Springer US
Published in
Quantum Information Processing / Issue 6/2017
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-017-1606-y

Other articles of this Issue 6/2017

Quantum Information Processing 6/2017 Go to the issue

OriginalPaper

The excitonic qubit coupled with a phonon bath on a star graph: anomalous decoherence and coherence revivals

OriginalPaper

Noisy metrology: a saturable lower bound on quantum Fisher information

OriginalPaper

Protecting single-photon entanglement with practical entanglement source

OriginalPaper

Dynamics of entanglement and quantum Fisher information for N-level atomic system under intrinsic decoherence

OriginalPaper

Characterizing the Nash equilibria of a three-player Bayesian quantum game

OriginalPaper

Optimal quantum thermometry by dephasing