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

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

Люди, которые знают что-либо о теоретических квантовых вычислениях, знают, что эта история - абсолютная ерунда, и что грубая идея, описанная выше, больше соответствует недетерминированной машине Тьюринга (NTM), чем квантовому компьютеру. Более того, класс сложности задач, эффективно решаемых NTM, - это NP, а QC - это BQP , и эти классы не считаются равными.

Люди, пытающиеся исправить популярную презентацию, справедливо отмечают, что упрощенный нарратив "многих миров" сильно преувеличивает силу КК, которые, как полагают, не способны решить (скажем) NP- неполные проблемы. Они сосредоточены на искажении процесса измерения: в квантовой механике результат, который вы измеряете, определяется правилом Борна, и в большинстве ситуаций вероятность измерения неверного ответа полностью перекрывает вероятность измерения правильного. (И в некоторых случаях, таких как поиск в «черном ящике»), мы можем доказать, что ни одна умная квантовая схема не может превзойти правило Борна и обеспечить экспоненциальное ускорение.) Если бы мы моглиВолшебно «решите, что измерять», тогда мы сможем эффективно решить все проблемы в классе сложности PostBQP , который, как полагают, намного больше, чем BQP .

Но я никогда не видел, чтобы кто-то прямо указывал на то, что есть другая причина, по которой популярная характеристика ошибочна, которая идет в другом направлении. Считается, что BQP не является строгим подмножеством NP , но, напротив, несопоставимо с ним. Существуют такие проблемы, как проверка Фурье, которые, как полагают, лежат не только за пределами NP , но на самом деле за пределами всей полиномиальной иерархии PH . Таким образом, в отношении подобных проблем, популярный нарратив на самом деле под состояниями, а не преувеличивает силу КК.

Моя наивная интуиция заключается в том, что если бы мы могли «выбрать, что измерить», популярный нарратив был бы более или менее правильным, что означало бы, что эти супер-квантовые компьютеры смогут эффективно решать именно класс NP . Но мы считаем, что это неправильно; фактически PostBQP = PP , который мы считаем строгим надмножеством NP .

Есть ли какая-то интуиция в том, что происходит за кулисами, которая позволяет квантовому компьютеру (в некоторых отношениях) быть более мощным, чем недетерминированная машина Тьюринга? Предположительно, эта «изначально квантовая» сила в сочетании с поствыбором (что в некотором смысле уже есть у НТМ) делает супер-КК гораздо более мощным, чем НТМ. (Обратите внимание, что я ищу некоторую интуицию, которая напрямую противопоставляет NTM и QC с поствыбором, без «прохождения» классического класса сложности PP .)

С псевдо-фундаментальной точки зрения, причина, по которой BQP является классом, отличным от NP (по- другому ), чем NP , состоит в том, что квантовые компьютеры могут рассматриваться как использующие деструктивное вмешательство.

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

• Является ли количество принимающих ветвей нулевым или ненулевым? (Характеристика НП .)
• Количество принимающих ответвлений меньше максимального или точно равно максимальному? (Характеристика ЧНП .)
• Является ли количество принимающих филиалов не более одной трети или не менее двух третей от общего числа? (Характеристика БПП .)
• Является ли количество принимающих ответвлений меньше половины или хотя бы наполовину от общего числа? (Характеристика по пп .)
• Отличается ли количество принимающих ветвей от ровно половины или равно ровно половине общего количества? (Характеристика класса называется C ₌ P. )

Они называются классами подсчета , потому что в действительности они определяются с точки зрения количества принимающих ветвей.

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

Таким образом, наиболее известные верхние границы для BQP , а именно AWPP и PP , легко определить с точки зрения «промежутков принятия». Класс NP , однако, не имеет такой очевидной характеристики. Кроме того, многие из классов, которые можно получить из определений с точки зрения промежутков принятия, кажутся более мощными, чем NP . Можно было бы принять это, чтобы указать, что «недетерминированное деструктивное вмешательство» является потенциально более мощным вычислительным ресурсом, чем простой недетерминизм; так что даже если квантовые компьютеры не в полной мере используют этот вычислительный ресурс, он, тем не менее, может противостоять легкому сдерживанию в таких классах, как NP .

Этот ответ был «перенесен» с момента, когда этот вопрос был задан в области компьютерных наук (автор остался прежним)

Ну, одна из основных причин заключается в том, что нет квантовых алгоритмов, которые решают NP-сложные задачи за полиномиальное время.

Другое состоит в том, что адиабетический квантовый отжиг (как в Dwave) едва может превзойти классический квантовый отжиг.

$\neq$$=$$\neq$$\neq$$=$$=$

$=$

$\neq$

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

$O(n)$$O(n)$