На первый взгляд, квантовые алгоритмы имеют мало общего с классическими вычислениями и P против NP, в частности: решение задач из NP с квантовыми компьютерами ничего не говорит нам об отношениях этих классических классов сложности 1 .
С другой стороны, «альтернативное описание» классического класса сложности PP как класса PostBQP, представленное в этой статье , насколько мне известно, рассматривается как важный результат для «классической сложности», под термином «квантовая сложность». ,
Фактически, Скотт Ааронсон, автор статьи, пишет в конце реферата:
Это показывает, что квантовые вычисления могут дать новые и более простые доказательства основных результатов о классических вычислениях.
Следовательно, мой вопрос: есть ли результаты в области квантовой сложности, которые «упрощают» проблему P против NP, подобно квантовому описанию PP? Если таких результатов нет, есть ли веская причина не ожидать этих результатов, несмотря на «успех» для PP?
1: Возьмите ответ на этот вопрос, например: станет ли проблема P против NP тривиальной в результате развития универсальных квантовых компьютеров?
источник
Ответы:
Я не думаю, что есть четкие причины для ответа «да» или «нет». Тем не менее, я могу привести причину, по которой PP с большей вероятностью допускает такую характеристику, чем NP , и дать некоторую интуицию о том, почему NP никогда не может иметь простую характеристику с точки зрения модификации квантовой вычислительной модели.
Подсчет сложности
Классы NP и PP могут быть охарактеризованы с точки зрения количества принимающих ветвей недетерминированной машины Тьюринга, которую мы можем описать более приземленным способом с точки зрения возможных результатов рандомизированного вычисления, которое использует равномерно случайные биты. Затем мы можем описать эти два класса как:
L ∈ NP, если существует рандомизированный алгоритм полиномиального времени, который выводит один бит α ∈ {0,1}, такой, что x ∈ L тогда и только тогда, когда Pr [ α = 1 | x ] не равен нулю (хотя эта вероятность может быть крошечной), в отличие от нуля.
L ∈ PP, если существует рандомизированный алгоритм за полиномиальное время, который выводит один бит α ∈ {0,1}, такой, что x ∈ L тогда и только тогда, когда Pr [ α = 1 | х ] больше 0,5 (хотя, возможно, только на крошечное количество), в отличие от того, чтобы быть равным или меньше 0,5 ( например , на крошечное количество).
Один из способов понять, почему эти классы не могут быть практически решены с помощью этого вероятностного описания, состоит в том, что может потребоваться экспоненциально много повторений, чтобы быть уверенными в оценке вероятности для Pr [ α = 1 | х ] из-за незначительности различий в вероятностях.
Сложность разрыва и квантовая сложность
Давайте опишем результаты «0» и «1» в приведенных выше вычислениях как «отклонить» и «принять»; и давайте назовем рандомизированную ветвь, которая дает результат отклонения / принятия, отклоняющую или принимающую ветвь. Поскольку каждая ветвь рандомизированного вычисления, которая не принимает, следовательно, отклоняет, PP также может быть определен с точки зрения разницы между числом принимающих и отклоняющих вычислительных путей - величиной, которую мы можем назвать разрывом принятия : в частности, является ли принятие разрыв положительный или меньше или равен нулю. Приложив немного больше работы, мы можем получить эквивалентную характеристику для PPс точки зрения того, больше ли промежуток принятия, чем некоторый порог, или меньше, чем некоторый порог, который может быть нулевым, или любая другая эффективно вычисляемая функция входа x .
Это, в свою очередь, может использоваться для характеристики языков в PP с точки зрения квантовых вычислений. Из описания PP в терминах рандомизированных вычислений, имеющих вероятности принятия (возможно, немного) больше 0,5 или не более 0,5, все проблемы в PP допускают квантовый алгоритм за полиномиальное время, который имеет такое же различие в вероятностях принятия; и моделируя квантовые вычисления как сумму по вычислительным путям, и моделируя эти пути, используя отклоняющие ветви для путей с отрицательным весом и принимая ветви путей с положительным весом, мы также можем показать, что такой квантовый алгоритм, имеющий (статистически слабое) различие, описывает проблема в пп .
Не очевидно, что мы можем сделать то же самое для NP . Не существует естественного способа описать NP с точки зрения промежутков принятия и очевидной догадки о том, как вы можете попытаться вписать его в квантовую вычислительную модель - задав вопрос, равна ли вероятность измерения результата «1» нулю или нет. ноль - вместо этого дает вам класс с именем coC = P , который не известен как равный NP , и очень грубо можно охарактеризовать как такой же мощный, как PP, а не близкий к NP по мощности.
Конечно, когда-нибудь можно будет как-то найти характеристику NP с точки зрения промежутков принятия, или можно найти новые способы соотнести квантовые вычисления с подсчетом сложности, но я не уверен, что у кого-нибудь есть какие-либо убедительные идеи о том, как это может произойти.
Резюме
Перспективы получить представление о самой проблеме P против NP с помощью квантовых вычислений не являются многообещающими - хотя это не невозможно.
источник