Квантовая машина Тьюринга - Quantum Turing machine

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

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

Неформальный эскиз

Нерешенная проблема в физике: Это универсальный квантовый компьютер достаточно, чтобы эффективно моделировать произвольная физическая система? (больше нерешенных задач по физике)

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

То есть классическая машина Тьюринга описывается 7-кортеж ${\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 \rightarrow \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). «Возвращаясь к моделированию квантовых машин Тьюринга квантовыми схемами». arXiv:1808.01701 [cs.CC ].
3. Фортноу, Лэнс (2003). "Взгляд одного теоретика сложности квантовых вычислений". Теоретическая информатика. 292 (3): 597–610. arXiv:Quant-ph / 0003035. Дои:10.1016 / S0304-3975 (01) 00377-2.
4. Дойч, Дэвид (Июль 1985 г.). «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер» (PDF). Труды Королевского общества А. 400 (1818): 97–117. Bibcode:1985RSPSA.400 ... 97D. CiteSeerX  10.1.1.41.2382. Дои:10.1098 / RSPA.1985.0070. Архивировано из оригинал (PDF) 23 ноября 2008 г.
5. Бениофф, Пол (1980). «Компьютер как физическая система: микроскопическая квантово-механическая гамильтонова модель компьютеров, представленная машинами Тьюринга». Журнал статистической физики. 22 (5): 563–591. Bibcode:1980JSP .... 22..563B. Дои:10.1007 / bf01011339.
6. Бениофф, П. (1982). «Квантово-механические гамильтоновы модели машин Тьюринга». Журнал статистической физики. 29 (3): 515–546. Bibcode:1982JSP .... 29..515B. Дои:10.1007 / BF01342185.
7. Саймон Пердрикс; Филипп Йорран (4 апреля 2007 г.). «Классически контролируемые квантовые вычисления». Математика. Struct. В комп. Наука. 16 (4): 601–620. arXiv:Quant-ph / 0407008. Дои:10.1017 / S096012950600538X. также Саймон Пердрикс и Филипп Йорран (2006). «Классически контролируемые квантовые вычисления» (PDF). Математика. Struct. В комп. Наука. 16 (4): 601–620. CiteSeerX  10.1.1.252.1823. Дои:10.1017 / S096012950600538X.
8. Ааронсон, Скотт (2005). «Квантовые вычисления, поствыбор и вероятностное полиномиальное время». Труды Королевского общества А. 461 (2063): 3473–3482. arXiv:Quant-ph / 0412187. Bibcode:2005RSPSA.461.3473A. Дои:10.1098 / rspa.2005.1546. Препринт доступен на [1]

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

• Молина, Абель; Уотроус, Джон (2018). «Возвращаясь к моделированию квантовых машин Тьюринга квантовыми схемами». arXiv:1808.01701 [cs.CC ].
• Ирияма, Сатоши; Охя, Масанори; Волович, Игорь (2004). «Обобщенная квантовая машина Тьюринга и ее применение к алгоритму SAT Chaos». arXiv:Quant-ph / 0405191.
• Дойч, Д. (1985). «Квантовая теория, принцип Черча-Тьюринга и универсальный квантовый компьютер». Труды Лондонского королевского общества. Серия A, Математические и физические науки. 400 (1818): 97–117. Bibcode:1985RSPSA.400 ... 97D. CiteSeerX  10.1.1.41.2382. Дои:10.1098 / RSPA.1985.0070. JSTOR  2397601.

внешняя ссылка

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