Квантовый клеточный автомат
Квантовый клеточный автомат ( ККА ) — это абстрактная модель квантовых вычислений , разработанная по аналогии с традиционными моделями клеточных автоматов, введенными Джоном фон Нейманом . Это же имя может также относиться к клеточным автоматам с квантовыми точками , которые представляют собой предлагаемую физическую реализацию «классических» клеточных автоматов, использующую квантово-механические явления. QCA привлек много внимания благодаря своему чрезвычайно маленькому размеру (на молекулярном или даже атомном уровне) и сверхнизкому энергопотреблению, что делает его одним из кандидатов на замену технологии КМОП .
Использование термина [ править ]
В контексте моделей вычислений или физических систем квантовый клеточный автомат относится к слиянию элементов как (1) изучения клеточных автоматов в традиционной информатике , так и (2) изучения квантовой обработки информации . В частности, особенностями моделей квантовых клеточных автоматов являются:
- Считается, что вычисления происходят в результате параллельной работы нескольких вычислительных устройств или ячеек . Ячейки обычно считаются идентичными конечномерными квантовыми системами (например, каждая ячейка представляет собой кубит ).
- Каждая ячейка имеет окрестности других ячеек. В совокупности они образуют сеть ячеек, которую обычно считают регулярной (например, ячейки расположены в виде решетки с периодическими граничными условиями или без них).
- Эволюция всех клеток имеет ряд физических симметрий. Локальность одна: следующее состояние клетки зависит только от ее текущего состояния и состояния ее соседей. Другое дело — однородность: эволюция везде происходит одинаково и не зависит от времени.
- Пространство состояний ячеек и операции, выполняемые над ними, должны быть мотивированы принципами квантовой механики.
Другая особенность, которую часто считают важной для модели квантовых клеточных автоматов, заключается в том, что она должна быть универсальной для квантовых вычислений (т. е. она может эффективно моделировать квантовые машины Тьюринга ). [1] [2] какая-то произвольная квантовая схема [3] или просто все другие квантовые клеточные автоматы [4] [5] ).
Модели, которые были предложены недавно, налагают дополнительные условия, например, что квантовые клеточные автоматы должны быть обратимыми и/или локально унитарными и иметь легко определяемую глобальную функцию перехода из правила обновления отдельных ячеек. [2] Недавние результаты показывают, что эти свойства могут быть выведены аксиоматически из симметрии глобальной эволюции. [6] [7] [8]
Модели [ править ]
Ранние предложения
В 1982 году Ричард Фейнман предложил первоначальный подход к квантованию модели клеточных автоматов. [9] В 1985 году Дэвид Дойч представил формальное развитие этой темы. [10] Позже Герхард Грёссинг и Антон Цайлингер ввели термин «квантовые клеточные автоматы» для обозначения модели, которую они определили в 1988 году. [11] хотя их модель имела очень мало общего с концепциями, разработанными Дойчем, и поэтому не получила значительного развития как модель вычислений.
Модели универсальных квантовых вычислений [ править ]
Первой формальной моделью квантовых клеточных автоматов, которая подверглась глубокому исследованию, была модель, предложенная Джоном Уотрусом . [1] Эта модель была развита Вимом ван Дамом. [12] а также Кристоф Дюрр, Хуонг ЛеТхань и Миклош Санта, [13] [14] Йозеф Грушка. [15] и Пабло Арриги. [16] Однако позже выяснилось, что это определение было слишком расплывчатым в том смысле, что некоторые его случаи допускают сверхсветовую передачу сигналов. [6] [7] Вторая волна моделей включает модели Сюзанны Рихтер и Райнхарда Вернера. [17] Бенджамина Шумахера и Райнхарда Вернера, [6] Карлоса Переса-Дельгадо и Донни Ченга, [2] и Пабло Арриги, Винсента Несме и Райнхарда Вернера. [7] [8] Все они тесно связаны между собой и не страдают от каких-либо проблем с локальностью. В конце концов, можно сказать, что все они согласны представлять квантовые клеточные автоматы как некую большую квантовую схему, бесконечно повторяющуюся во времени и пространстве. Последние обзоры по теме доступны здесь. [18] [19]
Модели физических систем [ править ]
Модели квантовых клеточных автоматов были предложены Дэвидом Мейером. [20] [21] Брюс Богосян и Вашингтон Тейлор, [22] и Питер Лав и Брюс Богосян [23] как средство моделирования квантовых решеточных газов, мотивированное использованием «классических» клеточных автоматов для моделирования классических физических явлений, таких как дисперсия газа. [24] Критерии, определяющие, когда квантовый клеточный автомат (QCA) может быть описан как квантовый решеточный газовый автомат (QLGA), были даны Асифом Шакилом и Питером Лавом. [25]
Клеточные автоматы квантовых на точках
Предложение по реализации классических клеточных автоматов с помощью систем, созданных с использованием квантовых точек , было предложено под названием «квантовые клеточные автоматы» Дугом Туго и Крейгом Лентом. [26] как замена классическим вычислениям с использованием технологии КМОП. Чтобы лучше отличать это предложение от моделей клеточных автоматов, выполняющих квантовые вычисления, многие авторы, работающие над этой темой, теперь называют это клеточным автоматом с квантовыми точками .
См. также [ править ]
- Квантовые конечные автоматы - квантовый аналог вероятностных автоматов.
- Квантовый эффект Холла - Электромагнитный эффект в физике
Ссылки [ править ]
- ^ Jump up to: а б Уотрус, Джон (1995), «Об одномерных квантовых клеточных автоматах», Proc. 36-й ежегодный симпозиум по основам информатики (Милуоки, Висконсин, 1995) , Лос-Аламитос, Калифорния: IEEE Comput. Соц. Press, стр. 528–537, doi : 10.1109/SFCS.1995.492583 , ISBN. 0-8186-7183-1 , МР 1619103 , S2CID 7441203 .
- ^ Jump up to: а б с К. Перес-Дельгадо и Д. Чунг, «Локальные унитарные квантово-клеточные автоматы», Физ. Rev. A 76, 032320, 2007. См. также arXiv:0709.0006 (quant-ph).
- ^ DJ Шеперд, Т. Франц, РФ Вернер: Универсально программируемый квантовый клеточный автомат. Физ. Преподобный Летт. 97, 020502 (2006)
- ^ П. Арриги, Р. Фарджеттон, З. Ван, По своей сути универсальные одномерные квантовые клеточные автоматы в двух вариантах, Fundamenta Informaticae Vol.91, No.2, стр. 197-230, (2009). См. также (квант-ph)
- ^ П. Арриги, Дж. Граттаж, Квантовая игра жизни, Труды JAC 2010, Турку, декабрь 2010 г. Примечания к лекциям TUCS 13, 31-42, (2010). См. также (quant-ph) и (сопутствующий веб-сайт).
- ^ Jump up to: а б с Б. Шумахер и Р. Вернер, «Обратимые квантовые клеточные автоматы», quant-ph/0405174.
- ^ Jump up to: а б с Пабло Арриги, Винсент Несме, Рейнхард Вернер, Одномерные квантовые клеточные автоматы над конечными неограниченными конфигурациями. См. также (квант-ph)
- ^ Jump up to: а б Пабло Арриги, Винсент Несме, Рейнхард Вернер, N-мерные квантовые клеточные автоматы. См. также (квант-ph)
- ^ Р. Фейнман, «Моделирование физики с помощью компьютеров», Int. Дж. Теория. Физ. 21 , 1982: стр. 467–488.
- ^ Д. Дойч, «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер», Труды Лондонского королевского общества A 400 (1985), стр. 97–117.
- ^ Г. Гроссинг и А. Цайлингер, «Квантовые клеточные автоматы», Complex Systems 2 (2), 1988: стр. 197–208 и 611–623.
- ^ В. ван Дам, «Квантовые клеточные автоматы», магистерская диссертация, информатика, Неймеген, лето 1996 г.
- ^ К. Дюрр и М. Санта, «Процедура принятия решения для унитарных линейных квантовых клеточных автоматов», quant-ph/9604007 .
- ^ К. Дюрр, Х. ЛеТан, М. Санта, «Процедура принятия решения для правильно сформированных линейных квантовых клеточных автоматов», Rand. Структура. Алгоритмы 11, 1997: стр. 381–394. См. также cs.DS/9906024 .
- ^ Дж. Груска, «Квантовые вычисления», McGraw-Hill, Кембридж, 1999: Раздел 4.3.
- ^ Пабло Арриги, Алгебраическое исследование унитарных одномерных квантовых клеточных автоматов, Труды MFCS 2006, LNCS 4162, (2006), стр. 122-133. См. также quant-ph/0512040.
- ^ С. Рихтер и Р. Ф. Вернер, «Эргодичность квантовых клеточных автоматов», J. Stat. Физ. 82, 1996: стр. 963–998. См. также cond-mat/9504001.
- ^ П. Арриги, Обзор квантовых клеточных автоматов, arXiv:1904.12956.
- ^ Терри Фаррелли, Обзор квантовых клеточных автоматов arXiv: 1904.13318
- ^ Д. Мейер, «От квантовых клеточных автоматов к квантовым решеточным газам», Журнал статистической физики 85, 1996: стр. 551–574. См. также quant-ph/9604003 .
- ^ Д. Мейер, «Об отсутствии однородных скалярных унитарных клеточных автоматов», Physics Letters A 223, 1996: стр. 337–340. См. также quant-ph/9604011 .
- ^ Б. Богосян и В. Тейлор, «Квантовая модель решеточного газа для многочастичного уравнения Шредингера в d-мерности», Physical Review E 57, 1998: стр. 54–66.
- ^ П. Лав и Б. Богосян, «От Дирака к диффузии: декогеренция в газах квантовой решетки», Quantum Information Processing 4, 2005, стр. 335–354.
- ^ Б. Чопард и М. Дроз, «Моделирование физических систем клеточными автоматами», Cambridge University Press, 1998.
- ^ Шакил, Асиф; С любовью, Питер Дж. (01 сентября 2013 г.). «Когда квантовый клеточный автомат (QCA) является квантовым решеточным газовым автоматом (QLGA)?». Журнал математической физики . 54 (9): 092203. arXiv : 1209.5367 . Бибкод : 2013JMP....54i2203S . дои : 10.1063/1.4821640 . ISSN 0022-2488 . S2CID 2351651 .
- ^ П. Туго, К. Лент, «Логические устройства, реализованные с использованием квантовых клеточных автоматов», J. Appl. Физ. 75, 1994: стр. 1818–1825.
