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

14

Пусть для квантовой машины Тьюринга (QTM) набор состояний равен , а алфавит символов - = { 0 , 1 } , которые появляются на головке ленты. Тогда, как я понимаю, в любой момент времени, когда QTM вычисляет, кубит, который появляется в его голове, будет содержать произвольный вектор V = a | 1 + б | 0 . Также, если | д 0, | д 1, . , , QQΣзнак равно{0,1}ВΣзнак равноa|1+б|0|Q0,|Q1,,,,Qтогда вектором состояния в этом случае также будет произвольный вектор ,ВQзнак равноб0|Q0+б1|Q1+,,,

Теперь, после завершения цикла инструкций, векторы и V q будут решать, будет ли QTM перемещаться влево или вправо вдоль ленты Qubit. Мой вопрос: поскольку гильбертово пространство, образованное Q ∑, является несчетным бесконечным множеством, а { Left, Right } является дискретным множеством, сопоставление между ними будет трудно создать.ВΣВQQΣ{Лево право}

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

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

Прем Кумар
источник
Посмотрите, поможет ли это. Как QTM рассчитывает
Пират Х
@PirateX Я читал этот пост, но я не понимаю, является ли внутреннее состояние QTM классической сущностью или Квантом. Может ли это идти в суперпозиции различных внутренних состояний? Кроме того, может ли QTM перемещаться влево и вправо по ленте памяти одновременно? Q
Прем Кумар

Ответы:

7

QΣзнак равно{0,1}a|0+б|1Q

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

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

(Q,σ)

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

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

Джон Уотроус
источник
1
@Premkumar: В качестве сноски к этому ответу --- если вы ищете авторитетную ссылку для этого отчета о QTM, то хорошим местом для рассмотрения будет оригинальная работа Бернштейна и Вазирани «Квантовая теория сложности» (Proc. 25th Annual ACM STOC (стр. 1411–1473), 1997 [ссылка на бесплатный PDF на citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.7852 ]. Почти все вышеприведенные замечания Джона по существу являются расширением определения 3.2. в этой статье, и некоторые обсуждения в том же разделе
Ниль де Бодрап
@Niel: Я не уверен, что вы можете редактировать комментарий, но, как я уверен, вы знаете, что версия конференции Бернштейна и Вазирани появилась в 1993 году, а не в 1997 году. Журнальная версия 1997 года появилась в SIAM Journal of Computing (в действительно монументальный специальный выпуск по квантовым вычислениям).
Джон Уотроус
Правда, и даже бесплатная PDF-ссылка описывает 1993 год; Кажется, я кое-что пересек. (Комментарии можно редактировать до 10 минут.)
Niel de Beaudrap
@NieldeBeaudrap Небольшая коррекция: до 5 минут :) (для обычных пользователей). Моды могут редактировать комментарии в любое время.
Санчайан Датта
4

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

пирамиды
источник