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

Модель квантовых вычислений

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

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

Неформальный набросок

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

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

(еще нерешенные проблемы по физике)

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

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

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

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

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

История

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

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

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

Смотрите также

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

Ссылки

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

Дальнейшее чтение

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

Внешние ссылки

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