Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Квантовый клеточный автомат ( КК ) представляет собой абстрактная модель квантовых вычислений , разработанных по аналогии с обычными моделями клеточных автоматов , введенных Джоном фон Нейманом . Это же название может также относиться к клеточным автоматам с квантовыми точками , которые являются предлагаемой физической реализацией «классических» клеточных автоматов, использующей квантово-механические явления. QCA привлек большое внимание из-за чрезвычайно небольшого размера элемента (в молекулярном или даже атомном масштабе) и сверхнизкого энергопотребления, что делает его одним из кандидатов на замену технологии CMOS .

Использование термина [ править ]

В контексте моделей вычислений или физических систем квантовый клеточный автомат относится к слиянию элементов как (1) изучения клеточных автоматов в традиционной информатике, так и (2) изучения квантовой обработки информации . В частности, следующие особенности моделей квантовых клеточных автоматов:

  • Считается, что вычисление происходит в результате параллельной работы нескольких вычислительных устройств или ячеек . Ячейки обычно считаются идентичными конечномерными квантовыми системами (например, каждая ячейка является кубитом ).
  • Каждая ячейка соседствует с другими ячейками. Все вместе они образуют сеть ячеек, которая обычно считается регулярной (например, ячейки расположены в виде решетки с периодическими граничными условиями или без них).
  • Эволюция всех ячеек имеет ряд симметрий, подобных физике. Локальность одна: следующее состояние ячейки зависит только от ее текущего состояния и состояния соседей. Другое дело - однородность: эволюция везде одинакова и не зависит от времени.
  • Пространство состояний ячеек и выполняемые над ними операции должны быть мотивированы принципами квантовой механики.

Еще одна особенность , которая часто считается важным для модели квантового клеточного автомата является то , что она должна быть универсальной для квантовых вычислений (то есть , что она может эффективно моделировать квантовые машины Тьюринга , [1] [2] некоторая произвольная квантовая схема [3] или просто все другие квантовые клеточные автоматы [4] [5] ).

Недавно предложенные модели накладывают дополнительные условия, например, что квантовые клеточные автоматы должны быть обратимыми и / или локально унитарными и иметь легко определяемую глобальную функцию перехода из правила обновления отдельных ячеек. [2] Недавние результаты показывают, что эти свойства могут быть аксиоматически выведены из симметрий глобальной эволюции. [6] [7] [8]

Модели [ править ]

Ранние предложения [ править ]

В 1982 году Ричард Фейнман предложил первоначальный подход к квантованию модели клеточных автоматов. [9] В 1985 году Дэвид Дойч представил формальное развитие предмета. [10] Позже Герхард Грёссинг и Антон Цайлингер ввели термин «квантовые клеточные автоматы» для обозначения модели, которую они определили в 1988 г. [11], хотя их модель имела очень мало общего с концепциями, разработанными Deutsch, и поэтому не использовалась. значительно развит как модель вычислений.

Модели универсальных квантовых вычислений [ править ]

Первой формальной моделью квантовых клеточных автоматов, подвергшейся глубокому исследованию, была модель, представленная Джоном Уотроусом . [1] Эта модель была развита Вимом ван Дамом [12], а также Кристофом Дюрром, Хуонгом ЛеТханом и Миклошом Сантой [13] [14] Йозефом Груска. [15] и Пабло Арриги. [16] Однако позже выяснилось, что это определение было слишком расплывчатым в том смысле, что некоторые его экземпляры допускают сверхсветовую передачу сигналов. [6] [7] Вторая волна моделей включает модели Сюзанны Рихтер и Рейнхарда Вернера, [17] Бенджамина Шумахера и Райнхарда Вернера, [6]Карлос Перес-Дельгадо и Донни Чунг, [2] и Пабло Арриги, Винсент Несме и Райнхард Вернер. [7] [8] Все они тесно связаны и не страдают подобными проблемами с местонахождением. В конце концов, можно сказать, что все они согласны представить квантовые клеточные автоматы как некую большую квантовую цепь, бесконечно повторяющуюся во времени и пространстве.

Модели физических систем [ править ]

Модели квантовых клеточных автоматов были предложены Дэвидом Мейером [18] [19] Брюсом Богосяном и Вашингтоном Тейлором [20], а также Питером Лавом и Брюсом Богозианом [21] в качестве средства моделирования квантовых решеточных газов, мотивированных использованием «классические» клеточные автоматы для моделирования классических физических явлений, таких как газовая дисперсия. [22] Критерии, определяющие, когда квантовый клеточный автомат (QCA) может быть описан как квантовый газовый автомат (QLGA), были даны Асифом Шакилом и Питером Лавом. [23]

Клеточные автоматы с квантовыми точками [ править ]

Предложение по реализации классических клеточных автоматов с помощью систем, разработанных с использованием квантовых точек , было предложено под названием «квантовые клеточные автоматы» Дугом Тугоу и Крейгом Лентом [24] в качестве замены классических вычислений с использованием технологии CMOS. Чтобы лучше различать это предложение и модели клеточных автоматов, которые выполняют квантовые вычисления, многие авторы, работающие над этой темой, теперь называют это клеточным автоматом с квантовыми точками .


См. Также [ править ]

  • Квантовые конечные автоматы
  • Квантовый эффект Холла  - квантово-механическая версия эффекта Холла

Ссылки [ править ]

  1. ^ a b Уотрус, Джон (1995), "Об одномерных квантовых клеточных автоматах", Proc. 36-й ежегодный симпозиум по основам компьютерных наук (Милуоки, Висконсин, 1995 г.) , Лос-Аламитос, Калифорния: IEEE Comput. Soc. . Пресс, стр 528-537, DOI : 10,1109 / SFCS.1995.492583 , MR  1619103 , S2CID  7441203.
  2. ^ a b c C. Pérez-Delgado и D. Cheung, "Local Unitary Quantum Cellular Automata", Phys. Rev. A 76, 032320, 2007. См. Также arXiv: 0709.0006 (Quant-ph)
  3. ^ DJ Shepherd, T. Franz, RF Werner: универсально программируемый квантовый клеточный автомат. Phys. Rev. Lett. 97, 020502 (2006)
  4. ^ П. Арриги, Р. Фаргеттон, З. Ван, Внутренне универсальные одномерные квантовые клеточные автоматы двух видов, Fundamenta Informaticae Vol.91, No. 2, pp.197-230, (2009). Также (Quant-ph)
  5. ^ П. Арриги, Дж. Граттэдж, Квантовая игра в жизнь, Труды JAC 2010, Турку, декабрь 2010 г. Примечания к лекциям TUCS 13, 31-42, (2010). См. Также (Quant-ph) и (Сопутствующий веб-сайт)
  6. ^ a b c Б. Шумахер и Р. Вернер, «Обратимые квантовые клеточные автоматы», Quant-ph / 0405174
  7. ^ a b c Пабло Арриги, Винсент Несме, Рейнхард Вернер, Одномерные квантовые клеточные автоматы над конечными неограниченными конфигурациями. Также (Quant-ph)
  8. ^ a b Пабло Арриги, Винсент Несме, Рейнхард Вернер, N-мерные квантовые клеточные автоматы. Также (Quant-ph)
  9. ^ Р. Фейнман, "Моделирование физики с помощью компьютеров", Int. J. Theor. Phys. 21 , 1982: стр. 467–488.
  10. ^ Д. Дойч, "Квантовая теория, принцип Черча-Тьюринга и универсальный квантовый компьютер" Труды Лондонского королевского общества A 400 (1985), стр. 97–117.
  11. ^ Г. Гроссинг и А. Цайлингер, "Квантовые клеточные автоматы", Комплексные системы 2 (2), 1988: стр. 197–208 и 611–623.
  12. ^ В. ван Дам, "Квантовые клеточные автоматы", магистерская диссертация, компьютерные науки, Неймеген, лето 1996 г.
  13. ^ C. Dürr и M. Santha, "Процедура принятия решения для унитарных линейных квантовых клеточных автоматов", Quant-ph / 9604007 .
  14. ^ C. Dürr, H. LêTanh, M. Santha, "Процедура принятия решения для правильно сформированных линейных квантовых клеточных автоматов", Rand. Struct. Алгоритмы 11, 1997: стр. 381–394. См. Также cs.DS / 9906024 .
  15. ^ Дж. Груска, «Квантовые вычисления», McGraw-Hill, Cambridge 1999: раздел 4.3.
  16. ^ Пабло Арриги, Алгебраическое исследование унитарных одномерных квантовых клеточных автоматов, Proceedings of MFCS 2006, LNCS 4162, (2006), pp122-133. См. Также Quant-ph / 0512040
  17. ^ С. Рихтер и Р.Ф. Вернер, "Эргодичность квантовых клеточных автоматов", J. Stat. Phys. 82, 1996: стр. 963–998. Также cond-mat / 9504001
  18. ^ Д. Мейер, «От квантовых клеточных автоматов к квантовым решеточным газам», журнал статистической физики 85, 1996: стр. 551–574. См. Также Quant-ph / 9604003 .
  19. ^ Д. Мейер, "Об отсутствии однородных скалярных унитарных клеточных автоматов", Physics Letters A 223, 1996: стр. 337–340. См. Также Quant-ph / 9604011 .
  20. ^ B. Boghosian и W. Taylor, "Квантовая модель решеточного газа для многочастичного уравнения Шредингера в d-измерениях", Physical Review E 57, 1998: стр. 54–66.
  21. ^ П. Лав и Б. Богосян, "От Дирака к диффузии: декогеренция в квантовых решеточных газах", квантовая обработка информации 4, 2005, стр. 335–354.
  22. ^ Б. Чопар и М. Дроз, "Моделирование физических систем клеточными автоматами", Cambridge University Press, 1998.
  23. ^ Шакил, Асиф; С любовью, Питер Дж. (01.09.2013). «Когда квантовый клеточный автомат (QCA) является квантовым газовым автоматом на решетке (QLGA)?». Журнал математической физики . 54 (9): 092203. arXiv : 1209.5367 . Bibcode : 2013JMP .... 54i2203S . DOI : 10.1063 / 1.4821640 . ISSN 0022-2488 . S2CID 2351651 .  
  24. ^ P. Tougaw, C. Lent, "Логические устройства, реализованные с использованием квантовых клеточных автоматов", J. Appl. Phys. 75, 1994: с. 1818–1825.