+Нерозв'язані проблеми фізики Чи здатний універсальний квантовий комп'ютер ефективно моделювати довільну фізичну систему?
Квантова машина Тюрінга (іноді універсальний квантовий комп'ютер) — абстрактна машина, що використовується для моделювання квантового комп'ютера. Вона являє собою просту модель, що вбирає в себе всю потужність квантових обчислень. Будь-який квантовий алгоритм може бути представлений як частковий випадок квантової машини Тюрінга. Подібні машини Тюрінга вперше описав Девід Дойч в своїй статті 1985 року (рос. переклад: ), де він припустив, що квантові вентилі можуть функціонувати так само, як і класичні бінарні логічні елементи.
Квантові машини Тюрінга не завжди використовуються для аналізу квантових обчислень. Більш поширеною моделлю є квантова схема, яка з обчислювального погляду еквівалентна до квантової машини Тюрінга.
Квантову машину Тюрінга можна зв'язати з класичною та ймовірнісною машинами Тюрінга за допомогою конструкції на основі матриць переходів, як показав Ленс Фортнов.
В 2003 році Іріяма, Ойя та Волович запропонували модель лінійної квантової машини Тюрінга, яка є узагальненням звичайної квантової машини Тюрінга, яка містить мішані стани й дозволяє необоротні функції переходів (arXiv: quant-ph/0405191 ). Це дозволяє представляти квантові вимірювання без класичних результатів (arXiv:quant-ph/0407008 ).
Квантову машину Тюрінга з подальшим вибором запропонував Скотт Ааронсон, який показав, що клас складності з поліноміальним часом (клас PostBQP) на такій машині еквівалентний до класичного класу складності PP (arXiv:quant-ph/0412187 ).
Виноски
Див. також Задача Фейнмана Квантовий комп'ютер Машина Тюрінга