Есть ли формальное доказательство того, что квантовые вычисления являются или будут быстрее, чем классические вычисления?

Вместо того, чтобы эмпирически доказывать, какими формальными принципами мы доказали, что квантовые вычисления будут быстрее, чем традиционные / классические вычисления?

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

Классами сложности, обычно связанными с эффективными классическими вычислениями, являются (для детерминированных алгоритмов) и B P P (для рандомизированных). Квантовый аналог этих классов Б В Р . Все три класса являются подмножествами P S P A C E (очень мощный класс). Тем не менее, наши нынешние методы доказательства не являются достаточно сильными , чтобы окончательно доказать , что P это не то же самое, что P S P A C E . Таким образом, мы не знаем, как формально отделить P от B Q $\mathsf{P}$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{PSPACE}$$\mathsf{P}$$\mathsf{PSPACE}$$\mathsf{P}$$\mathsf{BQP}$либо - так как , отделяя эти два класса труднее , чем уже грозную задачу отделения P от P S P A C E . (Если бы мы могли доказать P ≠ B Q P , мы бы сразу получили доказательство того, что P ≠ P S P A C E , поэтому доказательство P ≠ B Q $\mathsf{P \subseteq BQP \subseteq PSPACE}$$\mathsf{P}$$\mathsf{PSPACE}$$\mathsf{P \ne BQP}$$\mathsf{P \ne PSPACE}$$\mathsf{P \ne BQP}$должна быть, по крайней мере, такой же сложной, как и без того очень сложная задача доказательства ). По этой причине в современном уровне техники трудно получить строгое математическое доказательство, показывающее, что квантовые вычисления будут быстрее, чем классические вычисления.$\mathsf{P \ne PSPACE}$

Таким образом, мы обычно полагаемся на косвенные доказательства разделения классов сложности. Наши самый сильные и самые известные доказательства алгоритм Шора , что позволяет нам фактор . Напротив, мы не знаем ни одного алгоритма, который мог бы учитывать B P P - и большинство людей считают, что его не существует; это одна из причин, почему мы используем RSA для шифрования, например. Грубо говоря, это подразумевает, что для квантового компьютера возможен эффективный факторинг, но предполагает, что для классического компьютера может быть невозможным эффективный факторинг. По этим причинам результат Шора показал многим, что B Q P является строго более мощным, чем B P $\mathsf{BQP}$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{BPP}$(и, следовательно, также более мощный, чем ).$\mathsf{P}$

Я не знаю каких-либо серьезных аргументов в пользу того, что , за исключением тех людей, которые верят в крушение классов гораздо большей сложности (которые составляют меньшинство сообщества). Наиболее серьезные аргументы, которые я слышал против квантовых вычислений, исходят из позиций, более близких к физике, и утверждают, что B Q P неправильно отражает природу квантовых вычислений. Эти аргументы, как правило, говорят о том, что макроскопические когерентные состояния невозможно поддерживать и контролировать (например, из-за некоторого еще неизвестного фундаментального физического препятствия), и, таким образом, операторы, на которые опирается B Q P, не могут быть реализованы (даже в принципе) в нашем мире. ,$\mathsf{BQP = P}$$\mathsf{BQP}$$\mathsf{BQP}$

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

Что касается сложности вычислений, то нет никаких доказательств того, что квантовые компьютеры лучше классических, потому что трудно получить нижнюю оценку сложности задач. Тем не менее, существуют настройки, в которых квантовый компьютер доказуемо работает лучше, чем классический. Наиболее известным из этих примеров является модель черного ящика, в которой у вас есть доступ через черный ящик к функции и вы хотите найти уникальный x, для которого f оценивается как 1. мера сложности в этом случае число обращений к $f:\{0,1\}^n\mapsto \{0,1\}$$x$$f$$f$, Классически, вы не можете сделать лучше, чем угадать наугад, который в среднем получает Ω ( 2 n ) запросов к f . Однако, используя алгоритм Гровера, вы можете выполнить ту же задачу в O ( $x$$\Omega(2^n)$$f$.$O(\sqrt{2^n})$

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

Артем Казнатчеев приводит краткое изложение некоторых основных причин, по которым мы ожидаем, что квантовые компьютеры будут принципиально быстрее, чем классические компьютеры, для некоторых задач.

Если вам нужно дополнительное чтение, вы можете прочитать лекционные заметки Скотта Ааронсона по квантовым вычислениям , в которых обсуждается алгоритм Шора и другие алгоритмы, которые допускают эффективные квантовые алгоритмы, но, похоже, не допускают какого-либо эффективного классического алгоритма.

Там есть дискуссия о том, может ли быть построены квантовые компьютеры на практике: это BQP точная модель реальности, или есть что - то , что могло бы помешать нам строить квантовый компьютер, либо для инженерных причинам или из - за фундаментальных физических барьеров? Вы можете прочитать лекционные заметки Скотта Ааронсона, в которых резюмированы аргументы, высказанные другими, а также прочитать его пост в блоге с его мнением об этих дебатах , но у нас, вероятно, не будет однозначного ответа, пока кто-то на самом деле не создаст квантовый компьютер, способный выполнять нетривиальные задачи. (например, фактор большого числа).

Основное здание квантовых вычислений - Унитарное преобразование, это основной инструмент ускорения многих алгоритмов в литературе. Алгоритмы, которые используют унитарные, используют теоретико-числовые свойства числа / проблем под рукой - нахождение периодов, ускорения в квантовых блужданиях и т. Д. Ускорения в естественных задачах все еще неясны - как указывалось. Является ли факторинг больших чисел самоцелью для квантовых вычислений, остается открытым вопросом. Другие открытые вопросы, такие как QNC, его отделение от NC, могут все еще дать неясные подсказки о том, что могут сделать квантовые компьютеры. Но если цель квантового компьютера состоит в том, чтобы учесть большие числа - это может быть еще возможно, само по себе в будущем, со страшными последствиями (конечно, для личной жизни)!

Я хотел ответить на комментарии Нила де Бодрапа относительно источника квантовых ускорений, но я не могу комментировать. Я не знаю, смогу ли я опубликовать ответ.

На мой взгляд, все квантовые ускорения связаны с запутанностью. Единственный алгоритм, где мы можем сделать что-то быстрее классических компьютеров, не используя запутанные состояния, - это Deutsch-Jozsa для вычисления четности двух битов. Если мы говорим об асимптотических ускорениях, запутывание необходимо, а на самом деле его очень много. Если квантовый алгоритм требует небольшого количества запутывания, он может быть эффективно классически смоделирован. Я могу указать на статью http://arxiv.org/abs/quant-ph/0201143 , в которой конкретно обсуждается алгоритм факторинга и степень его запутанности.

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

этот вопрос пытается аккуратно разделить теоретические и прагматические / экспериментальные аспекты этого вопроса, но экспериментатор или инженер могут утверждать, что они тесно связаны, неразделимы, и что исторический прогресс в этой задаче является доказательством / доказательством этого.

следующий пункт, безусловно, не выиграет конкурсы популярности (возможно, из-за хорошо известного / наблюдаемого предубеждения, что отрицательные результаты редко сообщаются с научной точки зрения), но стоит отметить, что существует мнение меньшинства / противоположности, продвигаемое различными заслуживающими доверия Даже элитные исследователи считают, что QM-вычисления могут или никогда не будут реализованы физически из-за непреодолимых трудностей реализации, и даже для этого есть некоторое теоретическое обоснование / анализ (но, возможно, больше из теоретической физики, чем из TCS). (и обратите внимание, что у некоторых могут быть сомнения, но они не хотят продолжать ставить под сомнение «доминирующую парадигму».) Основные аргументы основаны на присущей QM шумности, принципе неопределенности Гейзенберга и фундаментальном экспериментальном беспорядке установок QM и т. д.

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

Одним из наиболее ярых сторонников негативного взгляда (граничащего с экстремальным / убийственным!) является Дьяконов, но он, тем не менее, страстно аргументирует случай, основываясь на всех ракурсах:

• Состояние и перспективы квантовых вычислений / Дьяконов

• Перспективы квантовых вычислений: крайне сомнительно / Дьяконов

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

• Вечное движение 21-го века?

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