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