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

Нерозв'язані проблеми фізики
Чи здатний універсальний квантовий комп'ютер ефективно моделювати довільну фізичну систему?

Квантова машина Тюрінга (іноді універсальний квантовий комп'ютер) — абстрактна машина, що використовується для моделювання квантового комп'ютера. Вона являє собою просту модель, що вбирає в себе всю потужність квантових обчислень. Будь-який квантовий алгоритм може бути представлений як частковий випадок квантової машини Тюрінга. Подібні машини Тюрінга вперше описав Девід Дойч в своїй статті 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.])

Див. також

[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 [Архівовано 16 Січня 2019 у Wayback Machine.])

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

[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 [Архівовано 28 Квітня 2019 у Wayback Machine.])

[1]

[2]

[3]

[4]

[5]

[6]

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

Виноски

Див. також

Portal di Ensiklopedia Dunia