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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Нерозв'язані проблеми фізики
Чи здатний універсальний квантовий комп'ютер ефективно моделювати довільну фізичну систему?

Квантова машина Тюрінга (іноді універсальний квантовий комп'ютер) — абстрактна машина, що використовується для моделювання квантового комп'ютера. Вона являє собою просту модель, що вбирає в себе всю потужність квантових обчислень. Будь-який квантовий алгоритм може бути представлений як частковий випадок квантової машини Тюрінга. Подібні машини Тюрінга вперше описав Девід Дойч в своїй статті 1985 року[1], де він припустив, що квантові вентилі можуть функціонувати так само, як і класичні бінарні логічні елементи.

Квантові машини Тюрінга не завжди використовуються для аналізу квантових обчислень. Більш поширеною моделлю є квантова схема, яка з обчислювальної точки зору еквівалентна до квантової машини Тюрінга[2].

Квантову машину Тюрінга можно зв'язати з класичною та ймовірнісною машинами Тюрінга за допомогою конструкції на основі матриць переходів, як показав Ленс Фортнов[3].

В 2003 році Іріяма, Ойя та Волович запропонували модель лінійної квантової машини Тюрінга, яка є узагальненням звичайної квантової машини Тюрінга, яка містить мішані стани й дозволяє необоротні функціїї переходів[4]. Це дозволяє представляти квантові вимірювання без класичних результатів[5].

Квантова машина Тюрінга з подальшим вибором була запропонована Скоттом Ааронсоном, який показав, що клас складності з поліноміальним часом (клас PostBQP) на такій машині еквівалентний до класичного класу складності PP[6].

Виноски[ред.ред. код]

  1. Deutsch D. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer // Proc. R. Soc. Lond A. — 400 (1985) С. 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. — 292 (2003) (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. — 16 (2006) (4) С. 601-620. (arXiv:quant-ph/0407008)
  6. Aaronson S. Quantum computing, postselection, and probabilistic polynomial-time // Proceedings of the Royal Society A. — 461 (2005) (2063) С. 3473-3482. (arXiv:quant-ph/0412187)

Див. також[ред.ред. код]