Sari la conținut

Automat celular cuantic

De la Wikipedia, enciclopedia liberă

Un automat celular cuantic (QCA) este un model abstract de calcul cuantic, conceput prin analogie cu modelele convenționale de automate celulare introduse de John von Neumann. Aceeași denumire se poate referi și la automate celulare cu puncte cuantice, care reprezintă o implementare fizică propusă pentru automate celulare "clasice" prin exploatarea fenomenelor mecanicii cuantice. QCA a atras o atenție deosebită datorită dimensiunii sale extrem de mici (la scară moleculară sau chiar atomică) și consumului său ultra-redus de energie, ceea ce îl face un candidat pentru înlocuirea tehnologiei CMOS.

Utilizarea termenului[modificare | modificare sursă]

În contextul modelelor de calcul sau al sistemelor fizice, automatul celular cuantic reprezintă fuziunea elementelor din (1) studiul automatelor celulare în informatica clasică și (2) studiul procesării informației cuantice. În particular, următoarele caracteristici definesc modelele de automate celulare cuantice:

  • Calculele se consideră a fi realizate prin operarea în paralel a unor dispozitive de calcul multiple, sau celule. Celulele sunt de obicei sisteme cuantice finite-dimensionale identice (de exemplu, fiecare celulă este un qubit).
  • Fiecare celulă are o vecinătate formată din alte celule. Toate acestea formează o rețea de celule, care de obicei este considerată regulată (de exemplu, celulele sunt aranjate ca o rețea cu sau fără condiții de frontieră periodice).
  • Evoluția tuturor celulelor prezintă o serie de simetrii de tip fizic. Localitatea este una dintre ele: starea următoare a unei celule depinde doar de starea curentă a acesteia și de starea vecinilor săi. Omogenitatea este o alta: evoluția acționează identic peste tot și este independentă de timp.
  • Spațiul de stare al celulelor și operațiile efectuate asupra lor ar trebui să fie motivate de principiile mecanicii cuantice.

O altă caracteristică adesea considerată importantă pentru un model de automat celular cuantic este aceea că ar trebui să fie universal pentru calculul cuantic (adică să poată simula eficient mașinile Turing cuantice,[1][2] un circuit cuantic arbitrar[3] sau pur și simplu toate celelalte automate celulare cuantice).[4][5]

Modelele propuse recent impun condiții suplimentare, de exemplu, automate celulare cuantice ar trebui să fie reversibile și/sau local unitare și să aibă o funcție de tranziție globală ușor de determinat din regula de actualizare a celulelor individuale.[2] Rezultatele recente arată că aceste proprietăți pot fi derivate axiomatic, din simetriile evoluției globale.[6][7][8]

Modele[modificare | modificare sursă]

Propuneri inițiale[modificare | modificare sursă]

În 1982, Richard Feynman a sugerat o primă abordare pentru cuantificarea unui model de automate celulare.[9] În 1985, David Deutsch⁠(d) a prezentat o dezvoltare formală a subiectului.[10] Ulterior, Gerhard Grössing și Anton Zeilinger au introdus termenul de "automate celulare cuantice" pentru a se referi la un model pe care l-au definit în 1988,[11] deși modelul lor avea foarte puține în comun cu conceptele dezvoltate de Deutsch și, prin urmare, nu a fost dezvoltat semnificativ ca model de calcul.

Modele de calcul cuantic universal[modificare | modificare sursă]

Primul model formal de automate celulare cuantice cercetat în profunzime a fost cel introdus de John Watrous.[1] Acest model a fost dezvoltat ulterior de Wim van Dam,[12] precum și de Christoph Dürr, Huong LêThanh, Miklos Santha,[13][14] Jozef Gruska[15] și Pablo Arrighi.[16] Totuși, ulterior s-a constatat că această definiție era prea laxă, în sensul că unele instanțe ale ei permiteau semnalizare superluminală (depășind viteza luminii).[6][7] Un al doilea val de modele include pe cele ale Susannei Richter și Reinhard Werner, [17] ale lui Benjamin Schumacher și Reinhard Werner,[6] ale lui Carlos Pérez-Delgado și Donny Cheung,[2] și ale lui Pablo Arrighi, Vincent Nesme și Reinhard Werner.[7][8] Toate acestea sunt strâns legate și nu suferă de nicio astfel de problemă de localitate. În cele din urmă, se poate spune că toate sunt de acord să imagineze automate celulare cuantice ca fiind doar un circuit cuantic mare, repetat la infinit în timp și spațiu. Recenzii recente ale subiectului sunt disponibile aici.[18][19]

Modele de sisteme fizice[modificare | modificare sursă]

Modele de automate celulare cuantice au fost propuse de David Meyer,[20] [21] Bruce Boghosian și Washington Taylor, [22] precum și Peter Love și Bruce Boghosian[23] ca o modalitate de a simula gazele cuantice pe rețele, motivate de utilizarea automatelor celulare „clasice” pentru a modela fenomene fizice clasice precum dispersia gazelor.[24] Criteriile care determină când un automat celular cuantic (QCA) poate fi descris ca automat celular cu gaz cuantic pe rețele (QLGA) au fost date de Asif Shakeel și Peter Love.[25]

Automate celulare cu puncte cuantice[modificare | modificare sursă]

O propunere pentru implementarea automatelor celulare clasice prin sisteme proiectate cu puncte cuantice a fost propusă sub numele de "automate celulare cuantice" de Doug Tougaw⁠(d) și Craig Lent,[26] ca înlocuitor pentru calculul clasic folosind tehnologia CMOS. Pentru a diferenția mai bine între această propunere și modelele de automate celulare care efectuează calcul cuantic, mulți autori care lucrează la acest subiect se referă acum la aceasta ca fiind un automat celular cu puncte cuantice.

Note[modificare | modificare sursă]

  1. ^ a b Watrous, John (), „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, doi:10.1109/SFCS.1995.492583, ISBN 0-8186-7183-1, MR 1619103 .
  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. ^ P. Arrighi, An overview of quantum cellular automata, arXiv:1904.12956
  19. ^ Terry Farrelly, A review of Quantum Cellular Automata arXiv:1904.13318
  20. ^ D. Meyer, "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics 85, 1996: pp. 551–574. See also quant-ph/9604003.
  21. ^ D. Meyer, "On the absence of homogeneous scalar unitary cellular automata'", Physics Letters A 223, 1996: pp. 337–340. See also quant-ph/9604011.
  22. ^ 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.
  23. ^ P. Love and B. Boghosian, "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases", Quantum Information Processing 4, 2005, pp. 335–354.
  24. ^ B. Chophard and M. Droz, "Cellular Automata modeling of Physical Systems", Cambridge University Press, 1998.
  25. ^ Shakeel, Asif; Love, Peter J. (). „When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)?”. Journal of Mathematical Physics. 54 (9): 092203. Bibcode:2013JMP....54i2203S. doi:10.1063/1.4821640. ISSN 0022-2488. 
  26. ^ P. Tougaw, C. Lent, "Logical devices implemented using quantum cellular automata", J. Appl. Phys. 75, 1994: pp. 1818–1825

Vezi și[modificare | modificare sursă]

Adus de la https://ro.wikipedia.org/w/index.php?title=Automat_celular_cuantic&oldid=16315798