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

Квантовая машина Тьюринга (англ. quantum Turing machine; иногда — универсальный квантовый компьютер) — абстрактная машина, используемая для моделирования квантового компьютера; простая модель, которая, в то же время, может описать любые квантовые вычисления: любой квантовый алгоритм может быть формально описан как некоторая квантовая машина Тьюринга. Впервые построена в 1985 году Дэвидом Дойчем, обратившим внимание на аналогию между квантовыми вентилями и логическими вентилями в цифровых схемах^[1] (в той же работе предложен тезис Чёрча — Тьюринга — Дойча).

Впоследствии бо́льшее распространение получила модель квантовых схем, вычислительно эквивалентная квантовой машине Тьюринга, но более удобная для исследовательских целей^[2].

ПримечанияПравить

↑ Deutsch, David. Quantum theory, the Church–Turing principle and the universal quantum computer (англ.) // Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences : journal. — 1985. — July (vol. 400, no. 1818). — P. 97—117. — doi:10.1098/rspa.1985.0070. Архивировано 9 марта 2016 года.
↑ Andrew Yao (1993). “Quantum circuit complexity”. Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352—361.

СсылкиПравить

История квантовых компьютеров. Архивная копия от 19 февраля 2020 на Wayback Machine

[Deutsch1985-1] Deutsch, David. Quantum theory, the Church–Turing principle and the universal quantum computer (англ.) // Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences : journal. — 1985. — July (vol. 400, no. 1818). — P. 97—117. — doi:10.1098/rspa.1985.0070. Архивировано 9 марта 2016 года.

[equivalence-2] Andrew Yao (1993). “Quantum circuit complexity”. Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352—361.

[1]

[2]