nach oben

Natural Computing

Erschienen in:

01.03.2012

Partitioned quantum cellular automata are intrinsically universal

verfasst von: Pablo Arrighi, Jonathan Grattage

Erschienen in: Natural Computing | Ausgabe 1/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

There have been several non-axiomatic approaches taken to define quantum cellular automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.

Vorheriger Artikel The Deutsch–Jozsa problem: de-quantisation and entanglement

Nächster Artikel Spatial search using the discrete time quantum walk

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Albert J, Culik K (1987) A simple universal cellular automaton and its one-way and totalistic version. Complex Syst 1:1–16MATHMathSciNet

Arrighi P, Fargetton R, Wang Z (2009) Intrinsically universal one-dimensional quantum cellular automata in two flavours. Fundamenta Informaticae 21:1001–1035MathSciNet

Arrighi P, Grattage J (2009) Intrinsically universal n-dimensional quantum cellular automata. Journal version of refereed conference proceedings. ArXiv preprint: arXiv:0907.3827 (submitted)

Arrighi P, Grattage J (2010) A simple n-dimensional intrinsically universal quantum cellular automaton. In: Language and automata theory and applications. Lecture notes in computer science, vol 6031. Springer, Heidelberg, pp 70–81

Arrighi P, Nesme V, Werner RF (2008) Quantum cellular automata over finite, unbounded configurations. In: Proceedings of MFCS. Lecture notes in computer science, vol 5196. Springer, Heidelberg, pp 64–75

Arrighi P, Nesme V, Werner R (2010) Unitarity plus causality implies localizability. QIP 2010 and J Comput Syst Sci. ArXiv preprint: arXiv:0711.3975

Banks ER (1970) Universality in cellular automata. In: SWAT ’70: Proceedings of the 11th annual symposium on switching and automata theory (SWAT 1970). IEEE Computer Society, Washington, DC, USA, pp 194–215

Berlekamp ER, Conway JH, Guy RK (2003) Winning ways for your mathematical plays. AK Peters Ltd, Wellesley

Brennen GK, Williams JE (2003) Entanglement dynamics in one-dimensional quantum cellular automata. Phys Rev A 68(4):042311CrossRefMathSciNet

Dür W, Vidal G, Cirac JI (2000) Three qubits can be entangled in two inequivalent ways. Phys Rev A 62:062314CrossRefMathSciNet

Durand B, Roka Z (1998) The game of life: universality revisited, Research report 98-01. Technical report, Ecole Normale Suprieure de Lyon

Durand-Lose JO (1995) Reversible cellular automaton able to simulate any other reversible one using partitioning automata. In: LATIN’95: theoretical informatics. Lecture notes in computer science, number 911. Springer, Heidelberg, pp 230–244

Durand-Lose JO (1997) Intrinsic universality of a 1-dimensional reversible cellular automaton. In: Proceedings of STACS 97. Lecture notes in computer science. Springer, Heidelberg, p 439

Durand-Lose JO (2008) Universality of cellular automata. In: Encyclopedia of complexity and system science. Springer, New York, p 22

Feynman RP (1986) Quantum mechanical computers. Foundations of Physics (Historical Archive) 16(6):507–531CrossRefMathSciNet

Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3:320–375MATHCrossRefMathSciNet

Inokuchi S, Mizoguchi Y (2005) Generalized partitioned quantum cellular automata and quantization of classical CA. Int J Unconv Comput. ArXiv preprint: quant-ph/0312102, 1:149–160

Karafyllidis IG (2004) Definition and evolution of quantum cellular automata with two qubits per cell. Phys Rev A 70:044301CrossRef

Kari J (1999) On the circuit depth of structurally reversible cellular automata. Fundamenta Informaticae 38(1-2):93–107MATHMathSciNet

Lloyd S (2005) A theory of quantum gravity based on quantum computation. ArXiv preprint: quant-ph/0501135

Margolus N (1984) Physics-like models of computation. Phys D Nonlinear Phenom 10(1–2):81–95

Margolus N (1990) Parallel quantum computation. In: Complexity, entropy, and the physics of information: the proceedings of the 1988 workshop on complexity, entropy, and the physics of information held May–June, 1989. Perseus Books, Santa Fe, New Mexico, p 273

Mazoyer J (1987) A six-state minimal time solution to the firing squad synchronization problem. Theor Comput Sci 50:183–238MATHCrossRefMathSciNet

Mazoyer J, Rapaport I (1998) Inducing an order on cellular automata by a grouping operation. In: Proceedings of STACS’98. Lecture notes in computer science, vol 1373. Springer, Heidelberg, pp 116–127

Morita K (1995) Reversible simulation of one-dimensional irreversible cellular automata. Theoretical Computer Science 148(1):157–163MATHCrossRef

Morita K, Harao M (1989) Computation universality of one-dimensional reversible (injective) cellular automata. IEICE Trans Inf Syst E 72:758–762

Morita K, Ueno S (1992) Computation-universal models of two-dimensional 16-state reversible cellular automata. IEICE Trans Inf Syst E 75:141–147

Nagaj D, Wocjan P (2008) Hamiltonian quantum cellular automata in 1D. ArXiv preprint: arXiv:0802.0886

Ollinger N (2008) Universalities in cellular automata a (short) survey. In: Durand B (eds) First symposium on cellular automata “Journées Automates Cellulaires” (JAC 2008), Uzès, France, April 21–25, 2008. Proceedings. MCCME Publishing House, Moscow, pp 102–118

Paz JP, Zurek WH (2002) Environment-induced decoherence and the transition from quantum to classical. Lecture notes in physics, Springer, Heidelberg, pp 77–140

Pérez-Delgado CA, Cheung D (2007) Local unreversible cellular automaton ableitary quantum cellular automata. Phys Rev A 76(3):32320CrossRef

Raussendorf R (2005) Quantum cellular automaton for universal quantum computation. Phys Rev A 72(2):22301CrossRefMathSciNet

Schumacher B, Werner R (2004) Reversible quantum cellular automata. ArXiv pre-print quant-ph/0405174

Shepherd DJ, Franz T, Werner RF (2006) A universally programmable quantum cellular automata. Phys Rev Lett 97:020502

Theyssier G (2004) Captive cellular automata. In: Proceedings of MFCS 2004. Lecture notes in computer science, vol 3153. Springer, Heidelberg, pp 427–438

Toffoli T (1977) Computation and construction universality of reversible cellular automata. J Comput Syst Sci 15(2): 213–231

Van Dam W (1996) Quantum cellular automata. Masters thesis, University of Nijmegen, The Netherlands

Vollbrecht KGH, Cirac JI (2004) Reversible universal quantum computation within translation-invariant systems. New J Phys Rev A 73:012324CrossRef

von Neumann J (1966) Theory of self-reproducing automata. University of Illinois Press, Champaign, IL

Watrous J (1991) On one-dimensional quantum cellular automata. Complex Syst 5(1):19–30MathSciNet

Watrous J (1995) Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on 23–25 October 1995, Milwaukee, WI, USA, pp 528–537

Titel: Partitioned quantum cellular automata are intrinsically universal
verfasst von: Pablo Arrighi
Jonathan Grattage
Publikationsdatum: 01.03.2012
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2012
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-011-9277-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2012

Topological Active Volume 3D segmentation model optimized with genetic approaches

A survey of recursive analysis and Moore’s notion of real computation

A Chaitin number based on compressible strings

Neural computation with cellular cultures

Quantum computation with write-only memory

Editorial for special issue on unconventional computation

Premium Partner