Un automate cellulaire quantique (QCA) est un modèle abstrait de calcul quantique, conçu par analogie avec les modèles conventionnels d'automates cellulaires introduits par John von Neumann. Le même nom peut également faire référence aux automates cellulaires à points quantiques, qui sont une proposition d'implémentation physique des automates cellulaires "classiques" en exploitant les phénomènes de la mécanique quantique. Les QCA ont attiré beaucoup d'attention en raison de la taille extrêmement réduite de leurs caractéristiques (à l'échelle moléculaire ou même atomique) et de leur très faible consommation d'énergie, ce qui en fait un candidat au remplacement de la technologie CMOS.
Utilisation du terme Dans le contexte des modèles de calcul ou de systèmes physiques, automate cellulaire quantique se réfère à la fusion d'éléments à la fois (1) l'étude des automates cellulaires dans la science informatique conventionnelle et (2) l'étude du traitement de l'information quantique. En particulier, les modèles d'automates cellulaires quantiques présentent les caractéristiques suivantes : Le calcul est considéré comme étant le résultat d'une opération parallèle de plusieurs dispositifs de calcul, ou cellules. Les cellules sont généralement considérées comme des systèmes quantiques identiques de dimension finie (par exemple, chaque cellule est un qubit). Chaque cellule a un voisinage d'autres cellules. L'ensemble de ces cellules forme un réseau de cellules, qui est généralement considéré comme régulier (par exemple, les cellules sont disposées comme un treillis avec ou sans conditions périodiques aux limites). L'évolution de toutes les cellules présente un certain nombre de symétries semblables à celles de la physique. La localité en est une : le prochain état d'une cellule ne dépend que de son état actuel et de celui de ses voisins. L'homogénéité en est une autre : l'évolution agit de la même manière partout et est indépendante du temps. L'espace d'état des cellules et les opérations effectuées sur celles-ci devraient être motivés par les principes de la mécanique quantique.
Une autre caractéristique souvent considérée comme importante pour un modèle d'automate cellulaire quantique est qu'il doit être universel pour le calcul quantique (c'est-à-dire qu'il peut simuler efficacement des machines de Turing quantiquesC. Pérez-Delgado et D. Cheung, "Local Unitary Quantum Cellular Automata", Phys. Rev. A 76, 032320, 2007. Voir aussi arXiv:0709.0006 (quant-ph), un circuit quantiqueD.J. Shepherd, T. Franz, R.F. Werner : Universally programmable Quantum Cellular Automaton. Phys. Rev. Lett. 97, 020502 (2006) ou simplement tous les autres automates cellulaires quantiquesP. Arrighi, R. Fargetton, Z. Wang, Intrinsically universal one-dimensional quantum cellular automata in two flavours, Fundamenta Informaticae Vol.91, No.2, pp.197-230, (2009). Voir aussi (quant-ph)P. Arrighi, J. Grattage, A quantum Game of Life, Proceedings of JAC 2010, Turku, December 2010. TUCS Lecture Notes 13, 31-42, (2010). Voir aussi (quant-ph) et (Companion Website)).
Les modèles proposés récemment imposent d'autres conditions, par exemple que les automates cellulaires quantiques soient réversibles et/ou localement unitaires, et qu'ils aient une fonction de transition globale facile à déterminer à partir de la règle de mise à jour des cellules individuelles. Des résultats récents montrent que ces propriétés peuvent être dérivées axiomatiquement, à partir des symétries de l'évolution globaleB. Schumacher et R. Werner, "Reversible quantum cellular automata", quant-ph/0405174Pablo Arrighi, Vincent Nesme, Reinhard Werner, One-dimensional quantum cellular automata over finite, unbounded configurations. Voir aussi (quant-ph)Pablo Arrighi, Vincent Nesme, Reinhard Werner, N-dimensional quantum cellular automata. Voir aussi (quant-ph).
Premières propositions En 1982, Richard Feynman a suggéré une première approche pour quantifier un modèle d'automates cellulairesR. Feynman, "Simulating physics with computers", Int. J. Theor. Phys. 21, 1982 : pp. 467-488.. En 1985, David Deutsch a présenté un développement formel du sujetD. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer" Proceedings of the Royal Society of London A 400 (1985), pp. 97-117.. Plus tard, Gerhard Grössing et Anton Zeilinger ont introduit le terme « automates cellulaires quantiques » pour désigner un modèle qu'ils ont défini en 1988G. Grossing et A. Zeilinger, "Quantum cellular automata", Complex Systems 2 (2), 1988 : pp. 197-208 et 611-623., bien que leur modèle ait très peu en commun avec les concepts développés par Deutsch et n'ait donc pas été développé de manière significative en tant que modèle de calcul.
Modèles de calcul quantique universel Le premier modèle formel d'automates cellulaires quantiques à avoir fait l'objet de recherches approfondies est celui introduit par John Watrous. Ce modèle a été développé par Wim van DamW. van Dam, "Quantum cellular automata", Master Thesis, Computer Science Nijmegen, Summer 1996., ainsi que par Christoph Dürr, Huong LêThanh, et Miklos SanthaC. Dürr et M. Santha, "A decision procedure for unitary linear quantum cellular automata", quant-ph/9604007 .C. Dürr, H. LêTanh, M. Santha, "A decision procedure for well-formed linear quantum cellular automata", Rand. Struct. Algorithms 11, 1997 : pp. 381-394. Voir aussi cs.DS/9906024., Jozef GruskaJ. Gruska, "Quantum Computing", McGraw-Hill, Cambridge 1999 : Section 4.3. et Pablo ArrighiPablo Arrighi, An algebraic study of unitary one dimensional quantum cellular automata, Proceedings of MFCS 2006, LNCS 4162, (2006), pp122-133. Voir aussi quant-ph/0512040.
Cependant, on s'est rendu compte plus tard que cette définition était trop lâche, dans le sens où certaines instances de cette définition permettent une signalisation superluminale. Une deuxième vague de modèles comprend ceux de Susanne Richter et Reinhard WernerS. Richter et R.F. Werner, "Ergodicity of quantum cellular automata", J. Stat. Phys. 82, 1996 : pp. 963-998. Voir aussi cond-mat/9504001, de Benjamin Schumacher et Reinhard Werner, de Carlos Pérez-Delgado et Donny Cheung, et de Pablo Arrighi, Vincent Nesme et Reinhard Werner.
Ceux-ci sont tous étroitement liés et ne souffrent pas d'un tel problème de localité. En fin de compte, on peut dire qu'ils sont tous d'accord pour représenter les automates cellulaires quantiques comme un grand circuit quantique, se répétant à l'infini dans le temps et l'espace. Des études récentes sur le sujet sont disponibles iciP. Arrighi, An overview of quantum cellular automata, arXiv:1904.12956Terry Farrelly, A review of Quantum Cellular Automata arXiv:1904.13318.
Modèles de systèmes physiques Des modèles d'automates cellulaires quantiques ont été proposés par David MeyerD. Meyer, "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics 85, 1996 : pp. 551-574. Voir également quant-ph/9604003.D. Meyer, "On the absence of homogeneous scalar unitary cellular automata'", Physics Letters A 223, 1996 : pp. 337-340. Voir également quant-ph/9604011., Bruce Boghosian et Washington TaylorB. Boghosian and W. Taylor, "Quantum lattice-gas model for the many-particle Schrödinger equation in d dimensions", Physical Review E 57, 1998 : pp. 54-66., et Peter Love et Bruce BoghosianP. Love et B. Boghosian, "From Dirac to Diffusion : Decoherence in Quantum Lattice Gases", Quantum Information Processing 4, 2005, pp. 335-354. comme moyen de simuler des gaz de réseau quantique, motivés par l'utilisation d'automates cellulaires « classiques » pour modéliser des phénomènes physiques classiques tels que la dispersion des gazB. Chophard et M. Droz, "Cellular Automata modeling of Physical Systems", Cambridge University Press, 1998.. Les critères déterminant quand un automate cellulaire quantique (QCA) peut être décrit comme un automate à gaz à réseau quantique (QLGA) ont été donnés par Asif Shakeel et Peter Love.
Automates cellulaires à points quantiques Une proposition de mise en œuvre d'automates cellulaires « classiques » par des systèmes conçus avec des points quantiques a été proposée sous le nom d'« automates cellulaires quantiques » par Doug Tougaw et Craig LentP. Tougaw, C. Lent, "Logical devices implemented using quantum cellular automata", J. Appl. Phys. 75, 1994 : pp. 1818-1825, pour remplacer l'informatique classique en utilisant la technologie CMOS. Afin de mieux différencier cette proposition des modèles d'automates cellulaires qui effectuent des calculs quantiques, de nombreux auteurs travaillant sur ce sujet parlent désormais d'automates cellulaires à points quantiques.
Modèles de physique des particules De nombreux QCA (Automate Cellulaire Quantique) qui simulent les théories quantiques des champs dans la limite du continuum ont été conçus. Le plus simple est le QCA de Dirac qui, pour un faible momentum et une faible masse, se comporte comme une particule de Dirac. D'autres QCA simulant l'électrodynamique quantique ont également été construits. Cependant, ces modes posent encore quelques problèmes. Par exemple, il n'est pas clair comment définir un vide de Dirac libre dans ces modèles qui soit stable.
Notes et références
Voir aussi
Articles connexes Projet:Automate cellulaire Informatique quantique Automate quantique Automate probabiliste
Liens externes
Catégorie:Automates finis et langages réguliers Catégorie:Théorie de l'information quantique Catégorie:Informatique quantique