Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Машины Тьюринга
Машина
Варианты
Наука

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

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

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

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

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

То есть классическая машина Тьюринга описывается семеркой .

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

  • Набор состояний заменяется гильбертовым пространством .
  • Символы ленточного алфавита аналогично заменяются гильбертовым пространством (обычно это гильбертово пространство, отличное от набора состояний).
  • Пустой символ соответствует нулевому вектору.
  • Входные и выходные символы обычно берутся как дискретный набор, как в классической системе; таким образом, ни вход, ни выход квантовой машины не должны быть самой квантовой системой.
  • Функция перехода является обобщением моноида перехода и понимается как набор унитарных матриц, которые являются автоморфизмами гильбертова пространства .
  • Начальное состояние может быть как смешанным, так и чистым .
  • Набор из конечных или допускающих состояний является подпространством гильбертова пространства .

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

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

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

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

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

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

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

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

  1. ↑ Эндрю Яо (1993). Сложность квантовой схемы . 34-й ежегодный симпозиум по основам информатики. С. 352–361.
  2. ↑ Абель Молина; Джон Уотроус (2018). «Возвращаясь к моделированию квантовых машин Тьюринга квантовыми схемами». arXiv : 1808.01701 [ cs.CC ].
  3. ^ Fortnow, Lance (2003). "Взгляд одного теоретика сложности квантовых вычислений". Теоретическая информатика . 292 (3): 597–610. arXiv : квант-ph / 0003035 . DOI : 10.1016 / S0304-3975 (01) 00377-2 .
  4. ^ a b Deutsch, Дэвид (июль 1985 г.). «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер» (PDF) . Труды Королевского общества А . 400 (1818): 97–117. Bibcode : 1985RSPSA.400 ... 97D . CiteSeerX 10.1.1.41.2382 . DOI : 10,1098 / rspa.1985.0070 . Архивировано из оригинального (PDF) 23 ноября 2008 года.  
  5. ^ Бениофф, Пол (1980). «Компьютер как физическая система: микроскопическая квантово-механическая гамильтонова модель компьютеров, представленная машинами Тьюринга». Журнал статистической физики . 22 (5): 563–591. Bibcode : 1980JSP .... 22..563B . DOI : 10.1007 / bf01011339 .
  6. Перейти ↑ Benioff, P. (1982). «Квантово-механические гамильтоновы модели машин Тьюринга». Журнал статистической физики . 29 (3): 515–546. Bibcode : 1982JSP .... 29..515B . DOI : 10.1007 / BF01342185 .
  7. ^ Саймон Пердрикс; Филипп Йорран (4 апреля 2007 г.). «Классически контролируемые квантовые вычисления». Математика. Struct. В комп. Наука . 16 (4): 601–620. arXiv : квант-ph / 0407008 . DOI : 10.1017 / S096012950600538X .также Саймон Пердрикс и Филипп Йорран (2006). «Классически контролируемые квантовые вычисления» (PDF) . Математика. Struct. В комп. Наука . 16 (4): 601–620. CiteSeerX 10.1.1.252.1823 . DOI : 10.1017 / S096012950600538X .  
  8. ^ Ааронсон, Скотт (2005). «Квантовые вычисления, поствыбор и вероятностное полиномиальное время». Труды Королевского общества А . 461 (2063): 3473–3482. arXiv : квант-ph / 0412187 . Bibcode : 2005RSPSA.461.3473A . DOI : 10.1098 / rspa.2005.1546 . Препринт доступен по адресу [1]

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

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

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

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