Я проходил дискуссию по вопросу, как определить квантовые машины Тьюринга? и я чувствую, что квантовая ТМ и недетерминированная ТМ - это одно и то же. Ответы на другой вопрос не касаются этого. Являются ли эти две модели одинаковыми?
Если нет,
- Каковы различия между квантовой ТМ и НДТМ?
- Существуют ли какие-либо вычисления, которые NDTM будет выполнять быстрее, чем Quantum TM?
- Если это так, то квант TM - это DTM, тогда почему в этой технологии столько шума, у нас уже так много DTM. Зачем разрабатывать новый DTM?
Ответы:
Как общая преамбула, QTM, TM и NTM - это разные вещи (принимая огромные свободы с кучей невысказанных предположений).
Я предполагаю, что вы знаете, что такое машина Тьюринга.
недетерминированный, не все. Вероятно, ключевые отличия высокого уровня между QTM и TM состоят в том, что QTM имеет в качестве своего состояния линейную комбинацию базовых состояний (опять же, это все в этом другом потоке) и что он вероятностный, то есть точность его вывода ограничен некоторой вероятностью меньше (в широком смысле). Просто чтобы быть по-настоящему ясным по вопросу, который привлекает многих людей, недетерминизм - это не случайность, это не параллелизм, это теоретическая конструкция, которая не имеет ничего общего ни с одним из них.
Сказав, что, если мы говорим свободно и лениво отождествляем QTM с квантовыми компьютерами и TM со стандартными компьютерами, то (опять же при определенных допущениях сложности) кажется, что квантовые компьютеры могут быстро выполнять определенные задачи, которые кажутся сложными для стандартных компьютеров (факторинг, дискретные журналы) , действительно определенный тип поиска и несколько других). Однако эти проблемы не известны вН П
Опять же, просто чтобы быть действительно ясным, я здесь упущен из-за большой вычислительной сложности, если вы действительно хотите понять, как все сочетается друг с другом, вам нужно начать изучать литературу.
источник
О значении недетерминизма
Здесь есть два разных значения «недетерминизма». Квантовая механика обычно описывается как «недетерминированная», но слово «недетерминированный» используется в теоретической информатике специальным образом.
Одно значение, которое применимо к квантовой механике, просто «не детерминировано ». Обычно это разумный способ интерпретации слова, и на самом деле ни квантовые машины Тьюринга, ни даже вероятностные машины Тьюринга не являются детерминированными в том, как они решают задачи решения.
Однако при описании моделей вычислений недетерминированный используется специально для обозначения того, что машина может (в некотором смысле) делать выбор, который не определяется ее состоянием или входом, для достижения конкретной цели. Это значение используется в других местах при описании моделей вычислений, таких как недетерминированные конечные автоматы .
Итак, квантовые машины Тьюринга - это модель вычислений, которая не является детерминированной, но отличается от « недетерминированной машины Тьюринга ».
Недетерминированные машины Тьюринга
Недетерминированная машина Тьюринга - это машина, которая может исследовать множество возможных переходов. Переход, который он делает на данном шаге, зависит, но не определяется, состоянием, в котором он находится, и символом, который он читает. Есть два способа, которыми это обычно представлено:
Специально для целей определения класса сложности NP можно описать машину как делающую выбор (или предположения) на каждом шаге, чтобы попытаться достичь принимающего состояния. Если вы думаете о том, что делает недетерминированная машина, как об исследовании дерева решений, она ищет приемлемый путь в дереве. Хотя нет описанного механизма, который бы подсказывал, как найти такой путь, мы представляем, что он найдет приемлемый путь, даже если он существует.
Также довольно часто говорят, что недетерминированная машина исследует все возможные пути в дереве решений параллельно и дает ответ «да», если какой-либо из них оказывается приемлемым путем.
Более современные методы недетерминизма также учитывают не только существование, но и количество принимающих путей; и это хорошо подходит для описания параллельного изучения всех путей. Мы можем наложить дополнительные ограничения, например, что все вычислительные пути имеют одинаковую длину (что машине всегда требуется одинаковое количество времени для выполнения вычислений) и что каждый путь выполняет предположение на каждом шаге или на каждом втором шаге, даже если предположение не используется. Если мы сделаем это, мы сможем сформулировать вероятностные модели вычислений, такие как случайные машины Тьюринга (классы мотивирующей сложности, такие как BPP ), в терминах числапринятия путей недетерминированной машины Тьюринга. Мы также можем перевернуть это и описать недетерминированные машины Тьюринга в терминах рандомизированных компьютеров, которые могут каким-то образом отличать результаты с нулевой вероятностью от тех, которые имеют ненулевую вероятность.
Квантовые машины Тьюринга
Основное различие между квантовой машиной Тьюринга и недетерминированной заключается в следующем: вместо недетерминированного «выбора» одного перехода из двух или более на каждом шаге, квантовая машина Тьюринга осуществляет переход в суперпозицию одного или нескольких возможных переходов. Полное состояние машины определяется как единичный вектор в сложном векторном пространстве, определяемый линейными комбинациями базовых состояний, описываемых классическими состояниями ленты, положением головки машины и «внутренним состоянием» головки машины. , (См., Например, стр. 9, определение 3.2.2, квантовой теории сложностидля полного описания того, как квантовые машины Тьюринга совершают переходы.) Условие, при котором квантовая машина Тьюринга принимает входные данные, также является более ограничительным и по своей природе включает в себя вероятность, требующую существенной вероятности наблюдения правильного результата для достижения успеха.
В результате квантовые машины Тьюринга отличаются от недетерминированных машин тем, что способы их переходов не являются полностью неопределенными. Даже если переход «кажется загадочным», это также эволюция того же рода со временем, что, как указывает наша лучшая теория материи, происходит в реальном мире. Хотя обычно квантовые компьютеры описывают как «параллельное исследование различных вычислительных путей», это делать не особенно полезно: амплитуды на разных путях означают, что они не все имеют одинаковое значение, и в отличие от недетерминированных машин Тьюринга, это недостаточно иметь ненулевую амплитуду для какого-либо результата; должна быть возможность получить очень большую вероятность получения правильного результата, например 2/3. (Класс задач BQPкоторую может эффективно решить квантовая машина Тьюринга, требует разрыва вероятности того же рода, что и BPP для рандомизированных вычислений.) Кроме того, очень сильно в отличие от недетерминированных машин Тьюринга, квантовая машина Тьюринга может создавать помехи друг другу после их разделения , что просто невозможно в типичной формулировке недетерминированной машины Тьюринга (и это делает описание в терминах дерева решений в первую очередь менее полезным).
Сравнивая две модели
Мы не знаем, является ли одна из этих машин более мощной, чем другая; различные способы их недетерминированности кажутся отличными друг от друга, и их трудно сравнивать.
Что касается проблем, которые каждая машина может быстро решить, то, что другая не может (насколько мы знаем):
Но даже если кто-то показывает, как связать два вида машин друг с другом - и даже в крайне маловероятном сценарии, когда кто-то показывает, что BQP = NP (проблемы, которые могут быть решены квантовой машиной Тьюринга и недетерминированной машиной Тьюринга, соответственно) ) - две машины, которые определяют эти модели вычислений, сильно отличаются друг от друга.
источник