научная статья по теме КВАНТОВЫЕ КОМПЬЮТЕРЫ: ДОСТИЖЕНИЯ, ТРУДНОСТИ РЕАЛИЗАЦИИ И ПЕРСПЕКТИВЫ Электроника. Радиотехника

Текст научной статьи на тему «КВАНТОВЫЕ КОМПЬЮТЕРЫ: ДОСТИЖЕНИЯ, ТРУДНОСТИ РЕАЛИЗАЦИИ И ПЕРСПЕКТИВЫ»

МИКРОЭЛЕКТРОНИКА, 2011, том 40, № 4, с. 243-255

КВАНТОВАЯ ИНФОРМАТИКА

УДК 530.145;621.382

КВАНТОВЫЕ КОМПЬЮТЕРЫ: ДОСТИЖЕНИЯ, ТРУДНОСТИ РЕАЛИЗАЦИИ И ПЕРСПЕКТИВЫ

© 2011 г. Ю. И. Богданов, |К. А. Валиев|, А. А. Кокин

Физико-технологический институт Российской АН E-mail: bogdanov@ftian.ru Поступила в редакцию 15.09.2010 г.

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

1. ВВЕДЕНИЕ

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

Важным примером, на котором можно продемонстрировать радикальное преимущество квантовых алгоритмов над классическими, является так называемая задача факторизации, связанная с раз-

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

Наилучший известный на сегодня классический алгоритм факторизации некоторого числа (так называемый метод решета числового поля — general number field sieve) требует для реализации следующее число операций:

Zclass « exp ((64/9f n13 (ln (n)f), (1)

где п = к 1п (10) — число двоичных знаков, а к — число соответствующих десятичных знаков, задающих это число.

Сравнение формул (1) и (2) показывает, что алгоритм Шора превращает экспоненциально сложный алгоритм в алгоритм полиномиальной сложности. Например, современный классический суперкомпьютер петафлопсного диапазона (1015 операций с плавающей запятой в секунду) позволяет разложить число с к = 500 десятичными знаками за 5 миллиардов лет. Ту же задачу квантовый компьютер мегагерцового диапазона (1 млн. операций в секунду) решает за 18 с. Аналогично, для числа с к = 1000 десятичными знаками трудоемкость классического алгоритма составля-

Квантовый алгоритм факторизации, предложенный П. Шором в 1994 г. требует выполнения числа операций, выражаемым следующей формулой [8]

(2)

ет 4 х 1020 лет, а квантового — 84 с. Таким образом, квантовые компьютеры, когда они будут созданы, позволят решать задачи, недоступные никаким классическим компьютерам.

Давно было известно, что квантовые задачи являются алгоритмически очень сложными для вычислений на компьютере. Из этого, на первый взгляд, негативного наблюдения Фейнман в 1982 г. сумел сделать позитивный вывод [9, 10]. Раз Природа с успехом решает эти задачи, то может быть и мы могли бы использовать квантовые системы в качестве некоторой новой элементной базы для

Equant ~ П2ln (n)ln (ln (n)).

вычислений. Компьютеры, основанные на квантовых логических элементах, могли бы быть намного более мощными по сравнению со своими классическими собратьями. Интересно, что за два года до Фейнмана в 1980 г. похожие идеи выдвигал российский математик Юрий Манин в своей небольшой, но очень содержательной книге "Вычислимое и невычислимое" [11].

где условие |с0|2 + |cj2 = 1 задает нормировку полной вероятности состояния кубита.

Удобное представление для вектора состояния

к> =

Кубит "живет" одновременно в абстрактном двумерном гильбертовом пространстве и в обычном трехмерном евклидовом пространстве. Вычислительные операции задаются посредством унитар-

где а = (аь а2, ) — матрицы Паули, I — единичная матрица.

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

где |соо|2 + Ы2 + |с1()|2 + |сп|2 = 1.

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

2. СИСТЕМЫ КУБИТОВ И КВАНТОВАЯ ЗАПУТАННОСТЬ

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

(3)

кубита дает сфера Блоха. Каждое чистое одноку-битовое состояние задается точкой на сфере Блоха, положение которой определяется полярным 9 и азимутальным ф углами:

(4)

ных вращений на сфере Блоха. Оператор унитарных

вращений на угол 8 относительно единичной оси п определяется следующей формулой:

(5)

ми, длительностью воздействий и т. п.). Аналогичное утверждение справедливо не только для отдельного кубита, но и для регистра из N куби-тов (только теперь гильбертово пространство

имеет размерность 2 )

Двухкубитовое состояние представляет собой суперпозицию 4-х базисных состояний:

(6)

Состояние системы, образованной двумя подсистемами, называется незапутанным, если оно может быть представлено в виде прямого (тензорного) произведения векторов состояний отдельных подсистем:

|у) = Ы г). (7)

В противном случае состояние называется запутанным. Для регистра из двух кубитов состояние (6) незапутанно, если выполняется условие:

с00с11 — с01с10 = (8)

И = c0\0) + Cl|1) = Со ( + Cl ( = ( cc° ),

( (à, cos I — Iexp

-гф 2~.

sin

(à) exp ((

\2

\ 2

R (0) = exp (-0

cos (^ j I - sin

(0) • n.

<-00 И + <-01 101 + <-10 H + cii|l1.

Так, состояние

к> = 1 (И-101 + И -|п>)

является незапуганным, поскольку может быть представлено в виде прямого произведения

k> = ^ (0)+11)® j. (0) - II).

Напротив, состояние

к> = т. (01 - |Ю>)

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

Мы видели, что двухкубитовое чистое состояние описывается четырьмя комплексными числами, аналогично можно показать, что трехкубитовое состояние задается с помощью 8-ми комплексных амплитуд, а состояние квантового регистра из N кубитов

посредством N комплексных чисел. Такой регистр

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

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

е-

Рис. 1. Графическое изображение двухкубитового элемента CNOT. Верхний кубит является управляющим, нижний — управляемым, символом © обозначена здесь однокубитовая операция NOT над управляемым кубитом, когда управляющий кубит находится в состоянии | 1).

Например, для регистра из 1000 кубитов без учета запутанности имеем только 2000 параметров, а с учетом запутанности таких параметров становится более

чем 10300. Это поистине колоссальное число. Заметим, что полное число барионов (таких частиц, как

протон и нейтрон) во Вселенной "всего" порядка 1 078.

Мы видим, что запутанность — это основной ресурс для новых квантовых информационных технологий. Для управления запутанностью может служить специальный логический квантовый вентиль (gate)-CNOT (Controlled NOT - Управляемое Не). Вентиль CNOT меняет состояние управляемого (target) кубита при условии, что управляющий кубит находится в состоянии 11).

Действие оператора CNOT на базисные состояния двухкубитового регистра описывается следующей таблицей (таблица истинности):

CNOT:

|00> ^ |00> |01)^|01) |10>^|11>. |11>^|10>

Унитарное преобразование CNOT задается следующей матрицей

(1 0 0 0^ 0 10 0

(9)

CNOT =

0 0 0 1 0 0 10 )

(10)

Графическое изображение вентиля СЫОТ представлено на рис. 1.

Было показано, что ььлюбое квантовое вычисление может быть выполнено с помощью универсального набора одно- и двухкубитовых элементарных операций. В качестве универсального может служить набор из произвольных однокубитовых вращений на сфере Блоха и двухкубитового элемента CNOT [12].

3. ОБЩИЕ ТРЕБОВАНИЯ, НЕОБХОДИМЫЕ ДЛЯ РЕАЛИЗАЦИИ КВАНТОВЫХ КОМПЬЮТЕРОВ

На рис. 2 представлена схема идеального квантового компьютера [1, 2].

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

|0х> |02>

К>

Рис. 2. Блок-схема идеального квантового компьютера.

ваний, сформулированных ДиВинченсо ^ГУтсеп-го) [13]:

1. Физическая система, представляющая полномасштабный (масштабируемый) квантовый регистр, должна содержать достаточно большое число N > 1000) кубитов с управляемыми резонансными частотами, на которые можно было бы независимо воздействовать в процессе выполнения соответствующих квантовых операций. Степень интеграции уровня N = 1000 ("одна квантовая килобита") может обеспечить вычисления, заведомо недоступные никакому классическому компьютеру во Вселенной.

2. Необходимо обеспечить условия приготовление состояния входного регистра с необходимой точностью в исходном основном состоянии

| 0N-1, 0N-2, 0N-3, • • • °()).

3. Необходимо обеспечить максимальное подавление эффектов декогерентизации (ёесоИегепсе) и исправление случайных ошибок квантовых состояний регистра. Характерное время декогерентиза-ции должно многокрано превышать время выполнения основных квантовых операций (время такта)

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком