Квантовая машина Тьюринга

Квантовая машина Тьюринга ( QTM ) или универсальный квантовый компьютер — это абстрактная машина, используемая для моделирования эффектов квантового компьютера . Он предоставляет простую модель, которая отражает всю мощь квантовых вычислений — то есть любой квантовый алгоритм может быть формально выражен как конкретная квантовая машина Тьюринга. Однако вычислительно эквивалентная квантовая схема является более распространенной моделью. ^[1]^[2]^: 2

Квантовые машины Тьюринга могут быть связаны с классическими и вероятностными машинами Тьюринга в рамках, основанных на матрицах переходов . То есть может быть указана матрица, произведение которой с матрицей, представляющей классическую или вероятностную машину, дает квантовую матрицу вероятности, представляющую квантовую машину. Это показал Лэнс Фортноу . ^[3]

Неофициальный скетч [ править ]

Нерешенная задача по физике :

Достаточно ли универсального квантового компьютера для эффективного моделирования произвольной физической системы?

(еще нерешенные задачи по физике)

Способ понимания квантовой машины Тьюринга (QTM) состоит в том, что она обобщает классическую машину Тьюринга (TM) таким же образом, как квантовый конечный автомат (QFA) обобщает детерминированный конечный автомат (DFA). По сути, внутренние состояния классической ТМ заменяются чистыми или смешанными состояниями в гильбертовом пространстве ; функция перехода заменяется набором унитарных матриц , которые отображают гильбертово пространство в себя. ^[4]

То есть классическая машина Тьюринга описывается семикортежностью . $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ .

Для квантовой машины Тьюринга с тремя лентами (одна лента содержит входные данные, вторая лента содержит промежуточные результаты вычислений и третья лента содержит выходные данные):

Набор состояний $Q$ заменяется гильбертовым пространством .
Символы алфавита ленты $\Gamma$ аналогичным образом заменяются гильбертовым пространством (обычно гильбертовым пространством, отличным от набора состояний).
Пустой символ $b\in \Gamma$ является элементом гильбертова пространства.
Входные и выходные символы $\Sigma$ обычно берутся в виде дискретного множества, как в классической системе; таким образом, ни входные, ни выходные данные квантовой машины не обязательно должны быть самой квантовой системой.
Функция перехода $\delta :\Sigma \times Q\otimes \Gamma \to \Sigma \times Q\otimes \Gamma \times \{L,R\}$ является обобщением переходного моноида и понимается как совокупность унитарных матриц , являющихся автоморфизмами гильбертова пространства. $Q$ .
Исходное состояние $q_{0}\in Q$ может быть либо смешанным , либо чистым состоянием .
Набор $F$ конечных принимающих или состояний является подпространством гильбертова пространства $Q$ .

Вышеприведенное представляет собой всего лишь набросок квантовой машины Тьюринга, а не ее формальное определение, поскольку оставляет неясными некоторые важные детали: например, как часто измерения выполняются ; см., например, разницу между QFA с однократным измерением и QFA с множественным измерением. Этот вопрос измерения влияет на способ определения записи на выходную ленту.

История [ править ]

В 1980 и 1982 годах физик Пол Бениофф опубликовал статьи. ^[5]^[6]который впервые описал квантовомеханическую модель машины Тьюринга . Статья 1985 года, написанная физиком Оксфордского университета Дэвидом Дойчем, развила идею квантовых компьютеров, предположив, что квантовые вентили могут функционировать аналогично традиционным двоичным логическим вентилям цифровых вычислений . ^[4]

Ирияма, Охья и Волович разработали модель линейной квантовой машины Тьюринга (LQTM). Это обобщение классической QTM, которая имеет смешанные состояния и допускает необратимые функции перехода. Они позволяют представлять квантовые измерения без классических результатов. ^[7]

Квантовая машина Тьюринга с постселекцией была определена Скоттом Ааронсоном , который показал, что класс полиномиального времени на такой машине ( PostBQP ) равен классическому классу сложности PP . ^[8]

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

Квантовый симулятор § Решение физических задач

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

^ Эндрю Яо (1993). Сложность квантовой схемы . 34-й ежегодный симпозиум по основам информатики. стр. 352–361.
^ Абель Молина; Джон Уотрус (2018). «Возвращаясь к моделированию квантовых машин Тьюринга с помощью квантовых схем» . Труды Королевского общества A: Математические, физические и технические науки . 475 (2226). arXiv : 1808.01701 . дои : 10.1098/rspa.2018.0767 . ПМК 6598068 . ПМИД 31293355 .
^ Фортнау, Лэнс (2003). «Взгляд одного теоретика сложности на квантовые вычисления». Теоретическая информатика . 292 (3): 597–610. arXiv : Quant-ph/0003035 . дои : 10.1016/S0304-3975(01)00377-2 . S2CID 18657540 .
^ Перейти обратно: ^а ^б Дойч, Дэвид (июль 1985 г.). «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер» (PDF) . Труды Королевского общества А. 400 (1818): 97–117. Бибкод : 1985РСПСА.400...97Д . CiteSeerX 10.1.1.41.2382 . дои : 10.1098/rspa.1985.0070 . S2CID 1438116 . Архивировано из оригинала (PDF) 23 ноября 2008 г.
^ Бениофф, Пол (1980). «Компьютер как физическая система: микроскопическая квантовомеханическая гамильтонова модель компьютеров, представленная машинами Тьюринга». Журнал статистической физики . 22 (5): 563–591. Бибкод : 1980JSP....22..563B . дои : 10.1007/bf01011339 . S2CID 122949592 .
^ Бениофф, П. (1982). «Квантово-механические гамильтоновы модели машин Тьюринга». Журнал статистической физики . 29 (3): 515–546. Бибкод : 1982JSP....29..515B . дои : 10.1007/BF01342185 . S2CID 14956017 .
^ Саймон Пердрикс; Филипп Жорран (4 апреля 2007 г.). «Классические управляемые квантовые вычисления». Математика. Структура. В Комп. Наука . 16 (4): 601–620. arXiv : Quant-ph/0407008 . дои : 10.1017/S096012950600538X . S2CID 16142327 . Также: Саймон Пердрикс и Филипп Жорран (2006). «Квантовые вычисления с классическим управлением» (PDF) . Математика. Структура. В Комп. Наука . 16 (4): 601–620. arXiv : Quant-ph/0407008 . CiteSeerX 10.1.1.252.1823 . дои : 10.1017/S096012950600538X . S2CID 16142327 .
^ Ааронсон, Скотт (2005). «Квантовые вычисления, постселекция и вероятностное полиномиальное время». Труды Королевского общества А. 461 (2063): 3473–3482. arXiv : Quant-ph/0412187 . Бибкод : 2005RSPSA.461.3473A . дои : 10.1098/rspa.2005.1546 . S2CID 1770389 . Препринт доступен по адресу [1] .

Дальнейшее чтение [ править ]

Молина, Абель; Уотрус, Джон (2018). «Возвращаясь к моделированию квантовых машин Тьюринга с помощью квантовых схем» . Труды Королевского общества A: Математические, физические и технические науки . 475 (2226). arXiv : 1808.01701 . дои : 10.1098/rspa.2018.0767 . ПМК 6598068 . ПМИД 31293355 .
Ирияма, Сатоши; Ойя, Масанори; Волович, Игорь (2004). «Обобщенная квантовая машина Тьюринга и ее применение к алгоритму хаоса SAT». arXiv : Quant-ph/0405191 .
Дойч, Д. (1985). «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер». Труды Лондонского королевского общества. Серия А, Математические и физические науки . 400 (1818): 97–117. Бибкод : 1985РСПСА.400...97Д . CiteSeerX 10.1.1.41.2382 . дои : 10.1098/rspa.1985.0070 . JSTOR 2397601 . S2CID 1438116 .

Внешние ссылки [ править ]

Квантовый компьютер – история

[equivalence-1] Эндрю Яо (1993). Сложность квантовой схемы . 34-й ежегодный симпозиум по основам информатики. стр. 352–361.

[newequivalence-2] Абель Молина; Джон Уотрус (2018). «Возвращаясь к моделированию квантовых машин Тьюринга с помощью квантовых схем» . Труды Королевского общества A: Математические, физические и технические науки . 475 (2226). arXiv : 1808.01701 . дои : 10.1098/rspa.2018.0767 . ПМК 6598068 . ПМИД 31293355 .

[transition-3] Фортнау, Лэнс (2003). «Взгляд одного теоретика сложности на квантовые вычисления». Теоретическая информатика . 292 (3): 597–610. arXiv : Quant-ph/0003035 . дои : 10.1016/S0304-3975(01)00377-2 . S2CID 18657540 .

[Deutsch1985-4] Перейти обратно: ^а ^б Дойч, Дэвид (июль 1985 г.). «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер» (PDF) . Труды Королевского общества А. 400 (1818): 97–117. Бибкод : 1985РСПСА.400...97Д . CiteSeerX 10.1.1.41.2382 . дои : 10.1098/rspa.1985.0070 . S2CID 1438116 . Архивировано из оригинала (PDF) 23 ноября 2008 г.

[5] Бениофф, Пол (1980). «Компьютер как физическая система: микроскопическая квантовомеханическая гамильтонова модель компьютеров, представленная машинами Тьюринга». Журнал статистической физики . 22 (5): 563–591. Бибкод : 1980JSP....22..563B . дои : 10.1007/bf01011339 . S2CID 122949592 .

[6] Бениофф, П. (1982). «Квантово-механические гамильтоновы модели машин Тьюринга». Журнал статистической физики . 29 (3): 515–546. Бибкод : 1982JSP....29..515B . дои : 10.1007/BF01342185 . S2CID 14956017 .

[7] Саймон Пердрикс; Филипп Жорран (4 апреля 2007 г.). «Классические управляемые квантовые вычисления». Математика. Структура. В Комп. Наука . 16 (4): 601–620. arXiv : Quant-ph/0407008 . дои : 10.1017/S096012950600538X . S2CID 16142327 . Также: Саймон Пердрикс и Филипп Жорран (2006). «Квантовые вычисления с классическим управлением» (PDF) . Математика. Структура. В Комп. Наука . 16 (4): 601–620. arXiv : Quant-ph/0407008 . CiteSeerX 10.1.1.252.1823 . дои : 10.1017/S096012950600538X . S2CID 16142327 .

[8] Ааронсон, Скотт (2005). «Квантовые вычисления, постселекция и вероятностное полиномиальное время». Труды Королевского общества А. 461 (2063): 3473–3482. arXiv : Quant-ph/0412187 . Бибкод : 2005RSPSA.461.3473A . дои : 10.1098/rspa.2005.1546 . S2CID 1770389 . Препринт доступен по адресу [1] .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]