Классический компьютер состоит, грубо говоря, из некоторого числа битов, с которыми можно выпол¬нять арифметические операции. Основным элементом кванто¬вого компьютера (КК) являются квантовые биты, или кубиты (от Quantum Bit, qubit). Обычный бит - это классическая система, у которой есть только два возмож¬ных состояния. Можно сказать, что пространство состояний бита - это множество из двух элемен¬тов, например, из нуля и единицы. Кубит же - это квантовая система с двумя возможными состояниями. Имеется ряд примеров таких квантовых систем: электрон, у ко¬торого спин может быть равен либо +1/2 либо –1/2, атомы в кристалли¬ческой решетке при некоторых условиях. Но, поскольку система квантовая, ее пространство состо¬яний будет несравненно богаче. Математически кубит - это двумерное комплек¬сное пространство.
В такой системе можно вы¬полнять унитарные преобразования про¬странства состояний системы. С точки зрения геометрии такие пре¬образования - прямой аналог вращении и симметрий обычного трехмерного пространства. Согласно принципу суперпозиции вы можете складывать состояния, вычитать их, ум¬ножать на комплексные числа. Эти состояния образуют фазовые пространства. При объединении двух сис¬тем полученное фазовое пространство будет их тензорным произведением. Эво¬люция системы в фазовом про¬странстве описывается унитарными преобразованиями фазового про¬странства.
Так вот, в квантовом компьюте¬ре аналогичная ситуация. Он тоже работает с нулями и единицами. Но его функциональные элемен¬ты реализуют действия прямо в фазовом пространстве некоторой квантовой системы - при помо¬щи унитарных преобразований этого пространства.
Конечно, унитарные пре¬образования не могут быть произ¬вольными - они должны удовлет¬ворять некоторым естественным ог¬раничениям. Например, в случае обычной логики достаточно иметь три операции: конъюнкция, дизъ¬юнкция, отрицание. Все можно ре¬ализовать, используя только эти три операции. Точно так же и в кванто¬вом случае есть некоторый набор операторов, действующих только на три бита, с помощью которых мож¬но все реализовать. Там есть даже более тонкие результаты: можно ограничиться классическими опера¬торами на нескольких битах, а кван¬товые операторы будут действовать только на один бит. То есть класси¬ческий набор операций {конъюнк¬ция, дизъюнкция, отрицание} мож¬но заменить на такой: {конъюнкция, дизъюнкция, квантовое отрицание}, где квантовое отрицание - это про¬извольное унитарное преобразо¬вание одного кубита.
Фазовое пространство КК есть тензорное произведение кубитов. Если в каждом кубите фиксирован базис (он будет состоять из двух векторов), то фазовое простран¬ство - это комплексное линейное пространство, базис которого ин¬дексирован словами из нулей и единиц. Таким способом двоич¬ное слово на входе определяет базисный вектор.
Итак, вход - двоичное слово, определяющее один из базисных векторов. Сам же алгоритм - предписанная последовательность элементарных операторов. При¬меняем эту последовательность к вектору на входе, в результате по¬лучаем некоторый вектор на выхо¬де.
Так вот, согласно квантовой механике (КМ), пока система эволюционирует под дей¬ствием наших унитарных операто¬ров, мы не можем сказать, в каком именно классическом состоянии она находится. То есть она находится в каком-то квантовом состоянии, но измеряем-то мы, когда общаемся с системой, все равно какие-то классические значения. Как это понима¬ется в КМ? В фазовом пространстве фиксируется некоторый базис, и век¬тор состояния разлагается по этому базису. Это математическая форма¬лизация процедуры измерения в КМ. То есть если мы имеем дело с сис¬темой, у которой «то ли спин влево, то ли спин вправо», и если мы все-таки посмотрим, какой спин, то мы получим одно из двух в любом слу¬чае. А вот вероятности того, что мы получим тот или другой резуль¬тат, - это как раз квадраты модуля коэффициентов разложения. КМ ут¬верждает, что точно предсказать ре¬зультат измерения нельзя, но веро¬ятности возможных результатов вы¬числить можно.
Вероятность возни¬кает в процессе измерения. А пока система живет, для нас существен¬но, что там есть сам этот вектор.
Другими словами, существенно, что система «находится одновременно во всех возможных состояниях». Как пишут многие авторы популяр¬ных введений в KB, возникает со¬вершенно чудовищный параллелизм вычислении: к примеру, в случае нашей системы из двух кубитов мы как бы оперируем одновременно со всеми возможными ее состояниями: 00, 01, 11, 10.
Чтобы интерпретировать ответ, надо заранее условиться, что какой-то бит - допустим, первый - это бит ответа. Пусть алгоритм проработал, у нас получился ка¬кой-то вектор, не обязательно ба¬зисный. Тогда мы можем сказать, что первый бит с некоторой вероят¬ностью равен 1. И требование к ал¬горитму такое: если ответ «да», то вероятность того, что первый бит равен 1, должна быть больше двух третей. А если ответ «нет», вероят¬ность того, что будет ноль, должна быть тоже больше двух третей.