1  Введение

В последние годы интерес к тому, что называется <<квантовые компьютеры>>, необычайно возрос. Идея использования возможностей квантовой механики при организации вычислений выглядит всё более привлекательной, начаты экспериментальные работы в этой области.

Однако перспективы физической реализации квантовых компьютеров пока совершенно неясны. Скорее всего, это дело нескольких десятилетий. Основные достижения в этой области носят пока чисто математический характер.

Все компьютеры, начиная от так и не построенной <<аналитической машины>> Чарльза Бэббиджа¹ и кончая Cray'ем, основаны на одних и тех же принципах. С логической точки зрения компьютер состоит из битов (переменных, принимающих значения 0 или 1), а программа - это последовательность операций, каждая из которых использует небольшое число битов. Конечно, новые компьютеры работают быстрее старых, но прогресс в этом направлении имеет предел. Трудно предположить, что размер транзистора или аналогичного элемента будет меньше 10^-8 см (диаметр атома водорода), а рабочая частота - больше 10¹⁵ Гц (частота атомных переходов). Так что даже суперкомпьютеры будущего не смогут решать вычислительные задачи, имеющие экспоненциальную сложность. Рассмотрим, например, задачу о разложении целого числа x на простые множители. Очевидный способ - это попробовать разделить x на числа от 2 до Цx. Если число x имеет n знаков в двоичной записи, то придётся перебрать ~ Цx ~ 2^n/2 вариантов. Существует хитроумный алгоритм, решающий ту же задачу примерно за exp(сn^1/3) шагов (c = const). Даже в этом случае, чтобы разложить на множители число из миллиона знаков, не хватит времени жизни Вселенной. (Возможно, есть и более эффективные алгоритмы, но от экспоненты, по-видимому, избавиться не удастся.)

Существует, однако, другой способ ускорить процесс вычисления для некоторых специальных классов задач. Дело в том, что обычные компьютеры не используют всех возможностей, предоставляемых природой. Это утверждение может показаться слишком очевидным: в природе есть множество процессов, совершенно непохожих на операции с нулями и единицами. Можно попытаться использовать эти процессы для создания аналоговой вычислительной машины. Например, интерференция света может использоваться для вычисления преобразования Фурье. Однако в большинстве случаев выигрыш в скорости не является принципиальным, т. е. слабо зависит от размера устройства. Причина заключается в том, что уравнения классической физики (например, уравнения Максвелла) эффективно решаются на обычном цифровом компьютере. Что значит эффективно? Вычисление интерференционной картины может занять в миллионы раз больше времени, чем реальный эксперимент, потому что скорость света велика, а длина волны мала. Однако с увеличением размера моделируемой физической системы количество необходимых вычислительных операций растёт не слишком быстро - степенным, или, как принято говорить в теории сложности, полиномиальным образом. (Как правило, число операций пропорционально величине Vt, где V - объём, а t - время.) Таким образом, классическая физика слишком <<проста>> с вычислительной точки зрения.

Квантовая механика устроена в этом смысле гораздо интереснее. Рассмотрим, например, систему из n спинов. Каждый спин обладает двумя базисными состояниями (0 = << спин вверх >> и 1 = << спин вниз >> ), а вся система имеет 2ⁿ базисных состояний |x₁,...,x_nс (каждая из переменных x₁,...,x_n принимает значение 0 или 1). Согласно общим принципам квантовой механики, возможными состояниями системы являются также суперпозиции вида е_x1,...,xnc_x1,...,xn|x₁,...,x_nс, где c_x1,...,xn - комплексные числа, называемые амплитудами. Знак суммы здесь нужно понимать чисто формально. Суперпозиция является новым математическим объектом - вектором в 2ⁿ-мерном комплексном пространстве. Квадрат модуля амплитуды, |с_x1,...,xn|², равен вероятности обнаружить систему в базисном состоянии |x₁,...,x_nс при измерении значений переменных x_j. (Отметим, что такое измерение разрушает суперпозицию.) Следовательно, должно выполняться условие е_x1,...,xn|с_x1,...,xn|² = 1. Итак, общее состояние системы (т. е. суперпозиция) - это вектор единичной длины в 2ⁿ-мерном комплексном пространстве. Изменение состояния за определённый промежуток времени описывается унитарной матрицей размера 2ⁿ×2ⁿ. Если промежуток времени очень мал ( << (^h/_2p)/J, где J - энергия взаимодействия), то эта матрица устроена достаточно просто; каждый из её элементов можно легко вычислить, зная взаимодействие между спинами. Если же мы хотим узнать изменение состояния системы за большой промежуток времени, то придётся перемножать такие матрицы. Для этого требуется экспоненциально большое число операций. В настоящее время неизвестно никакого способа упростить данное вычисление и, скорее всего, моделирование квантовой механики является экспоненциально сложной вычислительной задачей. Однако то же самое утверждение можно сформулировать иначе: квантовая система эффективно <<решает>> сложную вычислительную задачу - моделирует саму себя.

Можно ли использовать квантовые системы для решения других вычислительных задач? Какова должна быть математическая модель квантового компьютера, в той же степени не зависящая от физической реализации, что и модели классических вычислений²? Эти вопросы, по-видимому, впервые были поставлены в книге Ю. И. Манина <<Вычислимое и невычислимое>> (1980 г.). Они обсуждались также в работах Р. Фейнмана и других авторов. В 1985 году Д. Дойч [] предложил конкретную математическую модель - квантовую машину Тьюринга, а в 1989 году - эквивалентную, но более удобную модель - квантовые схемы [,].

Что такое квантовая схема? Пусть в нашем распоряжении имеется N спинов, каждый из которых находится в отдельном ящичке и идеально изолирован от окружающего мира. В каждый момент времени мы можем выбрать, по нашему усмотрению, любые два спина и подействовать на них любой унитарной матрицей 4×4. Последовательность таких операций называется квантовой схемой. Каждая операция определяется парой номеров спинов и шестнадцатью комплексными числами, поэтому квантовую схему можно записать на бумаге. Это своего рода программа для квантового компьютера.

Чтобы использовать квантовую схему для вычисления функции³ F/colon Bⁿ® B^m, нужно уметь вводить входные данные, проделывать вычисления и считывать результат. Ввести в квантовый компьютер последовательность (x₁,...,x_n) нулей и единиц - значит приготовить начальное состояние |x₁,...,x_n,0,...,0с. (Объём входных данных n обычно меньше общего количества <<ячеек памяти>>, т. е. спинов, N. Оставшиеся ячейки заполняются нулями.) К начальному состоянию применяется квантовая схема, зависящая от решаемой задачи, но не от конкретных входных данных. В итоге возникает квантовое состояние

Мы только что сформулировали (опуская некоторые подробности) математическую модель квантового вычисления. Теперь естественно задать два вопроса.

1.Для каких задач квантовое вычисление дает выигрыш по сравнению с классическим?

2.Какую систему можно использовать для физической реализации квантового компьютера? (Это не обязательно должна быть система спинов.)

Физическая реализация квантового компьютера - чрезвычайно интересная, но сложная задача. Ещё несколько лет назад высказывались сомнения в её принципиальной разрешимости. Дело в том, что любое унитарное преобразование можно реализовать лишь с некоторой точностью. Кроме того, систему спинов или аналогичную квантовую систему нельзя полностью защитить от возмущений со стороны окружающей среды. Всё это должно приводить к погрешностям, которые будут накапливаться в процессе вычисления. Через L ~ d^-1 шагов (где d - точность каждого унитарного преобразования) вероятность ошибки станет порядка единицы. К счастью, эту трудность можно преодолеть, используя квантовые коды, исправляющие ошибки. В 1996 году П. Шор предложил схему коррекции ошибок в процессе квантового вычисления (fault-tolerant quantum computation), которая была вскоре усовершенствована. Окончательный результат состоит в следующем. Существует некоторое пороговое значение точности d₀, такое что при d < d₀ возможно сколь угодно длинное квантовое вычисление. Однако при d > d₀ ошибки накапливаются быстрее, чем их удаётся исправлять. По разным оценкам, d₀ лежит в интервале от 10^-2 до 10^-6 (точное значение зависит от характера возмущений и используемой схемы коррекции ошибок).

Итак, принципиальных препятствий для реализации квантового компьютера нет. Однако задача столь трудна, что её можно сравнить с задачей об управляемом термоядерном синтезе. В самом деле, необходимо удовлетворить нескольким почти несовместимым требованиям.

1.Элементы квантового компьютера - квантовые биты (спины или что-то подобное) - должны быть изолированы друг от друга и от окружающей среды.

2.Необходимо иметь возможность избирательного воздействия на пару квантовых битов. (Возможно, потребуется несколько типов воздействия на одну и ту же пару, описываемых различными унитарными операторами.)

3.Каждый из унитарных операторов должен быть реализован с точностью d < d₀ (см. выше).

4.Реализуемые операторы должны быть достаточно нетривиальны. Точнее говоря, они должны образовывать полный базис, чтобы любой другой оператор в определенном смысле выражался через них.

1. Отдельные атомы или ионы. Это первая и наиболее хорошо разработанная идея, она существует в нескольких вариантах. Для представления квантового бита можно использовать как обычные электронные уровни, так и уровни тонкой и сверхтонкой структуры. Имеется экспериментальная техника, позволяющая удерживать отдельный ион или атом в ловушке из постоянного магнитного или переменного электрического поля в течение длительного времени (порядка 1 часа). Ион можно <<охладить>> (т. е. погасить колебательное движение) при помощи лазерного луча. Подбирая длительность и частоту лазерных импульсов, можно приготовить произвольную суперпозицию основного и возбуждённого состояний. Таким образом, управлять отдельным ионом достаточно легко. В ловушку можно также поместить два или большее число ионов на расстоянии несколько микрон друг от друга и управлять каждым из них в отдельности. Однако организовать взаимодействие между ионами достаточно трудно. Для этой цели предложено использовать коллективные колебательные моды ионов (обычные механические колебания с частотой в несколько мегагерц). Другой способ (для нейтральных атомов): поместить атомы в отдельные электромагнитные резонаторы, связанные друг с другом (пока непонятно, как это реализовать технически). Наконец, третий способ: при помощи нескольких лазерных лучей можно создать периодический потенциал (<<оптическую решётку>>), удерживающий невозбуждённые атомы. При этом возможна ситуация, когда возбуждённые атомы могут свободно двигаться. Таким образом, возбуждая на короткое время один из атомов, мы заставляем его взаимодействовать с соседями. Это направление экспериментальной физики сейчас быстро развивается и, по-видимому, имеет большие перспективы.

2. Ядерный магнитный резонанс. В молекуле с несколькими различными ядерными спинами произвольное унитарное преобразование можно реализовать при помощи последовательности импульсов магнитного поля. Это было проверено экспериментально при комнатной температуре. Однако для приготовления начального состояния необходима температура < 10^-3K. Помимо трудностей с охлаждением, при такой температуре возрастают нежелательные взаимодействия молекул друг с другом. Кроме того, непонятно, как избирательно воздействовать на данный спин, если в молекуле есть несколько одинаковых спинов.

3. Системы сверхпроводящих гранул.

При сверхнизких температурах единственной степенью свободы микроскопической сверхпроводящей гранулы (диаметром в несколько сотен ангстрем) является её заряд. Он может изменяться на величину, кратную двум зарядам электрона (поскольку электроны в сверхпроводнике связаны в пары). Меняя внешний электрический потенциал, можно добиться такой ситуации, когда два зарядовых состояния будут иметь почти одинаковую энергию. Эти два состояния можно использовать в качестве базисных состояний квантового бита. Гранулы взаимодействуют между собой посредством джозефсоновских контактов и взаимной электрической ёмкости. Этим взаимодействием можно управлять. Основная трудность состоит в том, что нужно управлять каждой гранулой в отдельности, причем с высокой точностью. По-видимому, этот подход перспективен, но для его реализации потребуется создание новой технологии.

4. Анионы. Анионы - это особые возбуждения в двумерных квантовых системах, в частности, в двумерной электронной жидкости в магнитном поле. Один из авторов (А. К.) считает этот подход наиболее интересным (поскольку он же его и придумал []), поэтому опишем его более подробно.

Основной проблемой при создании квантового компьютера является необходимость реализации унитарных преобразований с точностью d < d₀ ~ 10^-2ё10^-6. Для этого, как правило, требуется контролировать параметры системы с ещё большей точностью. Однако можно представить ситуацию, когда высокая точность достигается автоматически, т. е. исправление ошибок происходит на физическом уровне. Примером являются двумерные системы с анионными возбуждениями.

Все частицы в трёхмерном пространстве являются либо бозонами, либо фермионами. Волновая функция бозонов не меняется при перестановке двух частиц, а волновая функция фермионов умножается на -1. В любом случае при возвращении каждой из частиц на прежнее место состояние системы не меняется. В двумерных системах возможно более сложное поведение. Прежде всего заметим, что речь пойдёт не об элементарных частицах типа электрона, а о возбуждениях, или дефектах в двумерной электронной жидкости. Такие возбуждения похожи на <<настоящие>> (т. е. элементарные) частицы, но обладают некоторыми необычными свойствами. Возбуждение может иметь дробный электрический заряд (например, 1/3 от заряда электрона). При движении одного возбуждения вокруг другого состояние окружающей их электронной жидкости меняется строго определённым образом, зависящим от типа возбуждений и от топологии пути, но не от конкретной траектории. В простейшем случае волновая функция домножается на число (e^2pi/3 для анионов в двумерной электронной жидкости в магнитном поле при факторе заполнения 1/3). Возбуждения с таким свойством называются абелевыми анионами.

Более интересны неабелевы анионы, которые пока не наблюдались экспериментально. (Теория предсказывает существование неабелевых анионов в двумерной электронной жидкости в магнитном поле при факторе заполнения 5/2.) При наличии нескольких неабелевых анионов состояние электронной жидкости является вырожденным, причем кратность вырождения экспоненциально зависит от числа анионов. Другими словами, существует не одно, а много состояний, которые могут образовывать произвольные квантовые суперпозиции. На такую суперпозицию нельзя никак воздействовать, не перемещая анионы, поэтому она идеально защищена от возмущений. Если обвести один анион вокруг другого, суперпозиция подвергнется определённому унитарному преобразованию. Это преобразование является абсолютно точным. (Ошибка может возникнуть, только если анион <<вырвется у нас из рук>> вследствие квантового туннелирования).

На первый взгляд, проект с использованием анионов выглядит наименее реалистично. Прежде всего, абелевы анионы не годятся для квантовых вычислений, а неабелевы ещё только предстоит найти в эксперименте. Для реализации квантового компьютера нужно контролировать каждую из частиц, которые будут двигаться на расстояниях порядка долей микрона друг от друга. Это чрезвычайно сложная техническая задача. Однако, с учётом высоких требований к точности, осуществить любой из перечисленных выше подходов ничуть не легче. Кроме того, идея топологического квантового вычисления, лежащая в основе подхода с анионами, может воплотиться каким-либо другим способом. Например, защищённая от возмущений квантовая степень свободы может возникнуть на конце <<квантовой проволоки>> (одномерного проводника с нечётным числом распространяющихся электронных мод, находящегося в контакте с трёхмерным сверхповодником).

Итак, идея квантового компьютера выглядит столь же заманчиво, сколь нереалистично. Наверное, так же воспринимался проект обычного компьютера во времена Чарльза Бэббиджа, изобретение которого было реализовано лишь сто лет спустя. Будем надеяться, что в наше время научно-технический прогресс идет быстрее, поэтому не придётся ждать так долго. Возможно, достаточно одной свежей идеи плюс несколько лет на разработку новой технологии...

2  Квантовая механика

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

2.1  Эксперимент с фотонами

2.1.1  Эксперимент

Сначала установим фильтр А. Будем считать, что входящий свет поляризован случайным образом. Интенсивность выходящего света будет равна половине интенсивности входящего. Все выходящие фотоны поляризованы горизонтально.

Функцию фильтра А нельзя рассматривать как <<сито>>, которое пропускает только горизонтально поляризованные фотоны. Если бы это было так, то лишь малая часть случайно поляризованных входящих фотонов была бы горизонтально поляризована, и свет ослаблялся бы гораздо сильнее при прохождении через фильтр.

Далее, установив фильтр С, мы видим, что интенсивность выходящих фотонов снижается до нуля, т.е. ни один из тризонтально поляризованных фотонов не может пройти через вертикальный фильтр. (Модель <<сита>> такое поведение фотонов объяснить ещё может).

Установим теперь фильтр В между А и С. При этом мы столкнемся с удивительным фактом: интенсивность света на экране перестанет быть нулевой. (Она будет равна одной восьмой от первоначальной инте ней внести).

Мы наблюдаем непредсказуемое явление. Исходя из классической точки зрения, добавление фильтра должно снизить количество проходящих фотонов. Как же это количество увеличилось?

2.1.2  Объяснение результатов эксперимента

Поскольку нас интересует только направление поляризации (величина вектора не важна), то вектор состояния будем считать единичным вектором, т.е. a² + b² = 1. В общем случае поляризация фотона может быть выражена как |aс+|bс, где а и b - комплексные числа, такие что |a|²+|b|² = 1. Замечание: выбор базиса для данного случая абсолютно произвольный - можно использовать любые два ортогональных единичных вектора.

Постулат измерения в квантовой механике утверждает, что любое устройство, измеряющее двумерную систему, обладает связанным ортогональным базисом, но отношению к которому производится квантовое измерение. Измерение состояния преобразует его в один из связанных базисных векторов измеряющего устройства. Вероятность того, что состояние измерено как базисный вектор |uс, равна квадрату нормы проекции первоначального состояния на базисный вектор |uс. Например, пусть нам дано устройство для измерения поляризации фотонов со связанным базисом |1с, |0с? тогда состояние y = |aс+|bс измеряется как |1с с вероятностью |a|², и как |0с с вероятностью |b|². Эта ситуация иллюстрируется на рис. .

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

Важно отметить, что измерение переводит квантовое состояние в то состояние, которое получилось в результате измерения, то есть, если измерение y = |aс+|bс имеет результатом |1с, то состояние y переходит в |1с, и второе измерение, но отношению к тому же базису, будет иметь результатом |1с с вероятностью равной 1. Таким образом, до тех пор, пока первоначальное состояние не стало одним из базисных векторов измеряющего устройства, процесс измерения будет изменять состояние. После измерения уже невозможно определить, каким было первоначальное состояние.

С точки зрения квантовой механики эксперимент с поляризацией можно объяснить следующим образом. Поляроид измеряет квантовое состояние фотонов по отношению к базису, содержащему вектор поляризации самого поляроида, и вектор, перпендикулярный вектору поляризации поляроида. Фотоны, прошедшие сквозь фильтр, имеют ту же поляризацию, что и сам фильтр, тогда как отражённые фотоны обладают поляризацией, перпендикулярной поляризации фильтра. Например, фильтр А измеряет поляризацию фотона по отношению к базисному вектору |1с. Все фотоны, прошедшие через фильтр A, обладают |1с-поляризацией. Те фотоны которые отражаются, имеют |0с-поляризацию.

Если учесть то, что источник света испускает фотоны с произвольной поляризацией, фильтр А будет пропускать 50% фотонов. Состояние прошедших фотонов будет |1с. Фильтр С будет измерять фотоны по отношению к |0с. Но состояние фотонов будет проектироваться на |0с с вероятностью равной 0, и поэтому ни один фотон не пройдёт фильтр С.

Наконец, фильтр В измеряет квантовое состояние по отношению к базису ([1/( Ц2)]|1с+|0с, [1/( Ц2)]|1с-|0с). Этот фильтр пропускает 50% фотонов, изменяя их состояние, поворотом поляризации на p/2. Таким образом каждый из фильтров задерживает половину фотонов, только одна восьмая часть первоначальных фотонов способна пройти через последовательные фильтры A, B и C.

2.2  Квантовые частицы

Для описания квантовой частицы применяют волновую функцию y([(r)/vec], t). y, вообще говоря, комплексная величина, физический смысл имеет |y|². dp = |y(x, t)|²dx - вероятность того, что при измерении координаты частицы получится значение из интервала (x, x+dx). |y|² - плотность распределения координаты квантовой частицы. Условие нормировки - т_-Ґ^+Ґ|y(x, t)|²dx = 1.

Шредингер постулировал уравнение на волновую функцию:

Часто уровнение Шредингера записывается через оператор H:

Эволюция состояний квантовых систем происходит согласно квантовому уравнению Шредингера. С состояниями квантовой системы (частицы) могут быть связаны информационные понятия и символы. Установление такого соответствия превращает квантовые системы в квантовые приборы. Последние можно рассматривать как квантовую элементную базу информационных систем. Эволюция состояний квантовых приборов представляет информационный процесс.

Таким образом, подчинение прибора уравнению Шредингера (и принципу суперпозиции) выделяет его в класс квантовых приборов. Управление прибором извне (внешним полем) происходит также согласно уравнению Шредингера. Очевидно выделенными оказываются квантовые частицы (системы) с двумя состояниями, на которые отображаются информационные системы, построенные на двоичной системе исчисления.

3  Базовые понятия квантовой теории информации

3.1  Кубиты

Обычный компьютер работает с состояниями из конечного числа битов. Каждый бит может находиться в одном из двух состояний 0 или 1. Состояние всей системы задаётся указанием значений всех битов. Поэтому множество состояний Bⁿ = {0,1}ⁿ конечно и имеет мощность 2ⁿ.

Квантовый компьютер работает с конечными наборами элементарных состояний, называемых q-битами (Quantum Bit, кубит). Каждый q-бит имеет два выделенных состояния (если считать q-биты спинами, то это состояния <<спин вверх>> и <<спин вниз>>). Квантовый бит - это вектор единичной длины в 2-мерном комплексном векторном пространстве, имеющем некоторый базис (|0с, |1с). Указание выделенных состояний для каждого q-бита системы задаёт не все возможные состояния системы, а только базисные. Возможны также любые линейные комбинации базисных состояний с комплексными коэффициентами. Базисные состояния мы будем обозначать |x₁,...,x_nс, где x_j О B, или |xс , где x О Bⁿ . Произвольное состояние системы может быть представлено в виде

Пространство состояний для такой системы - конечномерное (размерности 2ⁿ) пространство над полем комплексных чисел. Небольшое уточнение: если умножить вектор е_x c_x|xс на фазовый множитель e^if (f - вещественное), то получится физически неотличимое состояние. Таким образом, состояние квантового компьютера - это вектор единичной длины, заданный с точностью до фазового множителя.

Хотя квантовый бит может находиться в бесчисленном множестве суперпозиций состояний, путём измерения из него можно извлечь только один бит классической информации. Измерение кубита заменяет его состояние на базисное, что мы и наблюдали в эксперименте с поляризацией фотонов. Так как каждое измерение приводит только к одному из двух состояний, т.е. к одному из базисных векторов измерительного устройства, то, как и в классической теории, есть только два возможных исхода. Измерение меняет состояние, поэтому очевидно, что состояние не может быть измерено по двум различным базисам. Более того, квантовые состояния нельзя клонировать, т.е. кубит невозможно измерить двумя способами даже косвенно, например, скопировав кубит и измеряя его копию по базисам, отличным от первоначального.

3.2  Множества кубитов

Состояния кубита можно представить вектором в двумерном комплексном векторном пространстве, порождённом |0с и |1с. В классической физике возможные состояния системы из n частиц, в которой состояние каждой частицы задается вектором в 2-мерном пространстве, образуют 2n-мерное векторное пространство. Однако в квантовой системе общее пространство состояний гораздо больше: система из n кубитов имеет пространство состояний размерности 2ⁿ. Именно этот экспоненциальный рост пространства состояний в зависимости от числа частиц даёт экспоненциальное преимущество в скорости вычислений на квантовых компьютерах в сравнении с классическими.

В классической системе из n частиц пространства состояний каждой частицы соединяются декартовым произведением. Квантовые же состояния соединяются тензорным произведением. Пусть V и W - 2-мерные комплексные векторные пространства с базисами (v₁, v₂) и (w₁, w₂) соответственно. Их декартово произведение будет иметь базис (v₁, v₂, w₁, w₂). Порядок выбора элементов этого базиса произволен. В частности, размер пространства состояний множества классических частиц линейно возрастает с увеличением частиц, т.к. dim(X×Y) = dim(X)+dim(Y). Тензорное же произведение V и W имеет базис (v₁Дw₁, v₁Дw₂, v₂Дw₁, v₂Дw₂).

Итак, пространство состояний двух кубитов, у каждого из которых базис (|0с, |1с, имеет базис |00с, |01с, |10с,|11с).

В общем случае система n кубитов имеет 2n базисных векторов. Теперь мы видим экспоненциальный рост пространства квантовых состояний по мере увеличения числа частиц. Тензорное произведение Х ДY имеет размерность dim(X) ×dim(Y).

Состояние |00с+|11с является примером квантового состояния, которое нельзя представить состояниями отдельных кубитов. Другими словами, мы не можем найти такие a₁, a₂, b₁, b₂ что

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

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

3.3  Квантовые вычисления

Вычисления - это некоторые преобразования состояния квантовой системы. Для описания этих преобразований необходимо ввести некоторые определения и обозначения. Комплексное линейное пространство Bⁿ - множество всех n-мерных векторов, элементами которых являются комплексные числа. Число n называется размерностью пространства. Линейный оператор в линейном пространстве - это такое отображение A этого пространства в себя, что для любых векторов [(u)/vec], [(v)/vec] и для любого числа c выполняется:

• A([(u)/vec]+[(v)/vec]) = A[(u)/vec]+A([(v)/vec])
• A([(cv)/vec]) = cA([(v)/vec])

Унитарный оператор - это такой линейный оператор A, что для любого вектора [(u)/vec] справедливао соотношение |A([(u)/vec])| = |[(u)/vec]|

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

Классический случай:	Квантовый случай:
преобразования - это функции из Bn в Bn.	преобразования - это унитарные операторы, то есть операторы, сохраняющие длину вектора еx О Bn|cx|2.

4  Квантовые вентили

Важным следствием тот, что квантовые преобразования унитарны, является их обратимость. Т.е. квантовые вентили должны быть обратимыми. Что же касается классических вычислений, то, как показали Беннетт, Фредкин и Тоффоли, они всегда могут быть выполнены обратимо. Более подробно обратимые вычисления и энергетический подход к ним рассмотрены в <<Лекциях по вычислениям>> Фейнмана [Feynman 1996].

4.1  Простейшие квантовые вентили

Рассмотрим несколько полезных примеров преобразований 1-кубитового квантового состояния. В силу линейности, преобразования полностью определяются их действием на базисные векторы. Соответствующие матрицы преобразований приведены рядом справа.

I:

|0с®|0с |1с®|1с

(

1 0 0 1

)

X:

|0с®|1с |1с®|0с

(

0 1 1 0

)

Y:

|0с®-|1с |1с®|0с

(

0 1 -1 0

)

Z:

|0с®|0с |1с®-|1с

(

1 0 0 -1

)

Обозначения этих преобразований являются общепринятыми. I - тождественное преобразование, X - отрицание, Z - операция сдвига по фазе, а Y = ZX - комбинация последних двух. Проверка унитарности этих однобитовых вентилей элементарна:

4.2  Квантовый вентиль C_not

Преобразование C_not является унитарным, т.к. C^*_not = C_not и C_notC_not = I Заметим, что C_not нельзя представить как тензорное произведение двух однобитовых преобразований.

Удобно представлять преобразования квантового состояния графически, особенно в случаях, когда проводится несколько преобразований. Вентиль C_not обычно представляют в виде схемы, показанной на рис .

Незакрашенный кружок обозначает управляющий кубит, а знак X - условное отрицание подчинённого кубита. Некоторые авторы закрашенным кружком обозначают вентиль с управлением по сигналу 0, то есть переворот управляемого бита, когда управляющий бит находится в состоянии 0. В общем случае, управляющих кубитов может быть несколько. CONTROLLED-CONTROLLED-NOT отрицает последний кубит из трёх, но только в том случае, если оба первых кубита равны единице. Графически его можно представить, как показано на рис. .

Однокубитовые операции графически отображаются с помощью подписанных квадратов.

4.3  Преобразование Уолша-Адамара

Преобразование H имеет большое число важных применений. Действуя на |0с, H создает состояние суперпозиции |0с®[1/( Ц2)](|0с+|1с). Применяя H к n кубитам по отдельности, получим суперпозицию всех 2ⁿ возможных состояний. Преобразование W, которое применяет H ко всем n кубитам называется преобразованием Уолша-Адамара. Его можно определить рекурсивно:

4.4  Невозможность клонирования квантового состояния

Крайне важно понять, какой вид клонирования допускается, а какой нет. Клонировать неизвестное квантовое состояние невозможно. Однако известное квантовое состояние в принципе можно клонировать. Привести n частиц в запутанное состояние a|00ј0с + b|11ј1с из неизвестных состояний вполне возможно. Каждая из этих частиц будет вести себя одинаково при измерении в стандартном базисе (|00ј0с, |00ј01с, ... ,|11ј1с), чего нельзя было бы сказать, если бы измерения проводились в каком-то другом базисе.

4.5  Квантовые схемы

Комбинация бx|yс обозначает внутреннее (скалярное произведение) двух векторов. Например, б0|0с = 1, а б0|1с = 0. Комбинация |xбсy| - это внешнее произведение |xс и бy|.

Таким образом вентиль C_not может быть определен как

На рисунке x и y обозначают биты данных, s - их сумму по модулю 2, c - входной разряд переноса, а cў - выходной разряд переноса.

Вентиль Фредкина выполняет так называемый <<управляемый обмен>>, и определяется как

Дойч показал [Deutsch 1985], что возможно построить обратимые квантовые схемы для вычисления любой классической функции. Фактически можно ввести понятие универсальной квантовой машины Тьюринга [Bernstein and Vazirani 1997]. При этом надо иметь в виду, что для <<ленты>> машины Тьюринга должно быть предоставлено необходимое количество кубитов.

Любая классическая функция f с m входными и k выходными битами может быть вычислена на квантовом компьютере, то есть существует такая квантовая схема, которая вычисляет f. Рассмотрим (m+k)-битовое преобразование U_f:|xсy®|x, yДf(x)с, где Д обозначает побитовое <<исключающее-ИЛИ>. Квантовая схема U_f, определенная таким способом, является унитарной при любой функции f. Для тот, чтобы вычислить f(x) мы применяем U_f к |xс, тензорно умноженному на c k нулей |x, 0с. Поскольку f(x)Дf(x) = 0, то мы имеем U_fU_f = I. Графически преобразование U_f:|xсy ® |x, yДf(x)с показано на рис. .

Хотя вентили Т и F являются универсальными для классических логических схем, из них нельзя построить произвольные квантовые преобразования. Для того, чтобы осуществить произвольные унитарные преобразования с точностью до постоянного фазового множителя (общий фазовый сдвиг состояния не имеет физического смысла), необходимо рассмотреть вращения одного бита. Баренко и др. [Barenco et al. 1995] показали, что C_not вместе с полным набором однобитовых квантовых вентилей является универсальным набором. Достаточно иметь возможность выполнять следующие однобитовые преобразования

для всех 0 Ј a Ј 2p, а также C_not, чтобы получить универсальный набор квантовых вентилей. Такие преобразования являются ключевыми для использования преимуществ квантовых вычислений.

4.6  Квантовый параллелизм

Достоинство квантовых алгоритмов заключается в преимуществе квантового параллеллизма и запутанности. Так, большинство квантовых алгоритмов начинается с вычисления интересующей нас функции на суперпозиции всех значений. Все начинается с состояния |00ј0с n-кубитов. Далее применяется преобразование Уолша-Адамара W из для получения суперпозиции

Рассмотрим тривиальный пример использования CONTROLLED-CONTROLLED-NOT оператора Тоффоли Т для вычисления конъюнкции двух величин. На вход подадим суперпозицию всех возможных бит-комбинаций х и y, кроме х = 1, у = 1:

Результирующую суперпозицию можно рассматривать как таблицу истинности для конъюнкции или как граф функции. На выходе величины x, y и xЩy запутаны таким образом, что измерение результата даст одну строку таблицы истинности, или, что эквивалентно, точку графа функции. После измерения первые два кубита соответствуют входному значения, а третий кубит - соответствующему значению f.

На первый взгляд, здесь нет преимущества над классическим параллелизмом, поскольку при измерении можно получить только один результат, и к тому же мы не можем выбирать, какой результат мы получим. Суть любого квантового алгоритма - это способ, с помощью которого он манипулирует квантовым параллелизмом таким образом, чтобы желаемые результаты измерялись с большой вероятностью. Управление такого типа не имеет классического аналога и требует нетрадиционных приемов программирования. Вот пара приемов, кото- рые известны на сегодняшний день:

1. Усиление нужных нам выходных величин. Основная идея этого способа заключается в преобразовании состояния таким образом, чтобы интересующие нас величины имели большую амплитуду и, следовательно, более высокую вероятность быть измеренными.

2. Нахождение общих свойств всех значений f(x). Этот способ применен в алгоритме Шора, где используется квантовое преобразование Фурье для получения периода f.

5  Факторы, обуславливающие высокую производительность квантовых вычислителей

Одним из наиболее интересных свойств квантовых состояний, принципиально отличающих их от классических, является запутывание (entanglement) состояний, которое представляет собой когерентную суперпозицию состояний нескольких квантовых элементов, определяющее своеобразную нелокальную корреляцию этих состояний, возникающую при взаимодействии кубитов. Такие состояния получили название запутанных (entangled) состояний. Запутанные состояния играют очень важную роль в различных процессах передачи и обработки квантовой информации. Хотя понятие запутывания (entanglement) было введено еще Э.Шредингером под названием Verschrankung в 1935 году, большое внимание оно привлекло к себе лишь с 1993 года в связи с обнаруженной Ч.Беннеттом с сотрудниками теоретической возможностью использования его для передачи (телепортации) неизвестного для отправителя A квантового состояния двухуровневой системы к получателю B без реального перемещения самого элемента. Эта мысль стала далее основной для развития принципиально нового метода секретной передачи информации (криптографии). В последнее время квантовое явление телепортации активно обсуждается с точки зрения организации быстрых квантовых вычислений в многокубитовых системах. Перечень возможных приложений запутанного состояния уже достаточно велик.

Свойство запутывания квантовых состояний лежит и в основе многих квантовых алгоритмов. Оно является одним из корней ожидаемых успехов квантовых вычислительных процессов, поскольку открывает принципиально новые возможности кодирования информации, обеспечения помехозащищенности и более эффективного управления информацией. С ожидаемым экспоненциальным ускорением квантовых вычислений обычно связывают перспективы решения так называемой NP-полной (Nondeterministic polynomial-time complete) проблемы, то есть проблемы решения таких задач, для которых это решение очень трудно найти с помощью классических цифровых компьютеров, хотя очень просто это решение проверить. Такие задачи относятся к классу невычисляемых в том смысле, что они не могут быть решены на классических компьютерах за время, полиномиально зависящее от числа битов L, представляющих задачу. Квантовый алгоритм факторизации, предложенный П.Шором в 1994 г., позволяющий производить разложение n-значного числа на простые множители за время полиномиально зависящее от n, то есть с экспоненциальным ускорением по сравнению с самыми мощными классическими алгоритмами, стал одним из основных побуждений для интенсивного развития квантовых методов вычислений и изобретения алгоритмов, которые позволяют решать некоторые NP-проблемы. Считается, что алгоритм Шора уже сейчас позволит найти применение квантовым компьютерам весьма скромных размеров (десятки кубитов) для целей квантовой криптографии, квантовой коммуникации.

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

6  Физическая реализация квантового компьютера

6.1  Структура квантового компьютера

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

Основной его частью является квантовый регистр - совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты регистра должны быть приведены в основные базисные (булевые) состояния, то есть в состояние |0₁с, |0₂с, |0₃с,... |0_nс. Эта операция называется подготовкой начального состояния или инициализацией (initializing). Далее каждый кубит подвергается селективному воздействию, например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером, которое переведет основные базисные состояния определенных кубитов в неосновное состояние. При этом состояние всего регистра перейдет в суперпозицию базисных состояний вида |xс = |x₁. x₂, ј, x_nс, задающую бинарное представление числа n = е_{i = 1}ⁿn_i2ⁱ.

При вводе информации в квантовый компьютер состояние входного регистра, с помощью соответствующих импульсных воздействий преобразуется в когерентную суперпозицию базисных ортогональных состояний |y(0)с. В таком виде информация далее подвергается воздействию квантового процессора, выполняющего последовательность квантовых логических операций, определяемую унитарным преобразованием действующим на состояние всего регистра. К моменту времени t в результате преобразований исходное квантовое состояние становится новой суперпозицией вида |y(t)с = U(|y(0)с), которая и определяет результат преобразования информации на выходе компьютера.

Совокупность всех возможных операций на входе данного компьютера, формирующих исходные состояния, а также осуществляющих унитарные локальные преобразования, соответствующие алгоритму вычисления, способы подавления потери когерентности - так называемой декогерентизации (decoherence) квантовых состояний и исправления случайных ошибок, играют здесь ту же роль, что и <<программное обеспечение>> (software) в классическом компьютере.

6.2  Общие требования к элементной базе квантового компьютера

При выборе конкретной схемы любого квантового компьютера необходимо решить три вопроса:

1. выбрать физическую систему, представляющую требуемую систему кубитов
2. определить физический механизм, определяющий взаимодействие между кубитами, необходимое для выполнения двухкубитовых операций
3. определить способы селективного управления кубитами и измерения их состояния на выходе.

Все это, вместе взятое, аналогично аппаратному обеспечению (hardware) классического компьютера.

Считается, что для реализации полномасштабного квантового компьютера, превосходящего по производительности любой классический компьютер, на каких бы физических принципах он не работал, следует обеспечить выполнение следующих пяти основных требований:

1. Физическая система, представляющая полномасштабный квантовый компьютер, должна содержать достаточно большое число n > 10³ хорошо различаемых кубитов для выполнения соответствующих квантовых операций.
2. Необходимо обеспечить условия для приготовления входного регистра в исходном основном базисном состоянии, то есть возможность процесса инициализации.
3. Необходимо обеспечить максимальное подавление эффектов декогерентизации квантовых состояний, обусловленное взаимодействием системы кубитов с окружающей средой, что приводит к разрушению суперпозиций квантовых состояний и может сделать невозможной выполнение квантовых алгоритмов. Время декогерентизации должно по крайней мере в 10⁴ раз превышать время выполнения основных квантовых операций (времени такта). Для этого система кубитов должна быть достаточно слабо связана с окружением.
4. Необходимо обеспечить за время такта выполнение требуемой совокупности квантовых логических операций, определяющей унитарное преобразование U(t). Эта совокупность должна содержать определенный набор только двухкубитовых операций, типа <<контролируемое НЕ>> (аналог <<исключающего ИЛИ>> в классических компьютерах), осуществляющих операции поворота вектора состояния двух взаимодействующих кубитов в четырехмерном гильбертовом пространстве, и однокубитовых операций, осуществляющих поворот вектора состояния кубита в двухмерном гильбертовом пространстве, таких как операции <<НЕ>>, Адамара и некоторые другие.
5. Необходимо обеспечить с достаточно высокой надежностью измерение состояния квантовой системы на выходе. Проблема измерения конечного квантового состояния является одной из основных проблем квантовых вычислений.

6.3  Основные направления в развитии элементной базы квантового компьютера

1. Использование для модельной реализации квантовых компьютеров в качестве кубитов уровней энергии ионов, захваченных ионными ловушками, создаваемыми в вакууме определенной конфигурацией электрического поля в условиях лазерного охлаждения их до микрокельвиновых температур.

   Взаимодействие между заряженными ионами в одномерной цепочке этих ловушек осуществляется посредством возбуждения их коллективного движения, а индивидуальное управление ими с помощью лазеров инфракрасного диапазона. Первый прототип квантового компьютера на этих принципах был предложен австрийскими физиками И.Цираком и П.Цоллером в 1995 году. В настоящее время интенсивные экспериментальные работы ведутся в Los Alamos Natl.Lab. (LANL) и Natl.Inst.Stand.Tech. (NIST) в США. Преимущество такого подхода состоит в сравнительно простом индивидуальном управлении отдельными кубитами. Основными недостатками этого типа квантовых компьютеров являются необходимость создания сверхнизких температур, обеспечение устойчивости состояний ионов в цепочке и ограниченность возможного числа кубитов значением n < 40.

2. Использование в качестве кубитов атомов с ядерными спинами с I = 1/2, принадлежащих молекулам органических жидкостей с косвенным скалярным взаимодействием между ними и методов ядерного магнитного резонанса (ЯМР) для управления кубитами.

   Первые предложения былисформулированы в 1997 году в Massach.Inst.Tech. (MIT), LANL в США и в Clarendon Lab. в Оксфорде в Великобритании и в этом же году были выполнены первые эксперименты на ядерных спинах двух атомов водорода H в молекулах 2,3-дибромотиофена SCH:(CBr)₂:CH и на трех ядерных спинах - одном в атоме водорода H и двух в изотопах углерода C в молекулах трихлорэтилена CCl₂:CHCl (рис. ).

   Рис. 10: Кубит на молекуле трихлорэтилена

   В ансамблевом ядерном магнитнорезонансном квантовом компьютере кубитами выступают спины - ядер водорода (протоны) и углерода С в молекулах жидкости. В молекуле трихлорэтилена спины ядер двух атомов С и одного протона образуют три кубита. Два атома С химически неэквивалентны и поэтому имеют различные частоты ядерного магнитного резонанса w_A и w_B в заданном внешнем постоянном магнитном поле B₀, протон будет иметь третью резонансную частоту w_C. Подавая импульсы внешнего переменного магнитного поля на различных частотах мы селективно управляем квантовой эволюцией любого из этих спинов (выполняем однокубитовые вентили). Между спинами ядер, разделенных одной химической связью H-С и С-С, имеется магнитное контактное взаимодействие, что позволяет построить двухкубитовые вентили.

   Макроскопически большое число ( 1⁰20) молекул в пробирке импульсного ЯМР спектрометра, запрограммированного на выполнение квантового алгоритма на трехкубитовом компьютере представляет собой ансамбль работающих параллельно квантовых компьютеров. <<Ансамблевость>> компьютера в данной ситуации позволяет решить трудные проблемы инициализации компьютера (т.е. приведения всех кубитов в состояние <<0>> перед вычислением) и измерения состояния кубитов по завершении процесса вычислений. Состояния некоторого кубита в конечном состоянии определяется путем наблюдения знака (фазы) линии резонансного поглощения: в случае |0с наблюдается, например, линия поглощения, а при ket1 - излучения.

   Важным здесь является то, что для селективного воздействия на ядерные спины молекулы необходимо чтобы они достаточно различались по резонансным частотам. Позднее были осуществлены квантовые операции также в цитозине, хлороформе, аланине и других жидкостях с числом спинов-кубитов n = 3,5,6,7.

   Главным преимуществом такого компьютера является то, что огромное число практически независимых молекул-компьютеров жидкости действует, обеспечивая тем самым возможность управления ими с помощью хорошо известных в технике ядерного магнитного резонанса (ЯМР) операций над макроскопическим объемом жидкости. Последовательности радиочастотных импульсов, выполняющие в этом случае роль определенных квантовых логических вентилей, осуществляют глобальные унитарные преобразования состояний соответствующих ядерных спинов для всех молекул-компьютеров. Индивидуальное обращение к отдельным кубитам заменяется одновременным обращением к соответствующим кубитам во всех молекулах большого ансамбля. Компьютер такого рода получил название ансамблевого (bulk-ensemble quantum computer) ЯМР квантового компьютера. Замечательно, что он может в принципе работать при комнатной температуре. Время декогерентизации квантовых состояний ядерных спинов в жидкости достаточно велико. Оно может составлять несколько секунд.

   В области ЯМР квантовых компьютеров на органических жидкостях к настоящему времени достигнуты наибольшие успехи. Они связаны в основном с хорошо развитой импульсной техникой ЯМР-спектроскопии, обеспечивающей выполнение различных операций над когерентными суперпозициями состояний ядерных спинов и с возможностью использования для этого стандартных ЯМР-спектрометров, работающих при комнатных температурах.

   Экспериментально на ЯМР квантовых компьютерах были осуществлены алгоритм Гровера поиска данных, квантовое фурье-преобразование, квантовая коррекция ошибок, квантовая телепортация, квантовое моделирование и другие операции. Основными ограничениями для этого направления являются:

   • Смешанный характер исходного состояния кубитов, что требует использования определенных неунитарных операций для приготовления начального состояния.
   • Измеряемый на выходе сигнал экспоненциально убывает с ростом числа кубитов n, что требует экспоненциального роста чуствительности измеряющего оборудования.
   • Число ядерных спинов-кубитов в отдельной молекуле с достаточно различающимися резонансными частотами n ограничено.
   • Однокубитовые и двукубитовые квантовые операции являются относительно медленными.

   Эти ограничения приводят к тому, что ЯМР квантовые компьютеры на молекулах органической жидкости не смогут иметь число кубитов, значительно больше десяти. Их следует рассматривать лишь как прототипы будущих квантовых компьютеров, полезные для отработки принципов квантовых вычислений и проверки квантовых алгоритмов.

3. Использование в качестве кубитов зарядовых состояний куперовских пар в квантовых точках, связанных переходами Джозефсона, предложенное Д.В.Авериным в 1998 году.

   Первый твердотельный кубит на этих принципах был создан в NEC Fund.Res.Lab. в Японии в 1999 году. Полагают, что перспективность этого направления состоит в возможности создания электронных квантовых устройств высокой степени интеграции на одном кристалле, при этом для управления кубитами не потребуются громоздкие лазерные или ЯМР установки. Однако на пути создания квантовых компьютеров еще остается нерешенными ряд важных проблем и, в частности, проблема устойчивости состояний кубитов и декогерентизация. Поисковые работы квантовым компьютерам на высокотемпературных сверхпроводниках в России ведутся в Институте теоретической физики им. Л.Д.Ландау РАН.

   Перечисленные выше три в разной степени реализованных направления в развитии элементной базы квантовых компьютеров дополнились еще двумя широко обсуждаемыми пока на уровне предложений направлениями:

4. Важные перспективы открываются перед направлением твердотельных ЯМР квантовых компьютеров.

   Для этого в 1998 г. австралийским физиком Б.Кейном было предложено использовать в качестве кубитов обладающие ядерным спином 1/2 донорные атомы с изотопами P₃1, которые имплантируются в кремниевую структуру. Это предложение, которое пока остается нереализованным, открывает потенциальную возможность создания квантовых вычислительных устройств с практически неограниченным числом кубитов.

   В рассматриваемом варианте предполагается использовать температуры достаточно низкие для того, чтобы электроны донорных атомов занимали только нижнее спиновое состояние в магнитном поле. В полях B і 2 Тл это соответствует температурам T Ј 0.1K, гораздо более низким, чем температура вымораживания электронных состояний доноров, которые будут поэтому оставаться в неионизированном основном орбитальном s-состоянии.

   Каждый донорный атом с ядерным спином - кубит в полупроводниковой структуре предполагается расположить регулярным образом с достаточной точностью под <<своим>> управляющим металлическим затвором (затвор A), отделенным от поверхности кремния тонким диэлектриком (например, окисью кремния толщиной порядка нескольких нанометров). Эти затворы образуют линейную решетку произвольной длины (рис. ).

   Рис. 11: Схематическое изображение двух ячеек полупроводниковой структуры модели Кейна, l_A ~ 10нм, l ~ 20нм, c ~ 20нм

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

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

   Для того, чтобы исключить взаимодействие ядерных спинов доноров с окружением сам кремний и окисел кремния должен быть достаточно хорошо очищенЫ от изотопа Si₂₉, обладающего спином I = 1/2, который содержится в количестве 4,7% в естественном кремнии. Возможно использование и других материалов.

   Были предложены и несколько вариантов измерения состояний кубитов, но ни один из них пока не реализован, а также ансамблевые варианты твердотельных ЯМР квантовых компьютеров. В России работы в этом направлении ведутся в Физико-технологическом институте РАН.

5. Еще одним из интересных направлений является использование в качестве состояний кубитов двух спиновых или двух зарядовых электронных состояний в полупроводниковых наноструктурах, в частности в квантовых точках, формируемых в гетероструктурах типа AlGaAs/GaAs, либо с спин-спиновым обменным, либо с электрическим взаимодействием между кубитами. Индивидуальное управление кубитами в случае спиновых электронных состояний предполагается осуществлять используя так называемые спиновые клапаны, а для измерения состояния отдельного спина - спиновые фильтры из ферромагнитных туннельных барьеров. В случае зарядовых состояний предполагается управлять кубитами либо лазерами инфракрасного диапазона, либо с помощью электрического воздействия на высоту барьера, разделяющего кубиты. Активные поисковые исследования в этом направлении проводятся исследовательских центрах IBM. Работа по моделированию полупроводниковых кубитовых наноструктур из квантовых точек в России ведется в Физико-технологическом институте РАН.

Отметим, что среди других направлений рассматриваются также и такие пока еще слабо разработанные варианты как использование квантовых электродинамических полостей для фотонов и фотонных кристаллов; электронов, плавающих на поверхности жидкого гелия; системы двух одномерных квантовых каналов для электронных волн (квантовые проволоки); системы ядерных спинов в двумерном электронном газе в условиях квантового эффекта Холла и некоторые другие.

Из рассмотренных выше пяти основных направлений наиболее привлекательными с точки зрения создания суперкомпьютеров в настоящее время представляются три пока нереализованных конкурирующих направления: полупроводниковые ЯМР квантовые компьютеры, квантовые компьютеры на переходах Джозефсона и квантовые компьютеры на квантовых точках. Все они допускают произвольно большое число кубитов и для них существуют уже многие наработанные приемы микро- и нанотехнологии создания полупроводниковых и сверхпроводниковых интегральных схем. Все три направления предполагают наличие генераторов управляющих импульсов, использование низких температур и, следовательно, использование совсем не миниатюрных обслуживающих систему кубитов устройств, а в случае твердотельного ЯМР квантового компьютера еще и использование магнита.

Однако для твердотельного ЯМР квантового компьютера можно указать на ряд важных преимуществ:

• Ядерные спины сами по себе являются кубитами.
• При низких температурах они характеризуются очень большими временами релаксации (и, соответственно, временами декогерентизации) по сравнению с электронными спинами.
• Технологические структуры нанометрового масштаба в полупроводниковых ЯМР квантовых компьютерах предназначаются не для создания самих кубитов, как в случае сверхпроводниковых устройств, а лишь для задач управления кубитами и измерения их состояний.

В настоящее время состояние современной высокоточной технологии и технологии высокочистых материалов уже сейчас позволяют приступить к экспериментальным работам по созданию элементов полупроводниковых ЯМР квантовых компьютеров. Можно ожидать, что в ближайшие годы уже будут созданы простейшие фрагменты или прототипы такого компьютера. Создание многокубитовых твердотельных структур - более далекая перспектива. Она потребует привлечения многих технологических и схемотехнических достижений современной микро- и наноэлектроники, а также разработки программ математического моделирования физических процессов, и в частности процессов декогерентизации, в многокубитовых квантовых системах.

6.4  Новое в области построения квантовых вычислителей

6.4.1  Первый сверхпроводящий квантовый бит

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

Центральный островок (box) соединен туннельными джозефсоновскими контактами с резервуаром в виде алюмиевого кольца. Измерительный зонд присоединен к островку через "толстый" слой окисла, сопротивление этого контакта очень велико (2МОм), чтобы вносить малые возмущения в состояние островка. А сам этот островок и является собственно кубитом, два состояния которого есть наличие |1с или отсутствие |0с избыточной куперовской пары. То, что это именно квантовый бит, а не просто бит, означает возможность существования смешанных состояний, когда на островке находится нецелое число куперовских пар.

На рис. 13 представлена зависимость электростатической энергии системы E_C(n-Q_t/e)² для состояний от полного заряда, индуцируемого электродом затвора (dc gate), здесь E_C - энергия зарядки островка одним электроном. Для наглядности квадратичная составляющая энергии вычтена. Энергетические зависимости пересекаются в точке Qt/e = 1, однако из-за антикроссинга термов в точке пересечения энергии расходятся на величину джозефсоновской энергии E_j. При подаче короткого импульса на электрод (pulse gate) происходит переход из исходного состояния |1с в состояние |0с. Пропорции смешивания этих состояний определяются длительностью импульса. Диагностирование смешанного состояния проводилось с помощью измерения тока через зонд. При этом время выхода куперовской пары в контакт составляло всего 1нс (по оценкам). Поэтому экспериментаторам пришлось прибегнуть к некоторым хитростям, чтобы все-таки провести измерение. В отсутствие измерительного электрода, который не нужен для работы кубита, время жизни состояния на островке оценивается в десятки и сотни секунд.

6.4.2  Квантовый бит на атомно-силовом микроскопе

Berman et.al. (Los Alamos Nat. Lab) предлагают использовать магнитный атомно-силовой микроскоп с крошечным (4нм) магнитом на острие кантилевера. Оказывается, что такой микроскоп позволяет измерять чистое состояние отдельного ядерного спина (<<спин вверх>> или <<спин вниз>>). Система спинов помещается во внешнее постоянное магнитное поле, созданное сверхпроводящим магнитом. Измерение состояния выделенного кубита производится при подведении к нему острия микроскопа и включении радиочастотного (РЧ) электромагнитного поля на частоте ЯМР. Для повышения чувствительности микроскопа амплитуда этого поля промодулирована с резонансной частотой колебаний кантилевера.

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

6.4.3  Квантовый компьютер на жидком гелии

Локализация электронов в плоскости двумерного электронного газа обеспечивается отдельными электродами, размещенными под слоем жидкого гелия. Причем, электроны, рассыпанные по поверхности гелия, сами скатываются к этим электродам, их не надо специально размещать над ними. Операции над отдельными кубитами выполняются с помощью электромагнитных импульсов, переводящих электроны с нижнего на верхний уровень и наоборот. Доступ к отдельным кубитам осуществляется подачей напряжения на электрод, которое изменяет энергетический зазор между уровнями в данном кубите, иными словами, либо вводит в резонанс с электромагнитной волной, либо выводит из резонанса. Взаимодействие соседних кубитов обеспечивается кулоновскими силами между электронами.

Очень интересно задуман процесс считывания результата. При этом надо было определить, в каком состоянии находится тот или иной кубит, т.е. узнать, на каком уровне сидит электрон, на нижнем или на верхнем. Это можно сделать, если разместить над электроном электрод и подать на него положительное напряжение. Электрон с верхнего уровня гораздо быстрее протуннелирует на этот электрод, чем электрон с нижнего уровня.

Авторы рассмотрели процессы декогеренизации в системе. Главным из них является возбуждение электронами, находящимися на верхнем уровне, колебаний поверхности гелия (ripplon). Приложение достаточно сильного магнитного поля может сделать этот процесс очень маловероятным.

6.4.4  Квантовый компьютер на электронных волнах

Действительно, одномерные квантовые каналы (квантовые проволоки) для электронов часто называют волноводами. И это вполне правильно до некоторого момента: фотоны не взаимодействуют, а электроны взаимодействуют кулоновским образом. Для достижения полной аналогии с фотонами в канале должен быть только один электрон. Но это как раз можно сейчас устроить с помощью т.н. одноэлектронных насосов (electron pumps). Кубит представляет собой два состояния электрона: электрон находится в одном канале, либо в другом. Если каналы соприкасаются друг с другом на некотором протяжении, то электрон полностью переходит из одного канала в другой. Это и есть операция изменения состояния отдельного кубита. Операцию взаимодействия кубитов можно организовать с помощью соприкосновения каналов, в которых находятся разные электроны. Кулоновское взаимодействие изменяет фазу волновой функции.

7  Исправление квантовых ошибок

Стин [Stean 1998] оценил, что декогерентность любой из предложенных систем на 7 порядков больше той, что необходима для нормальной работы алгоритма Шора с числами, содержащими 130 десятичных разрядов. Однако добавление так называемой коррекции ошибок снижает влияние декогерентности и снова дает надежды на осуществление алгоритма Шора для больших чисел.

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

Квантовая коррекция ошибок должна воссоздавать точно некоторое квантовое состояние. Трудности здесь связаны с невозможностью клонирования или копирования. Однако, оказывается, эти трудности преодолимы, и квантовые ошибки все-таки можно исправлять.

7.1  Описание ошибок

Для больших квантовых регистров ошибки так же выражаются линейными комбинациями унитарных операторов ошибок E_i. Эти операторы являются тензорными произведениями операторов ошибок отдельных кубитов (J, X, Y, Z) или более общих многокубитовых операторов ошибок. В любом случае, ошибку можно записать как е_i e_iE_i|yс.

7.2  Восстановление состояния

Теперь рассмотрим квантовый случай. Во-первых, состояние регистра может быть суперпозицией базисных векторов. Во-вторых, ошибка может быть линейной комбинацией операторов корректируемых ошибок E_i При этом оказывается, что восстановление закодированного квантового состояния всё же является возможным.

Зададим корректирующий код C и преобразование выделения ошибки S_c. Таким образом, n-битное квантовое состояние |yс закодировано в (n+k)-битном квантовом состоянии |yс = C|yс.

Допустим, что декогентность приводит к состоянию е_i e_iE_i|yс для некоторой комбинации корректируемых ошибок E_i. Первоначальное состояние |yс можно восстановить следующим образом:

1. Применяем оператор выделения признака ошибки S_c к квантовому состоянию с добавлением достаточного количества вспомогательных |0с кубитов

   Sc ж и е i  eiEi|yс ц ш Д|0с = е i  ei( Ei|yсД|iс).

   Квантовый параллелизм дает суперпозицию различных ошибок (индексируемых через i).
2. Измеряем компоненту |iс результата. Это даст некоторую (случайную) величину i₀ и спроектирует состояние на

   е i0  |y, i0с.

3. Применяем обратное преобразование для ошибки E^-1_i0 к первым n+k кубитам состояния е_i0|y, i₀с, чтобы получить исходное состояние |yс.

Заметим, что на шаге 2 суперпозиция нескольких ошибок проектируется на отдельную ошибку. Следовательно, для шага 3 необходимо только одно обратное преобразование ошибки.

7.3  Пример коррекции ошибок

Рассмотрим квантовый бит |yс = [1/( Ц2)](|0с-|1с), кодируемый следующим образом:

Footnotes:

¹ Бэббидж начал работу над проектом <<аналитической машины>> в 1833 году. Преполагалось, что, в отличие от уже существовавших в то время вычислительных устройств, это будет универсальный компьютер. Бэббидж посвятил разработке компьютера всю жизнь, но ему так и не удалось осуществить свою мечту. (Более простая, но неуниверсальная <<разностная машина>> была построена частично, но проект был вполне реалистичен - в 1991 году машина была полностью воспроизведена по чертежам Бэббиджа.)

² Наиболее известной математической моделью обычного компьютера является машина Тьюринга. Большинство моделей полиномиально эквивалентны друг другу, т. е. задача, разрешимая за L шагов в одной модели, разрешима за cL^k шагов в другой модели, где c и k - константы.

³ Любая вычислительная задача может быть представлена в таком виде. Например, если мы хотим решать задачу о разложении целого числа x на простые множители, то (x₁,...,x_n) = x (в двоичной записи), а F(x) - список простых множителей (в некоторой двоичной кодировке).

⁴ Если не вдаваться в тонкости, квантовый алгоритм - это то же самое, что квантовая схема. Отличие состоит в том, что схема определена для задачи фиксированного размера (n = const), а алгоритм определён для всех n сразу.