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

Математические основы функционирования квантовых компьютеров.

Классический компьютер состоит, грубо говоря, из некоторого числа битов, с которыми можно выпол­нять арифметические операции. Основным элементом кванто­вого компьютера (КК) являются квантовые биты, или кубиты (от Quantum Bit, qubit). Обычный бит - это классическая система, у которой есть только два возмож­ных состояния. Можно сказать, что пространство состояний бита - это множество из двух элемен­тов, например, из нуля и единицы. Кубит же - это квантовая система с двумя возможными состояниями. Имеется ряд примеров таких квантовых систем: электрон, у ко­торого спин может быть равен либо +1/2 либо –1/2, атомы в кристалли­ческой решетке при некоторых условиях. Но, поскольку система квантовая, ее пространство состо­яний будет несравненно богаче. Математически кубит - это двумерное комплек­сное пространство.

В такой системе можно вы­полнять унитарные преобразования про­странства состояний системы. С точки зрения геометрии такие пре­образования - прямой аналог вращении и симметрий обычного трехмерного пространства. Согласно принципу суперпозиции вы можете складывать состояния, вычитать их, ум­ножать на комплексные числа. Эти состояния образуют фазовые пространства. При объединении двух сис­тем полученное фазовое пространство будет их тензорным произведением. Эво­люция системы в фазовом про­странстве описывается унитарными преобразованиями фазового про­странства.

Так вот, в квантовом компьюте­ре аналогичная ситуация. Он тоже работает с нулями и единицами. Но его функциональные элемен­ты реализуют действия прямо в фазовом пространстве некоторой квантовой системы - при помо­щи унитарных преобразований этого пространства.

Конечно, унитарные пре­образования не могут быть произ­вольными - они должны удовлет­ворять некоторым естественным ог­раничениям. Например, в случае обычной логики достаточно иметь три операции: конъюнкция, дизъ­юнкция, отрицание. Все можно ре­ализовать, используя только эти три операции. Точно так же и в кванто­вом случае есть некоторый набор операторов, действующих только на три бита, с помощью которых мож­но все реализовать. Там есть даже более тонкие результаты: можно ограничиться классическими опера­торами на нескольких битах, а кван­товые операторы будут действовать только на один бит. То есть класси­ческий набор операций {конъюнк­ция, дизъюнкция, отрицание} мож­но заменить на такой: {конъюнкция, дизъюнкция, квантовое отрицание}, где квантовое отрицание - это про­извольное унитарное преобразо­вание одного кубита.

Фазовое пространство КК есть тензорное произведение кубитов. Если в каждом кубите фиксирован базис (он будет состоять из двух векторов), то фазовое простран­ство - это комплексное линейное пространство, базис которого ин­дексирован словами из нулей и единиц. Таким способом двоич­ное слово на входе определяет базисный вектор.

Итак, вход - двоичное слово, определяющее один из базисных векторов. Сам же алгоритм - предписанная последовательность элементарных операторов. При­меняем эту последовательность к вектору на входе, в результате по­лучаем некоторый вектор на выхо­де.

Так вот, согласно квантовой механике (КМ), пока система эволюционирует под дей­ствием наших унитарных операто­ров, мы не можем сказать, в каком именно классическом состоянии она находится. То есть она находится в каком-то квантовом состоянии, но измеряем-то мы, когда общаемся с системой, все равно какие-то классические значения. Как это понима­ется в КМ? В фазовом пространстве фиксируется некоторый базис, и век­тор состояния разлагается по этому базису. Это математическая форма­лизация процедуры измерения в КМ. То есть если мы имеем дело с сис­темой, у которой «то ли спин влево, то ли спин вправо», и если мы все-таки посмотрим, какой спин, то мы получим одно из двух в любом слу­чае. А вот вероятности того, что мы получим тот или другой резуль­тат, - это как раз квадраты модуля коэффициентов разложения. КМ ут­верждает, что точно предсказать ре­зультат измерения нельзя, но веро­ятности возможных результатов вы­числить можно.

Вероятность возни­кает в процессе измерения. А пока система живет, для нас существен­но, что там есть сам этот вектор.

Другими словами, существенно, что система «находится одновременно во всех возможных состояниях». Как пишут многие авторы популяр­ных введений в KB, возникает со­вершенно чудовищный параллелизм вычислении: к примеру, в случае нашей системы из двух кубитов мы как бы оперируем одновременно со всеми возможными ее состояниями: 00, 01, 11, 10.

Чтобы интерпретировать ответ, надо заранее условиться, что какой-то бит - допустим, первый - это бит ответа. Пусть алгоритм проработал, у нас получился ка­кой-то вектор, не обязательно ба­зисный. Тогда мы можем сказать, что первый бит с некоторой вероят­ностью равен 1. И требование к ал­горитму такое: если ответ «да», то вероятность того, что первый бит равен 1, должна быть больше двух третей. А если ответ «нет», вероят­ность того, что будет ноль, должна быть тоже больше двух третей.

Задачи, реализуемые на КВ.

Известно два примера нетри­виальных задач, в которых KB дают радикальный выигрыш.

Первый из них - задача разло­жения целых чисел на простые мно­жители и, как следствие, вычисле­ния дискретного логарифма (ДЛ). Дальше речь пойдет именно о ДЛ.

Пусть у нас есть поле вычетов по модулю простого числа. В нем есть первообразные корни - такие вы­четы, чьи степени порождают все ненулевые элементы. Если задан такой корень и задана степень, то возвести в степень можно быстро (например, сначала возводим в квадрат, потом получаем четвертую сте­пень, и т. д.) Дискретный лога­рифм - это обратная задача. Дан первообразный корень и какой-то элемент поля; найти, в какую степень нужно возвести этот корень, чтобы получить данный элемент. Вот эта задача уже считается сложной. На­столько сложной, что ряд совре­менных криптографических систем основан на том предположении, что вычислить ДЛ за приемлемое время невозможно, если модуль - доста­точно большое простое число.

Так вот, для дискретного лога­рифма есть эффективный кванто­вый алгоритм. Его придумал Шор в конце 1994 года. Пос­ле его статьи и начался взрыв публи­каций по КВ. Независимо от него, Алексей Китаев из ИТФ им. Ландау построил квантовый алгоритм для этой и некоторых более общих за­дач [8]. Идеи у них были разные.

Шор использовал примерно такую идею, она существенно квантовая: рассмот­рим базис в фазовом пространстве. Он состоит из классических состояний. Но в линейном пространстве много базисов. Мы можем найти некий оператор, который эффективно строит другой базис; мы можем к нему перейти, сделать там какие-то вычисления, вернуться обратно и получить нечто совершенно отлич­ное от того, что мы имели бы в классическом базисе. Одна из воз­можностей использовать квантовость состоит в том, что мы строим какой-то странный базис, в нем что-то делаем, возвращаемся обратно и интерпретируем результат. Шор именно эту идею и реализовал. При­чем преобразование оказалось та­кое, которое и в физике, и в матема­тике имеет принци­пиальное значение - дискретное преобразование Фурье.