Квантова машина Тюрінга
З Вікіпедії, безкоштовно encyclopedia
Квантова машина Тюрінга (іноді універсальний квантовий комп'ютер) — абстрактна машина, що використовується для моделювання квантового комп'ютера. Вона являє собою просту модель, що вбирає в себе всю потужність квантових обчислень. Будь-який квантовий алгоритм може бути представлений як частковий випадок квантової машини Тюрінга. Подібні машини Тюрінга вперше описав Девід Дойч в своїй статті 1985 року[1], де він припустив, що квантові вентилі можуть функціонувати так само, як і класичні бінарні логічні елементи.
Чи здатний універсальний квантовий комп'ютер ефективно моделювати довільну фізичну систему? |
Квантові машини Тюрінга не завжди використовуються для аналізу квантових обчислень. Більш поширеною моделлю є квантова схема, яка з обчислювальної точки зору еквівалентна до квантової машини Тюрінга[2].
Квантову машину Тюрінга можна зв'язати з класичною та ймовірнісною машинами Тюрінга за допомогою конструкції на основі матриць переходів, як показав Ленс Фортнов[3].
В 2003 році Іріяма, Ойя та Волович запропонували модель лінійної квантової машини Тюрінга, яка є узагальненням звичайної квантової машини Тюрінга, яка містить мішані стани й дозволяє необоротні функції переходів[4]. Це дозволяє представляти квантові вимірювання без класичних результатів[5].
Квантова машина Тюрінга з подальшим вибором була запропонована Скоттом Ааронсоном, який показав, що клас складності з поліноміальним часом (клас PostBQP) на такій машині еквівалентний до класичного класу складності PP[6].