Введение
Модель квантовых вычислений Квантовая машина Тьюринга (QTM) или универсальный квантовый компьютер - это абстрактная машина, используемая для моделирования эффектов квантового компьютера. Она предоставляет простую модель, которая охватывает всю мощь квантовых вычислений, то есть любой квантовый алгоритм может быть формально выражен как конкретная квантовая машина Тьюринга. Однако, вычислительно эквивалентная квантовая схема является более распространенной моделью. Квантовые машины Тьюринга могут быть связаны с классическими и вероятностными машинами Тьюринга в рамках, основанных на матрицах перехода. То есть, может быть указана матрица, продукт которой с матрицей, представляющей классическую или вероятностную машину, дает квантовую вероятностную матрицу, представляющую квантовую машину. Это показал Лэнс Фортноу.
A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model. Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices. That is, a matrix can be specified whose product with the matrix representing a classical or probabilistic machine provides the quantum probability matrix representing the quantum machine. This was shown by Lance Fortnow.
Неофициальный эскиз
Способ понимания квантовой машины Тьюринга (QTM) заключается в том, что она обобщает классическую машину Тьюринга (TM) таким же образом, как квантовый конечный автомат (QFA) обобщает детерминированный конечный автомат (DFA). По сути, внутренние состояния классического ТМ заменяются чистыми или смешанными состояниями в гильбертовом пространстве; функция перехода заменяется коллекцией унитарных матриц, которые отображают гильбертовое пространство к себе. который впервые описал квантовую механическую модель машин Тьюринга. В статье 1985 года, написанной физиком Оксфордского университета Дэвидом Дойчем, была развита идея квантовых компьютеров, предполагая, что квантовые ворота могут функционировать аналогично традиционным цифровым вычислительным двоичным логическим воротам. Ирияма, Оя и Волович разработали модель линейной квантовой машины Тьюринга (LQTM). Это обобщение классического QTM, который имеет смешанные состояния и который позволяет необратимым переходным функциям. Они позволяют представлять квантовые измерения без классических результатов. Квантовая машина Тьюринга с постселекцией была определена Скотом Ааронсоном, который показал, что класс полиномиального времени на такой машине (PostBQP) равен классическому классу сложности PP.