Квантовая машина Тьюринга
-
Основы квантовых машин Тьюринга
- Квантовая машина Тьюринга (QTM) — это абстрактная модель, которая описывает квантовые вычисления.
- QTM может быть связана с классическими и вероятностными машинами Тьюринга через матрицы переходов.
- Квантовые машины Тьюринга обобщают классические машины Тьюринга, заменяя классические состояния гильбертовым пространством и функцию перехода унитарными матрицами.
-
История и развитие
- Пол Бениофф описал квантово-механическую модель машин Тьюринга в 1980 и 1982 годах.
- Дэвид Дойч в 1985 году развил идею квантовых компьютеров, предполагая, что квантовые вентили функционируют аналогично цифровым логическим элементам.
- Ирияма, Охья и Волович разработали модель линейной квантовой машины Тьюринга, которая позволяет представлять квантовые измерения без классических результатов.
- Скотт Ааронсон показал, что класс сложности PostBQP равен классическому классу PP.
-
Рекомендации и дальнейшее чтение
- Статья предлагает дальнейшее чтение и внешние ссылки для углубления знаний о квантовых компьютерах.