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

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

Квантовая машина Тьюринга (англ. Quantum Turing machine; иногда — универсальный квантовый компьютер) — абстрактная машина, используемая для моделирования квантового компьютера. Представляет собой простую модель, которая, в то же время, может описать любые квантовые вычисления. Любой квантовый алгоритм может быть формально описан как некоторая квантовая машина Тьюринга. Впервые подобные модели были предложены в 1985 году в работе Дэвида Дойча (Oxford University)[1]

В настоящее время КМТ используются не очень часто, модель quantum circuit, вычислительно эквивалентная КМТ[2], используется чаще.

Примечания[править | править вики-текст]

  1. Deutsch, David (July 1985). «Quantum theory, the Church-Turing principle and the universal quantum computer». Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences 400 (1818): pp. 97–117. DOI:10.1098/rspa.1985.0070.
  2. Andrew Yao (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science: 352–361. 

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