Ссылки на сравнение между квантовыми компьютерами и машинами Тьюринга

Мне сказали, что квантовые компьютеры не являются вычислительно более мощными, чем машины Тьюринга. Может ли кто-нибудь любезно помочь дать некоторые литературные ссылки, объясняющие этот факт?

computability reference-request turing-machines quantum-computing Мок-Конг Шен
источник

Вы , кажется , есть зарегистрированный аккаунт на других сайтах Stack Exchange. Вы должны зарегистрировать свой аккаунт CS и связать его с другими (см справочного центра ). Помимо всего прочего, это позволит вам участвовать в чате с CS.

Жиля SO- перестать быть злым »

Ответы:

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

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

Вся проблема, возникающая из квантовой механики, состоит в том, чтобы определить, могут ли такие коэффициенты быть эффективно вычислены , что является более сложной задачей, чем то, могут ли они быть вычислены вообще .

Ниль де Бодрап
источник

Хотя знания моего новичка говорят мне, что квантовая схема представляет собой матричное преобразование Адамара, я пока не вижу, как возможность программирования для выполнения произвольных матричных вычислений на классическом компьютере могла бы заменить физическую квантовую схему. Например, моя книга говорит о генерации случайных чисел следующим образом: 1. | x> <- | 0> 2. | x> <- H | x> 3. Измерение | x> Что в частности соответствует шагу 3 программирование на классическом компьютере?

Мок-Конг Шен

(Нормализованная) матрица Адамара - это только одно из возможных унитарных преобразований. Для вашего вычисления мы можем признать, что детерминированная машина Тьюринга может вычислить распределение вероятности (0,5, 0,5), состоящее из квадрата норм первого столбца матрицы Адамара , и что для рандомизированной машины Тьюринга (которая может выполнять подбрасывание монет), мы можем пойти еще дальше и получить выборку из этого распределения вероятности. В любом случае на любую функцию, вычисленную по квантовой схеме с ошибкой <1/2, классическая машина тоже может.

| ⟨ b | H | 0 ⟩ |^{2}

$\bigl|\langle b |H|0\rangle\bigr|^2$

Ниль де Бодрап

@ Мок-Конг Шен: в случае , если это не ясно из моих замечаний по поводу неэффективности или медлительности, принято считать , что квантовые компьютеры являются вычислительно более мощным в том смысле, что в состоянии вычислить более быстро . Я обращаю внимание на тот факт, что они не способны вычислять вещи, которые классический компьютер тоже не может вычислить (где я игнорирую понятие «подбрасывание монеты» в качестве вычисления).

Ниль де Бодрап,

Рассмотрим квантовые ворота. Сглаживание всех технических деталей, она может быть представлена в виде матрицы . Вход в вентиль, скажем, - это просто вектор , а выход вентиля - вектор . $G$ $\vert \phi \rangle$ $v$ $Gv$

Теперь рассмотрим схему. Схема - это просто группа ворот , и сама схема может рассматриваться как «обобщенный вентиль» , который работает с входным состоянием (вектором ). [Опять же, это очень грубая абстракция.] $\{G_1, G_2, ... \}$ $C=G_n \cdots G_2 G_1$ $v$

В общем, вычисление схемы на входе - это просто вычисление вектора или . Понятно, что такую задачу (умножение матрицы и умножение матрицы на вектор) может выполнить классическая ТМ, поэтому ТМ, по крайней мере, так же сильна, как квантовая ТМ (QTM) [хорошо, классические схемы так же сильны, как квантовая схем. не обращайте на это внимания.] $\vert \phi \rangle$ $Cv$ $G_n \cdots G_2 G_1 v$

С другой стороны, QTM тривиально так же силен, как и TM, и поэтому обе модели эквивалентны.

РЕДАКТИРОВАТЬ из-за комментариев
Чтобы спросить, какой «компьютер» является более мощным, нам нужно сначала уточнить, что значит быть «более мощным в вычислительном отношении». И эта полуфилософская дискуссия начинается с вопроса

Что такое вычисления ?

Является ли "воспроизведение MP3" файлов вычислением? Является ли вывод случайных чисел вычислением?

Стандартное определение гласит, что вычисление - это «вычисление функции». То есть для каждого входного (который может быть любой строкой любой конечной длины) выведите , где снова может быть строкой произвольной (конечной) длины. Если ваш компьютер может вывести для любого , мы говорим, что он может вычислить . $x$ $y=f(x)$ $y$ $y$ $x$ $f$

Теперь, чтобы сказать , что компьютер «А» является более мощным , чем «B» просто означает , что вычисляет больше функций , чем . По аналогии, $f$ $B$

Две модели, и считаются эквивалентными , если для любой функции , вычисляет тогда и только тогда , когда вычисляет . $A$ $B$ $f$ $A$ $f$ $B$ $f$

Хорошо, вы говорите, но подождите секунду, есть случайность. Квантовый компьютер не просто выводит . Он выдает с вероятностью или с вероятностью или .... $y$ $y_1$ $p_1$ $y_2$ $p_2$ $^0$

Действительно ... И это расширяет стандартное определение вычисления функции. Мы можем решить это и обобщить наши определения несколькими способами. (1) один вариант - сказать, что ответом является тот конкретный который имеет вероятность (и существует не более одного такого значения) . Если предположить, что выводит только один бит, то «выход всегда хорошо определен В противном случае, если такого значения не существует и все выходы имеют малую вероятность, мы можем сказать $f(x)$ $y_i$ $p_i>0.75$ $^1$ $f$ $f(x)$ $^2$ $f$ не определен на этом входе; (2) Второй вариант должен сказать , что выход список , Для того, чтобы это было правильно определено, у нас должен быть конечный список, так как мы требовали, чтобы выходная строка была конечной. $f(x)$ $(y_1,p_1), (y_2,p_2),...$

С учетом вышесказанного должно быть ясно, что наличие вероятностей не меняет мощность модели, и классический TM может просто вывести список возможных выходных данных вместе с вероятностью для каждого выходного. это именно то, что происходит, когда ТМ умножает матрицы и выводит вектор - вектор представляет вероятность каждого возможного результата измерения.

^{$^0$

$^1$ $p=0.75$ $1/2$

$^2$ $f$}

Ран Г.
источник

Я мог программировать матричные вычисления на классическом компьютере, но не знаю, как написать код для моделирования квантовых вычислений. В любом случае мне понадобятся квантовые биты. Квантовый бит имеет 2 значения, обычно обозначаемых альфа и бета. Какие значения я должен использовать? Смотрите также мой комментарий к ответу Ниль де Бодрап для случая генерации случайных чисел.

Мок-Конг Шен

| ψ ⟩ = α | 0 ⟩ + β | 1 ⟩

$\def\ket#1{|#1\rangle}\ket\psi = \alpha\ket0 + \beta\ket1$

ψ ψ = [α β]^{⊤}

$\pmb\psi = [\alpha\quad\beta]^\top$

@Niel de Beaudrap: Но когда я пишу код для имитации определенного квантового вычисления, например, генерации случайных чисел, о котором я говорил, мне нужно реализовать симулированные квантовые биты на классическом компьютере. Я не знаю, как написать код, чтобы сделать это, не зная значений этих коэффициентов.

Мок-Конг Шен

@ Мок-Конг Шен: дело в том, что во время выполнения вы знаете; и проблема точно такая же, как выборка из классического распределения вероятностей, которое указывается на входе, т.е. она сводится к хорошо изученным задачам случайной выборки. Например, здесь применяются методы Монте-Карло.

Ниль де Бодрап,

@ Mok-KongShen Пожалуйста, не используйте комментарии (особенно к чужим постам) для расширенных обсуждений. Перейти к чату , либо в общей комнате для этого сайта или в чате , созданный для этой цели.

Жиль "ТАК - перестань быть злым"

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

но эквивалентность в теории сложности очень сильно зависит от временных и пространственных тонкостей / эффективности, то есть ресурсов для вычисления конкретных алгоритмов. а также огромное количество исследований, посвященных «шуму» в вычислениях QM, в которых рассматривается, что теоретические бесшумные модели могут быть «нереальными» или не достижимыми на практике, а реальные модели могут иметь / будут иметь значительный шум. Существуют сложные схемы для снижения этого шума и т. д .; есть несколько превосходных комментариев по этому поводу в различных постах в блоге RJ Liptons, например, летательные аппараты 21-го века

например, Шор доказал, что факторинг в BQP, классе квантовых алгоритмов, выполняющихся за время P, доказал, что в то же время было запущено большое количество серьезных исследований / исследований в области вычислений QM из-за драматического результат.

$\stackrel{?}{=}$

Скотт Ааронсон - отличный писатель / исследователь в этой области, он написал несколько статей, доступных для непрофессионала. см., например, «Ограничение компьютеров QM, SciAm или вычислений QM, обещает новое понимание, Нью-Йорк Таймс» .

ВЗН
источник

Обратите внимание, что Арам Харроу является ведущим скептиком в QM-вычислениях относительно проблем с шумом. Еще одно хорошее место для начала, блог RJ Lipton, вечное движение 21-го века?

ВЗН