Известно два примера нетри¬виальных задач, в которых KB дают радикальный выигрыш.
Первый из них - задача разло¬жения целых чисел на простые мно¬жители и, как следствие, вычисле¬ния дискретного логарифма (ДЛ). Дальше речь пойдет именно о ДЛ.
Пусть у нас есть поле вычетов по модулю простого числа. В нем есть первообразные корни - такие вы¬четы, чьи степени порождают все ненулевые элементы. Если задан такой корень и задана степень, то возвести в степень можно быстро (например, сначала возводим в квадрат, потом получаем четвертую сте¬пень, и т. д.) Дискретный лога¬рифм - это обратная задача. Дан первообразный корень и какой-то элемент поля; найти, в какую степень нужно возвести этот корень, чтобы получить данный элемент. Вот эта задача уже считается сложной. На¬столько сложной, что ряд совре¬менных криптографических систем основан на том предположении, что вычислить ДЛ за приемлемое время невозможно, если модуль - доста¬точно большое простое число.
Так вот, для дискретного лога¬рифма есть эффективный кванто¬вый алгоритм. Его придумал Шор в конце 1994 года. Пос¬ле его статьи и начался взрыв публи¬каций по КВ. Независимо от него, Алексей Китаев из ИТФ им. Ландау построил квантовый алгоритм для этой и некоторых более общих за¬дач [8]. Идеи у них были разные.
Шор использовал примерно такую идею, она существенно квантовая: рассмот¬рим базис в фазовом пространстве. Он состоит из классических состояний. Но в линейном пространстве много базисов. Мы можем найти некий оператор, который эффективно строит другой базис; мы можем к нему перейти, сделать там какие-то вычисления, вернуться обратно и получить нечто совершенно отлич¬ное от того, что мы имели бы в классическом базисе. Одна из воз¬можностей использовать квантовость состоит в том, что мы строим какой-то странный базис, в нем что-то делаем, возвращаемся обратно и интерпретируем результат. Шор именно эту идею и реализовал. При¬чем преобразование оказалось та¬кое, которое и в физике, и в матема¬тике имеет принци¬пиальное значение - дискретное преобразование Фурье.
Его можно представить в виде тензорного произведения опера¬торов, которые действуют на каж¬дый из кубитов такой матрицей:

Китаев придумал примерно следующее. Есть некото¬рая ячейка - основной регистр, где мы записываем наши данные нулями и единицами. И еще есть один управляющий кубит. Мы ра¬ботаем так: у нас реализована про¬цедура умножения на первообраз¬ный корень, на квадрат первооб¬разного корня, и т. д. Управляю¬щий кубит переводим в некоторое смешанное состояние, дальше строим такой оператор, который, в зависимости оттого, ноль или еди¬ница в этом управляющем кубите, либо применяет умножение к на¬шему основному регистру, либо не применяет. А потом кубит опять возвращаем в смешанное состоя¬ние. Оказывается, что это эффек¬тивный способ проделать некото¬рое измерение. То есть Китаев за¬метил, что одна из вещей, которые мы можем эффективно делать на квантовом компьютере, - это имитировать процесс квантового измерения. В данной задаче из результатов этих измерений эф¬фективно извлекается ответ.
Сам процесс вычислений, происходит так: мы все время умножаем одну и ту же ячей¬ку на некие константы, результаты измерений записываем, а потом производим своего рода обработ¬ку результатов эксперимента - уже чисто классическими вычис¬лениями. Вся квантовая часть зак¬лючается в том, что где-то рядом с нашим регистром находится в некоем смешанном состоянии коррелированный с ним кубит, и мы его периодически наблюдаем.
Для вы¬числения ДЛ числа, записанного N битами, нужно потратить N 3 еди¬ниц времени. Вполне реализуе¬мо - на КК, естественно. Но здесь надо заметить, что никто пока не доказал, что не существует столь же быстрого алгоритма для вы¬числения ДЛ на обычной машине.
Вторая задача предложена Гровером (L. Grover) [9]. Рассмотрим базу дан¬ных, содержащую 2N записей. Мы хотим найти ровно одну запись. Имеется некая процедура опреде¬ления того, нужную запись мы взяли или нет. Записи не упоря¬дочены. С какой скоростью мы можем решить эту задачу на обыч¬ном компьютере? В худшем слу¬чае нам придется перебрать все 2N записей - это очевидно. Оказывается, что на КК достаточно числа запросов по¬рядка корня из числа записей – 2N/2.
Интересная задача - созда¬ние оптимальных микросхем. Пусть есть функция, которую нужно ре¬ализовать микросхемой, и эта функция задана программой, ис¬пользующей полиномиально ог¬раниченную память. Построение нужной микросхемы с минималь¬ным числом функциональных эле¬ментов - задача PSPACE. По¬этому появление устройств, эф¬фективно решающих PSPACE-задачи, позволило бы единообразно проектировать оптимальные по своим показателям вычислитель¬ные устройства обычного типа. Кроме того, в PSPACE попадает большинство задач «искусственного интеллекта»: машинное обучение, распознавание образов и т.д.
Так вот, точно установлено, что KB находятся где-то между обыч¬ными вероятностными вычисле¬ниями и PSPACE. Если все же ока¬жется, что KB можно эффективно реализовать на классических ве¬роятностных машинах, не будет смысла в физической реализации квантовых машин. Если же выяс¬нится, что при помощи KB можно эффективно решать те или иные PSPACE-задачи, то физическая реализация КК откроет принци¬пиально новые возможности.
Есть еще одна область применения КК, где заведомо возможен радикальный выигрыш у существующих техно¬логий. Это моделирование самих квантовых систем.
Давайте посмотрим на такой вопрос: как можно эволюцию квантовой системы изучать на обычном компьютере? Это посто¬янно делается, так как это задача важна для химии, молеку¬лярной биологии, физики и т.п. Но, за счет эк¬споненциального роста размер¬ности при тензорном произведе¬нии, для моделирования десяти спинов вам нужно оперировать с тысячемерным пространством, сто спинов - это уже конец. А если вспомнить, что в молекуле белка десятки тысяч атомов, то... Там, правда, не всюду существенно именно квантовое моделирование, но в целом ясно, что есть очень серьезные препятствия для моде¬лирования квантовых систем на классических компьютерах. Так что если создать вычислительное устройство, которое ведет себя квантовым образом, то по край¬ней мере один важный класс за¬дач на нем есть смысл решать - можно моделировать реальные квантовые системы, возникающие в физике, химии, биологии.