Квантова машина Тюрінга
| Чи здатний універсальний квантовий комп'ютер ефективно моделювати довільну фізичну систему? |
Квантова машина Тюрінга (іноді універсальний квантовий комп'ютер) — абстрактна машина, що використовується для моделювання квантового комп'ютера. Вона являє собою просту модель, що вбирає в себе всю потужність квантових обчислень. Будь-який квантовий алгоритм може бути представлений як частковий випадок квантової машини Тюрінга. Подібні машини Тюрінга вперше описав Девід Дойч в своїй статті 1985 року[1], де він припустив, що квантові вентилі можуть функціонувати так само, як і класичні бінарні логічні елементи.
Квантові машини Тюрінга не завжди використовуються для аналізу квантових обчислень. Більш поширеною моделлю є квантова схема, яка з обчислювального погляду еквівалентна до квантової машини Тюрінга[2].
Квантову машину Тюрінга можна зв'язати з класичною та ймовірнісною машинами Тюрінга за допомогою конструкції на основі матриць переходів, як показав Ленс Фортнов[3].
В 2003 році Іріяма, Ойя та Волович запропонували модель лінійної квантової машини Тюрінга, яка є узагальненням звичайної квантової машини Тюрінга, яка містить мішані стани й дозволяє необоротні функції переходів[4]. Це дозволяє представляти квантові вимірювання без класичних результатів[5].
Квантову машину Тюрінга з подальшим вибором запропонував Скотт Ааронсон, який показав, що клас складності з поліноміальним часом (клас PostBQP) на такій машині еквівалентний до класичного класу складності PP[6].
- ↑ Deutsch D. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer // Proc. R. Soc. Lond A. — 1985. — Т. 400. — С. 97-117. (рос. переклад: Дойч Д. Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер // Квантовый компьютер и квантовые вычисления (том 2). — Ижевск : РХД, 1999. — 288 с.)
- ↑ Yao A. Quantum circuit complexity // Proceedings of the 34th Annual Symposium on Foundations of Computer Science. — 1993. — С. 352-361.
- ↑ Fortnow L. One Complexity Theorist's View of Quantum Computing // Theoretical Computer Science. — 2003. — Т. 292, вип. 3. — С. 597-610.
- ↑ Iriyama S., Ohya M., Volovich I. Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm // Quantum Information and Computing. University of Waseda, Tokyo, Japan, 29 – 31 October 2003. — World Scientific, 2006. (arXiv: quant-ph/0405191 [Архівовано 16 Січня 2019 у Wayback Machine.])
- ↑ Perdrix S., Jorrand P. Classically-Controlled Quantum Computation // Math. Struct. In Comp. Science. — 2006. — Т. 16, вип. 4. — С. 601-620. (arXiv:quant-ph/0407008 [Архівовано 6 Серпня 2020 у Wayback Machine.])
- ↑ Aaronson S. Quantum computing, postselection, and probabilistic polynomial-time // Proceedings of the Royal Society A. — 2005. — Т. 461, вип. 2063. — С. 3473-3482. (arXiv:quant-ph/0412187 [Архівовано 28 Квітня 2019 у Wayback Machine.])