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

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

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

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

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

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