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.

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 quantiques^[1],[2], un circuit quantique^[3] ou simplement tous les autres automates cellulaires quantiques^[4],[5]).

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^[2]. Des résultats récents montrent que ces propriétés peuvent être dérivées axiomatiquement, à partir des symétries de l'évolution globale^[6],[7],[8].

En 1982, Richard Feynman a suggéré une première approche pour quantifier un modèle d'automates cellulaires^[9]. En 1985, David Deutsch a présenté un développement formel du sujet^[10]. 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 1988^[11], 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.

Le premier modèle formel d'automates cellulaires quantiques à avoir fait l'objet de recherches approfondies est celui introduit par John Watrous^[1]. Ce modèle a été développé par Wim van Dam^[12], ainsi que par Christoph Dürr, Huong LêThanh, et Miklos Santha^[13],[14], Jozef Gruska^[15] et Pablo Arrighi^[16].

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^[6],[7]. Une deuxième vague de modèles comprend ceux de Susanne Richter et Reinhard Werner^[17], de Benjamin Schumacher et Reinhard Werner^[6], de Carlos Pérez-Delgado et Donny Cheung^[2], et de Pablo Arrighi, Vincent Nesme et Reinhard Werner^[7],[8].

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 ici^[18],[19].

Des modèles d'automates cellulaires quantiques ont été proposés par David Meyer^[20],[21], Bruce Boghosian et Washington Taylor^[22], et Peter Love et Bruce Boghosian^[23] 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 gaz^[24]. 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^[25].

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 Lent^[26], 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.

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^[27]. D'autres QCA simulant l'électrodynamique quantique ont également été construits^[28]. 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^[29].

• Projet:Automate cellulaire
• Informatique quantique
• Automate quantique
• Automate probabiliste

• Portail de la logique
• Portail de l'informatique théorique
• Portail des sciences quantiques