Д. Дойч, Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер.
По причине унитарности динамика
, как динамика любой квантовой системы, необходимо обратима. С другой стороны, машины Тьюринга совершают необратимые изменения в процессе вычислений и до недавнего времени действительно был широко распространен взгляд, согласно которому необратимость — существенная черта вычисления.
Тем не менее, Беннетт (1973) доказал, что это не так, явно построив обратимую классическую модель вычислительной машины, эквивалентную (т. е. порождающую те же вычислимые функции)
(см. так-же Тоффоли (Toffoli), 1979). (Машины Бенёва эквивалентны машинам Беннетта, но используют квантовую динамику.)
Квантовые компьютеры
![$\mathcal{Q}[U^+, U^-]$](https://dxdy-03.korotkov.co.uk/f/a/3/d/a3d19a58c3b0695ed1fc24e07191383282.png "$\mathcal{Q}[U^+, U^-]$")
, эквивалентные любой обратимой машине Тьюринга, можно получить, приняв
![$$U^\pm(n', m'|n, m) =\frac{1}{2}\delta^{A(n,m)}{n'} \delta^{B(n,m)}{m'}[1 \pm C(n, m)] , (2.8)$$](https://dxdy-02.korotkov.co.uk/f/5/e/a/5eac9d60c38fbd60f8828bd3e45abbc082.png "$$U^\pm(n', m'|n, m) =\frac{1}{2}\delta^{A(n,m)}{n'} \delta^{B(n,m)}{m'}[1 \pm C(n, m)] , (2.8)$$")
где
,
,
— функции со значениями
,
и
, соответственно. Другими словами, машины Тьюринга — это те квантовые компьютеры, динамика которых обеспечивает то, что они остаются в основных вычислительных состояниях в конце каждого шага, если они стартуют в основном состоянии. Чтобы обеспечить унитарность, необходимо и достаточно, чтобы отображение
было бы биективно. Поскольку составляющие функции
,
,
в остальном произвольны, должны, в частности, существовать варианты, которые делают
эквивалентным универсальной машине Тьюринга
.
, то можно сделать "копию" 
, но нельзя "настоящую копию" 
. То есть разница в запутанности.
