В квантовой машине Тьюринга как принимается решение перемещаться по ленте памяти?

Пусть для квантовой машины Тьюринга (QTM) набор состояний равен , а алфавит символов - ∑ = { 0 , 1 } , которые появляются на головке ленты. Тогда, как я понимаю, в любой момент времени, когда QTM вычисляет, кубит, который появляется в его голове, будет содержать произвольный вектор V ∑ = a | 1 ⟩ + б | 0 ⟩ . Также, если | д 0 ⟩ , | д 1 ⟩ , . , , ∈ $Q$$\sum=\{0,1\}$$V_\sum = a|1\rangle+b|0\rangle$$|q_0\rangle , |q_1\rangle, ... \in Q$тогда вектором состояния в этом случае также будет произвольный вектор ,$V_q=b_0|q_0\rangle + b_1 |q_1\rangle+ ...$

Теперь, после завершения цикла инструкций, векторы и V q будут решать, будет ли QTM перемещаться влево или вправо вдоль ленты Qubit. Мой вопрос: поскольку гильбертово пространство, образованное Q ⊗ ∑, является несчетным бесконечным множеством, а { Left, Right } является дискретным множеством, сопоставление между ними будет трудно создать.$V_\sum$$V_q$$Q \otimes \sum$$\{\text{Left,Right}\}$

Итак, как принимается решение двигаться влево или вправо? Двигаться ли QTM слева и справа , в то же время, это означает , что множество также образует другое гильбертово пространство, и , следовательно , движение QTM становится чем - то вроде | Левый ⟩ + б | Право ⟩ .$\{\text{Left,Right}\}$$a|\text{Left}\rangle+b|\text{Right}\rangle$

Или, как и в случае классической машины Тьюринга, QTM перемещается влево или вправо, но не одновременно в одно и то же время?

$Q$$\Sigma = \{0,1\}$$a|0\rangle + b|1\rangle$$Q$

В качестве аналогии мы не будем описывать глобальное состояние вероятностной машины Тьюринга, независимо указав распределение для внутреннего состояния и для каждого из квадратов ленты. Скорее, мы должны описать все вместе, чтобы правильно представить корреляции между различными частями машины. Например, биты, хранящиеся в двух удаленных квадратах ленты, могут быть идеально коррелированы, оба равны 0 с вероятностью 1/2 и оба равны 1 с вероятностью 1/2.

Итак, в квантовом случае, и если предположить, что мы говорим о чистых состояниях квантовых машин Тьюринга с унитарными эволюциями (в отличие от более общей модели, основанной на смешанных состояниях), глобальное состояние представляется вектором, элементы которого индексируются конфигурации (т. е. классические описания внутреннего состояния, расположения головки ленты и содержимого каждого квадрата ленты) машины Тьюринга. Следует отметить, что мы обычно предполагаем, что в алфавите ленты есть специальный пустой символ (который может быть равен 0, если мы хотим, чтобы в наших квадратах на ленте хранились кубиты), и что мы начинаем вычисления с не более чем конечным числом квадратов, не являющихся пустыми, так что набор всех достижимых конфигураций исчисляется. Это означает, что состояние будет представлено единичным вектором в сепарабельном гильбертовом пространстве.

$(q,\sigma)$

$Q = \{0,1\}$$\Sigma = \{0,1\}$(и мы возьмем 0, чтобы быть пустым символом). Мы начинаем в состоянии 0, сканируя квадрат, в котором хранится 1, а все остальные квадраты хранят 0. Я не буду явно записывать функцию перехода, а просто опишу поведение словами. При каждом перемещении содержимое отсканированного квадрата ленты интерпретируется как управляющий бит для операции Адамара во внутреннем состоянии. После выполнения контролируемого Адамара голова перемещается влево, если (новое) состояние равно 0, и перемещается вправо, если (новое) состояние равно 1. (В этом примере мы фактически никогда не меняем содержимое ленты.) После одного шага QTM будет находиться в одинаково взвешенной суперпозиции между нахождением в состоянии 0 с квадратом сканирования головки ленты -1 и нахождением в состоянии 1 с квадратом сканирования головки ленты +1. На всех последующих ходах контролируемый Адамар ничего не делает, потому что каждый квадрат, кроме квадрата 0, содержит символ 0. Таким образом, головка ленты будет продолжать двигаться одновременно влево и вправо, как частица, движущаяся налево и направо в суперпозиции.

Если бы вы хотели, вы, конечно, могли бы определить вариант модели квантовой машины Тьюринга, для которого местоположение и движение головки ленты является детерминированным, и это не разрушило бы вычислительную универсальность модели, но "классическое" определение квантовой ленты Тьюринга машины не накладывают это ограничение.

Квантовая машина Тьюринга может перейти в суперпозицию движения влево и вправо. Это отличается от классической машины Тьюринга, которая может двигаться только влево или вправо.