Autómata celular cuántico

Un autómata celular cuántico, o ACC, es un modelo abstracto de la computación cuántica, ideado en analogía de los modelos convencionales de la autómata celular introducidos por von Neumann. Este nombre también puede referirse a la autómata celular de puntos cuánticos, que son una implementación física propuesta de los autómatas celulares "clásicos", explotando los fenómenos de la mecánica cuántica. Las ACC han atraído mucha atención a consecuencia de su característico tamaño (a escala molecular o incluso atómica) y su consumo ultra bajo de energía, por lo que es uno de los candidatos para la sustitución de la tecnología CMOS.

Uso del término

En el contexto de los modelos computacionales o en el de los sistemas físicos, el autómata celular cuántica se refiere a la fusión de dos elementos (1) el estudio del autómata celular en las ciencias computacionales y (2) el estudio del procesamiento de información cuántica. En particular, las siguientes son características de los modelos de un autómata celular cuántica:

  • El cálculo se obtiene por la operación en paralelo de múltiples dispositivos informáticos, o células. Las células, generalmente, son tomadas para ser sistemas cuánticos idénticos de dimensión finita (por ejemplo, cada célula es un qubit).
  • Cada célula tiene una vecindad de otras células. Juntas forman una red de células, que se consideran como regular (por ejemplo, las células se acomodan como una rejilla con, o sin, condiciones periódicas de contorno).
  • La evolución de todas las células tiene una serie de simetrías físicas. La localidad es una: el siguiente estado de una célula depende de su estado actual y el de sus vecinas. La homogeneidad es otra: la evolución actúa de la misma forma sobre todas las células, es independiente del tiempo.
  • El estado espacial de las células y las operaciones que se realizan en ellas, deben estar motivadas por los principios de la mecánica cuántica.

Otra característica que a menudo es considerada importante para un modelo de la autómata celular cuántico es que debe ser universal para la computación cuántica es decir, que pueda simular de manera eficiente a las máquinas de Turing cuánticas,[1]​[2]​ algún circuito cuántico arbitrario[3]​ o simplemente, todos los otros autómatas celulares cuánticos.[4]​[5]​

Los modelos propuestos recientemente imponen otras condiciones, por ejemplo, qué los autómatas celulares cuánticos deben ser reversibles y/o localmente unitarias, que tengan una función de transición global fácil de determinar a partir de la regla de actualización de células individuales.[2]​ Resultados recientes muestran que estas propiedades se pueden derivar axiomáticamente, a partir de las simetrías de la evolución global.[6]​[7]​[8]​

Modelos de ACC

Primeras propuestas

En 1982, Richard Feynman sugirió una primera aproximación a la cuantificación de un modelo de autómatas celulares.[9]​ En 1985, David Deutsch presentó un desarrollo formal sobre el tema.[10]​ Más tarde, Gerhard Grössing y Anton Zeilinger introdujeron el término "autómatas celulares cuánticos" para referirse a un modelo que definieron en 1988,[11]​ aunque su modelo tenía muy poco en común con los conceptos desarrollados por Deutsch por lo que no se ha desarrollado de manera significativa como un modelo de cálculo.

Modelos de la computación cuántica universal

El primer modelo formal de autómatas celulares cuánticos para ser investigado en profundidad fue introducido por John Watrous.[1]​ Este modelo fue desarrollado por Wim van Dam,[12]​ así como Christoph Dürr, Huong LêThanh, y Miklos Santha,[13]​[14]​ Jozef Gruska.[15]​ y Pablo Arrighi.[16]​ Sin embargo, fue después cuando se dieron cuenta de que esta definición era demasiado floja, en el sentido de que algunos casos permitían señalización súper lumínica.[6]​[7]​ Una segunda ola de modelos incluye las de Susanne Richter y Reinhard Werner,[17]​ de Benjamin Schumacher y Reinhard Werner,[6]​ de Carlos Pérez Delgado y Donny Cheung,[2]​ y de Pablo Arrighi, Vincent Nesme y Reinhard Werner.[7]​[8]​ Estas están estrechamente relacionadas y no sufren de ninguna cuestión de localidad. Al final se puede decir que todos están de acuerdo a la imagen de los autómatas celulares cuánticos como solo un gran circuito cuántico, infinito y repitiéndose a través del tiempo y el espacio.

Modelos de sistemas físicos

Modelos de autómatas celulares cuánticos han sido propuestos por David Meyer,[18]​[19]​ Bruce Boghosian y Washington Taylor,[20]​ y Peter Love junto con Bruce Boghosian[21]​ como un medio para simular rejillas cuánticas de gases, motivadas por el uso de autómatas celulares “clásicos” para la modelación de fenómenos físicos clásicos tales como la dispersión de gases.[22]​

Autómata celular de puntos cuánticos

Una propuesta para la implementación clásica de autómatas celulares por sistemas diseñados con puntos cuánticos se ha propuesto con el nombre de "autómatas celulares de puntos cuánticos" por Doug Tougaw y Craig Lent,[23]​ como un reemplazo de la computación clásica utilizando la tecnología CMOS. Con el fin de poder diferenciar mejor entre esta propuesta y modelos de autómatas celulares que realizan computación cuántica, muchos autores que trabajan sobre este tema ahora se refieren a esto como un autómata celular de puntos cuánticos.

Véase también

Referencias

  1. ↑ a b Watrous, John (1995), «On one-dimensional quantum cellular automata», Proc. 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995), Los Alamitos, CA: IEEE Comput. Soc. Press, pp. 528-537, MR 1619103, doi:10.1109/SFCS.1995.492583 ..
  2. ↑ a b c C. Pérez-Delgado and D. Cheung, "Local Unitary Quantum Cellular Automata", Phys. Rev. A 76, 032320, 2007. See also arXiv:0709.0006 (quant-ph)
  3. ↑ D.J. Shepherd, T. Franz, R.F. Werner: Universally programmable Quantum Cellular Automaton. Phys. Rev. Lett. 97, 020502 (2006)
  4. ↑ P. 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). See also (quant-ph)
  5. ↑ P. Arrighi, J. Grattage, A quantum Game of Life, Proceedings of JAC 2010, Turku, December 2010. TUCS Lecture Notes 13, 31-42, (2010). See also (quant-ph) and (Companion Website)
  6. ↑ a b c B. Schumacher and R. Werner, "Reversible quantum cellular automata", quant-ph/0405174
  7. ↑ a b c Pablo Arrighi, Vincent Nesme, Reinhard Werner, One-dimensional quantum cellular automata over finite, unbounded configurations. See also (quant-ph)
  8. ↑ a b Pablo Arrighi, Vincent Nesme, Reinhard Werner, N-dimensional quantum cellular automata. See also (quant-ph)
  9. ↑ R. Feynman, "Simulating physics with computers", Int. J. Theor. Phys. 21, 1982: pp. 467–488.
  10. ↑ D. 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.
  11. ↑ G. Grossing and A. Zeilinger, "Quantum cellular automata", Complex Systems 2 (2), 1988: pp. 197–208 and 611–623.
  12. ↑ W. van Dam, "Quantum cellular automata", Master Thesis, Computer Science Nijmegen, Summer 1996.
  13. ↑ C. Dürr and M. Santha, "A decision procedure for unitary linear quantum cellular automata", quant-ph/9604007 .
  14. ↑ 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. See also cs.DS/9906024.
  15. ↑ J. Gruska, "Quantum Computing", McGraw-Hill, Cambridge 1999: Section 4.3.
  16. ↑ Pablo Arrighi, An algebraic study of unitary one dimensional quantum cellular automata, Proceedings of MFCS 2006, LNCS 4162, (2006), pp122-133. See also quant-ph/0512040
  17. ↑ S. Richter and R.F. Werner, "Ergodicity of quantum cellular automata", J. Stat. Phys. 82, 1996: pp. 963–998. See also cond-mat/9504001
  18. ↑ D. Meyer, "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics 85, 1996: pp. 551–574. See also quant-ph/9604003.
  19. ↑ D. Meyer, "On the absence of homogeneous scalar unitary cellular automata'", Physics Letters A 223, 1996: pp. 337–340. See also quant-ph/9604011.
  20. ↑ B. 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.
  21. ↑ P. Love and B. Boghosian, "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases", Quantum Information Processing 4, 2005, pp. 335–354.
  22. ↑ B. Chophard and M. Droz, "Cellular Automata modeling of Physical Systems", Cambridge University Press, 1998.
  23. ↑ P. Tougaw, C. Lent, "Logical devices implemented using quantum cellular automata", J. Appl. Phys. 75, 1994: pp. 1818–1825