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

Квантова машина Тюрінга (іноді універсальний квантовий комп'ютер) — абстрактна машина, що використовується для моделювання квантового комп'ютера. Вона являє собою просту модель, що вбирає в себе всю потужність квантових обчислень. Будь-який квантовий алгоритм може бути представлений як частковий випадок квантової машини Тюрінга. Подібні машини Тюрінга вперше описав Девід Дойч в своїй статті 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)
Perdrix S., Jorrand P. Classically-Controlled Quantum Computation // Math. Struct. In Comp. Science. — 2006. — Т. 16, вип. 4. — С. 601-620. (arXiv:quant-ph/0407008)
Aaronson S. Quantum computing, postselection, and probabilistic polynomial-time // Proceedings of the Royal Society A. — 2005. — Т. 461, вип. 2063. — С. 3473-3482. (arXiv:quant-ph/0412187)

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 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 с.)

[2] Yao A. Quantum circuit complexity // Proceedings of the 34th Annual Symposium on Foundations of Computer Science. — 1993. — С. 352-361.

[3] Fortnow L. One Complexity Theorist's View of Quantum Computing // Theoretical Computer Science. — 2003. — Т. 292, вип. 3. — С. 597-610.

[4] 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)

[5] Perdrix S., Jorrand P. Classically-Controlled Quantum Computation // Math. Struct. In Comp. Science. — 2006. — Т. 16, вип. 4. — С. 601-620. (arXiv:quant-ph/0407008)

[6] Aaronson S. Quantum computing, postselection, and probabilistic polynomial-time // Proceedings of the Royal Society A. — 2005. — Т. 461, вип. 2063. — С. 3473-3482. (arXiv:quant-ph/0412187)