Квантовые вычисления со времен Демокрита - Скотт Ааронсон

которому BQP ⊄ PH? Увы, сегодня, когда прошло два десятилетия и потерпело неудачу неизвестное число аспирантов, ответ по-прежнему отрицателен. Тем не менее многие из нас по-прежнему считают разделение возможным, и до недавнего времени задача рекурсивной выборки Фурье была практически единственным кандидатом на эту роль.

Наконец в 2009 г. я предложил другую задачу-кандидата[77], получившую известность под названием «проверка коэффициентов Фурье»; по идее, она должна дать не просто разделение BQP и PH по оракулу, но и (в отличие от рекурсивной выборки Фурье) разделение экспоненциальное. Увы, доказательство этого разделения, судя по всему, требует кое-каких новых достижений в классической теории сложности, а именно в определении нижних оценок схем постоянной глубины, пока нам неизвестных. Однако не исключено, что в результате работы над проверкой коэффициентов Фурье задачу рекурсивной выборки Фурье удастся наконец превзойти, и она сохранит лишь историческое значение.

Квантовые вычисления и NP-полные задачи

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

Я бы сказал, что именно это — основа неверных представлений неспециалиста о квантовых вычислениях. Позвольте пояснить.

Очевидно, мы не можем пока доказать, что квантовые компьютеры не способны эффективно решать NP-полные задачи, иными словами, что NP ⊄ BQP, поскольку мы не можем даже доказать, что P ≠ NP! Мы также совершенно не представляем себе, как доказать, что если P ≠ NP, то NP ⊄ BQP.

По существу, у нас есть только давний результат Беннетта, Бернштейна, Брассара и Вазирани о том, что существует оракул, в отношении которого NP ⊄ BQP. Или конкретнее, предположим, то вы ищете в пространстве 2n возможных решений единственное верное, и предположим, что возможное решение-кандидат вы можете только скормить «черному ящику», чтобы он сказал, верное оно или нет. В таком случае сколько раз вам нужно послать запрос черному ящику, чтобы найти верное решение? В классическом варианте ясно, что вам потребуется ~2n запросов в худшем случае (или ~2n/2 в среднем). С другой стороны, Гровер[78] предложил известный квантовый алгоритм поиска, посылающий черному ящику всего ~2n/2 запроса. Интересно, что еще до открытия алгоритма Гровера Беннетт и др. доказали, что он оптимален! Иными словами, любому квантовому алгоритму поиска иголки в стоге сена размером 2n потребуется по крайней мере ~2n/2 шагов. Так что итог таков: в случае «обобщенных», или «неструктурированных», поисковых задач квантовые компьютеры способны дать некоторое, а именно квадратичное, ускорение по сравнению с классическими компьютерами, но ничем похожим на экспоненциальное ускорение, которое дает алгоритм Шора для разложения на простые множители, здесь и не пахнет.

Вы можете спросить: почему ускорение должно быть именно квадратичным, а не кубическим или каким-то еще? Позвольте, я попытаюсь ответить на этот вопрос, не вдаваясь в конкретику ни алгоритма Гровера, ни доказательства оптимальности Беннетта и др. По существу, причина, по которой мы получаем квадратичное ускорение, состоит в том, что квантовая механика основана на второй, а не на первой норме. В классической информатике если имеется N решений, только одно из которых верно, то после одного запроса мы получаем вероятность угадывания, равную 1/N, после двух запросов — вероятность 2/N, после трех — 3/N и т. п. Таким образом, для получения непренебрежимой (то есть близкой к единице) вероятности угадывания верного ответа нам требуется ~N запросов. Но в квантовом варианте мы применяем линейные преобразования к векторам амплитуд, которые представляют собой квадратные корни из вероятностей. Так что думать об этом следует так: после одного запроса мы получаем амплитуду угадывания верного решения, равную

после двух запросов мы имеем амплитуду после трех запросов — амплитуду и т. п. Таким образом, после T запросов амплитуда угадывания верного решения равняется а вероятность равняется Следовательно, вероятность будет близка к единице после всего лишь T ≈ √N запросов.

Ну хорошо, те из вас, кто читает мой блог[79], должно быть, устали от споров об ограниченности квантовых компьютеров при решении неструктурированных поисковых задач. Так что я позволю себе вольность и закончу на этом данный раздел.

Квантовые вычисления и многомировая интерпретация

Поскольку данная книга носит название «Квантовые вычисления со времен Демокрита», мне, наверное, следует завершить главу глубоким философским вопросом. Ну хорошо, как насчет такого: если бы нам удалось построить нетривиальный квантовый компьютер, можно было бы считать это доказательством существования параллельных вселенных?

Один из основателей теории квантовых вычислений в 1980-е гг. Дэвид Дойч определенно считает, что можно[80]. Хотя, чтобы быть точным, Дойч убежден, что воздействие было бы «всего лишь» психологическим, поскольку для него квантовая механика уже доказала существование параллельных вселенных! Дойч любит задавать вопросы вроде такого: если алгоритм Шора успешно раскладывает на простые множители 3000-значное целое число, то где при этом производится разложение? Откуда взялись вычислительные ресурсы, необходимые для разложения этого числа, если не из какой-то «мультивселенной», экспоненциально большей, чем та, которую мы видим вокруг? На мой взгляд, Дойч здесь неявно предполагает, что задача разложения на простые множители не входит в BPP, но это не важно; для целей данной дискуссии мы вполне можем согласиться с этим его предположением.

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

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