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
Natural Computing
Published in: Natural Computing 1/2015

01-03-2015

Simulation methods for quantum walks on graphs applied to formal language recognition

Authors: K. Barr, T. Fleming, V. Kendon

Published in: Natural Computing | Issue 1/2015

Log in

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

search-config
loading …

Abstract

We describe an algorithm which automates the generation of appropriate shift and coin operators for a discrete time quantum walk, given the adjacency matrix of the graph over which the walk is run. This gives researchers the freedom to numerically investigate any discrete time quantum walk over graphs of a computationally tractable size by greatly reducing the time required to initialise a given walk. We then describe one application in which the swift initialisation of walks has enabled systematic investigations of walks over a large number of structures. New results concerning this application, which is to formal language recognition, are described. The reliability of these results, as well as the general suitability of numerical analysis as a tool for investigating discrete time quantum walks, are briefly discussed. We also mention specific Python packages which facilitate our simulations and analysis, motivating the use of high level programming languages in this context.
previous article Advantages of Model Driven Engineering for studying complex systems
next article Using a simulated Wolbachia infection mechanism to improve multi-objective evolutionary algorithms

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
Ambainis A (2004) Quantum walk algorithm for element distinctness. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science. IEEE Computer Society, Washington, DC, pp 22–31
Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J (2001) One-dimensional quantum walks. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing. ACM, New York, pp 37–49
Barr K, Felming T, Kendon V (2013) Simulation methods for quantum walks on graphs applied to perfect state transfer and formal language recognition. In: Stepney S, Andrews PS (eds) Proceedings of the 2013 workshop on complex systems modelling and simulation, Milan, Italy, July 2013. Luniver Press, Frome
Bašić M, Petković MD, Stevanović D (2009) Perfect state transfer in integral circulant graphs. Appl Math Lett 22(7):1117–1121CrossRefMATHMathSciNet
Bose S (2003) Quantum communication through an unmodulated spin chain. Phys Rev Lett 91(20):207901CrossRef
Childs AM, Gosset D, Webb Z (2013) Universal computation by multiparticle quantum walk. Science 339(6121):791–794CrossRefMathSciNet
Gottlieb AD, Janson S, Scudo PF (2005) Convergence of coined quantum walks on \(\mathbb{R}_d\). Infin Dimens Anal Quantum Probab Relat Top 8(1):129–140CrossRefMathSciNet
Grover LK (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, New York, pp 212–219
Hopcroft J, Ullman J (1979) Introduction to automata theory, languages, and computation. Addison-Wesley, ReadingMATH
Jaro MA (1989) Advances in record-linkage methodology as applied to matching the 1985 census of Tampa, Florida. J Am Stat Assoc 84(406):414–420CrossRef
Jaro MA (1995) Probabilistic linkage of large public health data files. Stat Med 14(5–7):491–498CrossRef
Kendon VM, Tamon C (2011) Perfect state transfer in quantum walks on graphs. J Comput Theor Nanosci 8(3):422–433CrossRef
Kendon V, Tregenna B (2003) Decoherence can be useful in quantum walks. Phys Rev A 67(4):042315CrossRef
Kondacs A, Watrous J (1997) On the power of quantum finite state automata. In: FOCS 1997, pp 66–75
Lovett NB, Cooper S, Everitt M, Trevers M, Kendon V (2010) Universal quantum computation using the discrete-time quantum walk. Phys Rev A 81(4):042330CrossRefMathSciNet
Moore C, Russell A (2002) Quantum walks on the hypercube. In: Randomization and approximation techniques in computer science. Springer, Berlin, pp 164–178
Papadimitriou CH (1991) On selecting a satisfying truth assignment. In: Proceedings of the 32nd annual IEEE symposium on foundations of computer science, 1991, pp 163–169
Saxena N, Severini S, Shparlinski IE (2007) Parameters of integral circulant graphs and periodic quantum dynamics. Int J Quantum Inf 5(03):417–430CrossRefMATH
Schoning T (1999) A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: 40th Annual IEEE symposium on foundations of computer science, 1999, pp 410–414
Shenvi N, Kempe J, Whaley K (2003) Quantum random-walk search algorithm. Phys Rev A 67:052307CrossRef
Shor PW (1994) Algorithms for quantum computation: discrete logarithms and factoring. In: 1994 Proceedings of the 35th annual IEEE symposium on foundations of computer science, pp 124–134
Sipser M (2012) Introduction to the theory of computation. Cengage Learning, Boston
Tregenna B, Flanagan W, Maile R, Kendon V (2003) Controlling discrete quantum walks: coins and initial states. N J Phys 5(1):83CrossRef
Watrous J (1999) Quantum simulations of classical random walks and undirected graph connectivity. In: 1999 Proceedings of the fourteenth annual IEEE conference on computational complexity. IEEE, pp 180–187
Metadata
Title
Simulation methods for quantum walks on graphs applied to formal language recognition
Authors
K. Barr
T. Fleming
V. Kendon
Publication date
01-03-2015
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 1/2015
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-014-9441-x

Other articles of this Issue 1/2015

Natural Computing 1/2015 Go to the issue

EditorialNotes

CoSMoS special issue editorial

OriginalPaper

Environment orientation: a structured simulation approach for agent-based complex systems

OriginalPaper

A novel hybrid artificial bee colony algorithm with crossover operator for numerical optimization

OriginalPaper

Principled simulation of cell proliferation dynamics using the CoSMoS approach

OriginalPaper

Advantages of Model Driven Engineering for studying complex systems

OriginalPaper

Using a simulated Wolbachia infection mechanism to improve multi-objective evolutionary algorithms

Premium Partner

    Image Credits