Моделирование работы квантового компьютера на квадрупольных ядрах тема диссертации и автореферата по ВАК РФ 01.04.03, кандидат наук Ермилов, Андрей Сергеевич

• Ермилов, Андрей Сергеевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Ермилов, Андрей Сергеевич

Оглавление

Введение

Глава 1. Методы организации квантовых вычислений

1.1. Базовые понятия

1.1.1. Квантовые биты (кубиты)

1.1.2. Квантовые логические операторы (квантовые вентили)

1.2. Квантовые алгоритмы

1.2.1. Квантовое преобразование Фурье

1.2.2. Использование квантового преобразования Фурье в алгоритмах определения периода

1.2.3. Квантовый алгоритм поиска порядка подстановки

1.3. Адиабатическое квантовое вычисление. Квантовый отжиг

1.4. Вычисления на многоуровневых квантовых элементах

1.4.1. Понятие кудита

1.4.2. Система связанных квадрупольных ядер в магнитном поле

1.4.3. Управление с помощью импульсов радиочастотного поля

1.4.4. Матрица плотности. Квазичистое состояние

Выводы по главе

Глава 2. Реализация квантовых вентилей на кудитах и их применение для выполнения квантовых алгоритмов

2.1. Вентиль контролируемого сдвига фазы

2.2. Вентиль QFT, выполняемый на отдельном кудите

2.2.1. Реализация через виртуальные кубиты

2.2.2. Реализация через общее разложение унитарных матриц

2.2.3. Обобщение через виртуальные кудиты

2.3. Реализации вентиля БиМна двух кудитах

2.4. Выполнение квантового преобразования Фурье на нескольких кудитах

2.5. Выполнение алгоритма поиска порядка подстановки на двух кудитах

2.5.1. Общая схема

2.5.2. Моделирование алгоритма

2.5.3. Сравнение с реализацией на кубитах

Выводы по главе

Глава 3. Квантовые вычисления с использованием адиабатической эволюции

3.1. Метод получения адиабатической эволюции для квантовых алгоритмов, представленных стандартной квантовой схемой

3.2. Адиабатическая реализация квантового преобразования Фурье на трех кубитах

3.3. Адиабатическая реализация квантового алгоритма определения порядка подстановки на пяти кубитах

3.4. Обсуждение результатов

Выводы по главе

Глава 4. Адиабатические квантовые вычисления на кудитах

4.1. Адиабатическая реализация алгоритма определения порядка подстановки на двух кудитах

4.2. Адиабатическая реализация алгоритма факторизации на двух кудитах

4.2.1. Получение эффективного гамильтониана

4.2.2. Реализация на системе двух связанных квадрупольных ядер

4.2.3. Расчеты и обсуждение результатов

Выводы по главе

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Моделирование работы квантового компьютера на квадрупольных ядрах»

Введение

Объект исследования и актуальность темы

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

Одними из первых, кто высказал идею о применении квантовых систем в качестве вычислительной машины, были Р. Фейнман [1, 2, 3] и Ю. И. Манин [4]. Ими было замечено, что моделирование естественных систем (например, квантово-механических) является экспоненциально сложной задачей для классических компьютеров. В то же время, если для моделирования использовать систему с тем же типом поведения, то задача становится полиномиально сложной, то есть существует эффективный алгоритм ее решения.

В тот же период, благодаря работам таких авторов как П. Бениофф [5, 6], Д. Дойч [3,7] и Ч. Беннетт [3,8], были заложены теоретические основы квантовых вычислений. Позже были получены вычислительные алгоритмы [3, 9, 10, 11], использующие такие квантово-механические эффекты, как квантовый параллелизм [10], интерференция и запутанность квантовых состояний [11, 12], и демонстрирующие эффективность квантовых вычислений в решении различных задач.

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

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

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

С другой стороны, современные импульсные методы ядерного магнитного резонанса (ЯМР) оказались весьма эффективными для выполнения простых квантовых алгоритмов, благодаря хорошо развитым методам управления с помощью резонансных импульсов радиочастотного (РЧ) магнитного поля. В том числе, существует ряд работ по управлению состояниями отдельных кудитов, представленных квадрупольными ядрами со спином /> 1/2.

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

Цель работы и основные задачи

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

Для достижения поставленной цели решались следующие задачи:

1. Получение схемы реализации простых квантовых алгоритмов на кудитах.

2. Нахождение последовательности РЧ импульсов для выполнения алгоритмов на квадрупольных ядрах со спином /> 1/2.

3. Численное моделирование эволюции квантовой системы под действием полученной последовательности РЧ импульсов.

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

Структура диссертации

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

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

Вторая глава посвящена проблеме реализации базовых вентилей на кудитах. На примере квадрупольных ядер, управляемых с помощью селективных (по переходам между уровнями) РЧ импульсов, рассмотрены способы получения вентилей QFT и SUM, а также представлены схемы для выполнения квантового преобразования Фурье (КПФ) и простейшего алгоритма поиска порядка подстановки.

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

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

Диссертацию завершает заключение, в котором подводятся основные итоги работы.

Научная новизна работы, ее теоретическая и практическая значимость

Научная новизна работы заключается в следующем:

1. Разработаны схемы для практического осуществления КПФ на кудитах. Рассчитаны последовательности РЧ импульсов для реализации вентиля О^Т на отдельных кудитах, представленных квадрупольными ядрами со спином 1 </<9/2. Последовательности для случаев ядер со спинами 3/2 </<9/2 найдены впервые.

2. Впервые получена схема для выполнения квантового алгоритма поиска порядка подстановки на двух кудитах, а также рассчитана последовательность РЧ импульсов для реализации алгоритма на системе связанных квадрупольных ядер со спинами 1Х = 7/2 и /2 = 3/2, выполнено численное моделирование работы алгоритма.

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

4. Впервые получена схема для выполнения адиабатического квантового алгоритма факторизации на двух кудитах и рассчитана последовательность РЧ импульсов для факторизации чисел 35, 21 и 15 на системе связанных квадрупольных ядер со спинами 1Х = Ъ12 и /2=1, выполнено численное моделирование работы алгоритма.

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

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

Достоверность полученных результатов подтверждается согласованностью результатов численного моделирования с аналитическими оценками. Применяемые для численного моделирования модели соответствуют природе исследуемых объектов.

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

Основные результаты и положения, выносимые на защиту:

1. Результаты исследования различных способов получения одночастичного вентиля О^Т для многоуровневых квантовых элементов. Последовательности операторов для получения вентиля QFT на кудитах с числом энергетических уровней от 3 до 10.

2. Последовательности операторов для реализации квантового алгоритма поиска порядка подстановки на системе двух квадрупольных ядер со спинами 1\ = 7/2 и /2 = 3/2, управляемых селективными РЧ импульсами. Результаты численного моделирования работы алгоритма.

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

а) алгоритма вычисления КПФ на системе трех кубитов;

б) алгоритма поиска порядка подстановки на системе пяти кубитов;

в) алгоритма поиска порядка подстановки на системе двух квадрупольных ядер со спинами /] = 7/2 и /2 = 3/2.

4. Способ получения эффективного гамильтониана для выполнения адиабатического алгоритма факторизации на системе двух квадрупольных ядер, управляемых селективными РЧ импульсами. Последовательности РЧ импульсов для реализации алгоритма в случае ядер со спинами /] = 3/2 и I2= 1, а также результаты численного моделирования работы алгоритма.

Апробация работы

Результаты диссертационных исследований опубликованы в журналах: «ЖЭТФ» [13], «Письма в ЖЭТФ» [14, 15], «Оптика и спектроскопия» [16], «ТМФ» [17], «Вестник КрасГУ» [18], «Quantum Computers and Computing» [19], a также докладывались и обсуждались на следующих конференциях: VIII Всероссийском семинаре «Моделирование неравновесных систем» (Красноярск, 2005 г.), Всероссийской научной конференции студентов-физиков и молодых ученых «ВНКСФ-12» (Новосибирск, 2006 г.), Международной конференции «Micro- and nanoelectronics» (Звенигород, 2007 и 2009 гг.).

Глава 1

Методы организации квантовых вычислений

1.1. Базовые понятия

1.1.1. Квантовые биты (кубиты)

Для описания состояний микрообъектов и их свойств удобнее всего использовать язык комплексных Гильбертовых пространств. Простейшим таким пространством является пространство двух квантовых состояний, ортонормирован-ный базис которого можно обозначить как {|0), |1)}. В соответствии с принципом суперпозиции, наиболее общее нормированное состояние в таком пространстве может быть представлено в виде вектора:

И = С0|0)+С1|1), (И<гНс0|2+Ы2=1. (1.1)

После проецирования на ортонормированный базис, состояние \у/) переходит либо

2 2 в состояние |0) с вероятностью |с0| , либо в состояние |1) с вероятностью \с\\ .

Аналогично тому, как в классической теории для обозначения единицы информации, принимающей значение 0 или 1, вводится понятие бита, единица квантовой информации, описываемая выражением (1.1), называется кубитом [12].

Состояния кубита |0) и |1> называются базисными, а комплексные числа со и c¡ - их ♦ амплитудами. В процессе считывания информации с кубита, суперпозиция (1.1) разрушается и кубит переходит в одно из своих базисных состояний, т.е. преобразуется в вероятностный классический бит.

Понятие кубита имеет формально прос-

Рисунок 1.1.

тую геометрическую интерпретацию в виде Сфера Блоха. Амплитуды состояний в

сферы Блоха (рисунок 1.1), построенной в (1Л) связаны со сферическими координатами через соотношение:

воображаемом пространстве состояний. с0 = cos(é'/2), с, = e¥sin(6>/2).

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

1.1.2. Квантовые логические операторы (квантовые вентили)

Известно, что универсальный компьютер может быть представлен как схема взаимосвязанных логических блоков - вентилей, выполняющих элементарные логические операции, при этом, любое «разумное» вычисление может быть выполнено с помощью фиксированного набора вентилей [4].

Точно так же, с помощью небольшого набора квантовых вентилей, любое квантовое вычисление можно разложить в виде последовательности элементарных операций, выполняемых этими вентилями [10].

Действие любого квантового вентиля представляет собой изменение состояния квантовой системы во времени, которое определяется уравнением Шредингера:

¿к) <м

=~ши к)

(1.2)

с гамильтонианом Ни (здесь и далее константа Ь = 1). Если гамильтониан Ни не зависит от времени, то решение уравнения (1.2) может быть записано в виде:

к(0) = ехрНЯ^И0)) = ^(0к(°)> > О-3)

где оператор эволюции

и{{) = ехр(— ///у/) (1.4)

представляет собой матричный унитарный оператор, действующий на вектор состояния квантовой системы.

Рассмотрим примеры простейших квантовых вентилей. Для этого вернемся к геометрической интерпретации кубита. Унитарный оператор, описывающий поворот вектора состояния на угол 0 вокруг произвольной оси ц, проходящей через центр сферы Блоха, имеет следующий вид [10]:

а, -гвш

Ьх^х +г1у°У +Л2(Т?Х (1-5)

где <7/ — единичная матрица, ах, ~ матрицы Паули:

1

0 1

0 Г

1 0.

о -/ / о

/1 о ^ 0 -1

(1.6)

В случае классических вычислений, число всех возможных вентилей конечно. Для квантовых вычислений, благодаря суперпозиции (1.1), такого ограничения нет, однако, в силу полноты набора операторов (1.6), любой одно-кубитовый оператор может быть разложен по этой системе матриц [10]:

и = ехр(г'«)^(/{в), где ехр(т) - фазовый множитель. Например, вентиль МОТ, инвертирующий состояние кубита, можно записать как:

(о Г ыот = \ 1» о,

вентиль сдвига фазы:

= <т

X '

(1.7)

0 е'6

- exp{i0/2)-

ехр(- id/2) 0 0 ехр(/6>/2)

= exp(f0/2)-Jlz(0);

(1.8)

вентиль Адамара:

(1.9)

Говоря про вентиль Адамара, стоит отметить его свойство самосопряженности:

#■# = #•#* = Н1 ■ Н- сг,.

t

(1.10)

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

Так, двухкубитовый вентиль контролируемого сдвига фазы В]к{0), действующий в пространстве двух кубитов j и к, изменяет фазу кубита к на угол в, чем схож с вентилем (1.8), но делает это лишь при условии, что кубит j находится в состоянии |1). В виде матричного оператора этот оператор выглядит следующим образом:

'1 0 0 04

0 10 0

0 0 10

0 0 0 е,в

Ч у

Другой двухкубитовый вентиль CNOTjk действует на кубит к как вентиль NOT, контролируемый состоянием кубита j:

0 0 0Л

0 10 0

0 0 0 1

v0 О 1 оу

вМ =

(1.11)

CNOT,t

(1.12)

Оператор СИ01)к может быть выражен через операторы и Я по формуле [20]:

В качестве примера трехкубитового вентиля можно привести вентиль Тоффоли, обозначаемый также как ССЫОТ]кт, поскольку действует как дважды контролируемый вентиль ЫОТ - обращает состояние контролируемого кубита т только в том случае, когда оба контролирующих (/ и к) находятся в состоянии |1):

1.2. Квантовые алгоритмы

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

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

1.2.1. Квантовое преобразование Фурье

Квантовая реализация преобразования Фурье играет ключевую роль во многих алгоритмах. В общем виде действие КПФ на квантовый регистр, представленный ¿/-мерным вектором состояния, осуществляется унитарным оператором,

СНОТ]к = ® Н) Я О) {ст1 ® Н).

(1.13)

"1 0 0 0 0 0 0 0"

0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 10 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1

0 0 0 0 0 0 1 0,

(1.14)

который задается выражением:

i/-l d-1

( 2 та

QFTd—YL-M-fj^m-

\а /=о к=о V " У

(1.15)

В матричном виде КПФ описывается матрицей Вандермонда, которая является обобщением матрицы Уолша-Адамара [12, 21]:

OFT, =

-id

rl 1 1 1

со

2

СО

СО

СО

1 я/-' co2{J~l)

СО

1

а?"'1

2(</-1)

СО

со = ехр

v d У

(1.16)

В случае й?=2, оператор КПФ (1.16) равен оператору Адамара (1.9), то есть вентиль Адамара - это КПФ, действующее на состояние отдельного кубита.

Для системы п кубитов, образующих квантовый регистр размерности с1 = 2", существует схема быстрого КПФ, демонстрирующая экспоненциальный прирост в скорости вычисления, по сравнению с любой классической схемой быстрого преобразования Фурье. Реализуется эта схема при помощи последовательности квантовых вентилей двух типов: вентиля Адамара (1.9) и вентиля контролируемого сдвига фазы (1.11) [12, 22, 23]:

HnBn-\,,Bn-2,n---B2,nB\,„Hn-\ --H3B2,lB\,iH2B\,2H\ '

(1.17)

где Hj — оператор Адамара, действующий на кубит j, В} к = В]к{&) - оператор сдвига

фазы кубита к, контролируемого кубитом j, на угол в = тс/24 В целом, после-

2 2 довательность (1.17) включает в себя {п + п)/2 вентилей: (п —п)/2 вентилей В]к

и п вентилей Hj, в то время как классическое преобразование требует порядка п2"

операций. На рисунке 1.2 показана схема применения последовательности (1.17) в

"2

случае трех кубитов (n = 3,d=2 =8).

При использовании последовательности (1.17) следует учитывать одну ее особенность - результат преобразования получается побитно обратным по отношению результату, полученному после применения оператора (1.16). Поэтому, после вычисления следует либо учитывать эту особенность в дальнейшей обработке результата, либо воспользоваться оператором перестановки SWAP [12].

н

Рисунок 1.2.

Схема для реализации квантового преобразования Фурье на примере трех кубитов. оператор Адамара,

Н

90 - оператор контролируемого сдвига фазы на угол в — тс/2,

451 - оператор контролируемого сдвига фазы на угол и в — к/4.

1.2.2. Использование квантового преобразования Фурье в алгоритмах определения периода

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

В общем виде, в алгоритмах такого типа можно выделить 5 основных этапов:

1) подготовка квантовых регистров |х) и [у) и перевод основного регистра в состояние суперпозиции;

2) кодирование некоторой периодической функции Дх) с применением вспомогательного регистра [у), при этом, регистр \х) должен быть достаточно большим, чтобы вместить как минимум два периода кодируемой функции;

3) применение КПФ к основному регистру \х)\

4) применение оператора SWAP к регистру \х), если это необходимо;

5) чтение состояния основного регистра |х>.

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

В качестве примеров подобных алгоритмов можно привести:

• алгоритм поиска порядка подстановки [24];

• алгоритм факторизации (разбиения числа на множители) Шора [3, 22].

1.2.3. Квантовый алгоритм поиска порядка подстановки

Сначала определим значения ключевых терминов. Представим себе множество Y из п элементов yj (J = 1, ..., ri). Пускай существует биективное преобразование s множества Y самого в себя, которое будем называть подстановкой. Такая подстановка может быть представлена в виде произведения независимых циклов [25, 26]:

s = sxs2...sk, s, =(yy,j,(yy)t...,jI/'-,(y7))J = (1.18)

где yj - элемент подмножества Yh на котором действует подстановка s„ /, - длина цикла i. Тогда порядок г подстановки 5 равен наименьшему общему кратному длин /ь /2, ..., 4 циклов, входящих в разложение 5 (1.18).

В качестве конкретного примера рассмотрим случай множества из 4 элементов: Y= {0, 1, 2, 3}. Для данного множества можно определить подстановки четырех различных порядков:

1. г = 1 (тождественная подстановка): 0—>0, 1—>1, 2—>2, 3—»-3, s = (0)(1)(2)(3)

2. г = 2 (вариант 1): 0->1, 1->0, 2->3, 3->2, s = (0, 1)(2, 3) г = 2 (вариант 2): 0—»2, 1—>3, 2—>0, 3—>1, s = (0, 2)(1,3) г = 2 (вариант 3): 0—»>3, 1—>2, 2—>1, 3—>0, s = (0,3)(l,2)

3. г = 3 (простой пример): 0—>-1, 1—>2, 2—>0, 3—>3, s = (0, 1, 2)(3)

4. г = 4 (простой пример): 0->1, 1—>2, 2^3, 3—>0, 5 = (0, 1, 2, 3) Математически, действие подстановки может быть описано периодической

функцией, определенной на множестве Y:

/(x,y) = sx(y).

В частности, для второго варианта подстановки с порядком г = 2, эта функция будет иметь следующие значения:

Д1,0) = 5(0) = 2 /1, l) = s(l) = 3 Д1, 2) = s (2) = 0 Д1, 3) = s (3) = 1 Д2, 0) = 52(0) = 0 Д2, 1) = s\ 1) = 1 f[2, 2) = s\2) = 2 Д2, 3) = /(3) = 3 ДЗ, 0) = ДО) = 2 ДЗ, 1) = 53(1) = 3 Д3,2) = 53(2) = 0 ДЗ, 3) = s3(3) = 1

Тогда период подстановки будет равен периоду функции fix, у). Следовательно, задачу поиска порядка подстановки можно свести к задаче определения периода.

1.3. Адиабатическое квантовое вычисление. Квантовый отжиг

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

В то же время, квантовые вычисления можно проводить иначе, посредством адиабатического изменения гамильтониана: от начального гамильтониана Н{0), чье основное состояние [у(0)> легко приготовить, к конечному гамильтониану Н(Т), основное состояние \щ(Т)) которого кодирует решение поставленной задачи. Если на всем протяжении такой эволюции соблюдается условие адиабатичности, то квантовая система, на которой выполняется квантовое вычисление, будет находиться в основном состоянии. Поскольку основное состояние отличается повышенной устойчивостью к помехам, с квантовым адиабатическим вычислением связывают надежды в уменьшении вероятности ошибок, возникающих по ходу вычисления [27].

Доказано, что любую последовательность квантовых вентилей можно реализовать с помощью адиабатической эволюции [28,29,30]. Особо стоит отметить предложенное в работе [28] нелинейное унитарное преобразование гамильтониана, которое гарантирует, что разница энергий между основным и ближайшим возбужденным энергетическими уровнями будет не меньше заданной величины на протяжении всей эволюции квантовой системы. Этот параметр играет важную роль в квантовых вычислениях, поскольку определяет допустимую скорость изменения гамильтониана и, следовательно, продолжительность эксперимента и его точность.

Помимо этого, с помощью квантовых адиабатических алгоритмов, в том числе популярного в последнее время квантового отжига (quantum annealing) [31, 32], можно решать различные задачи, не раскладывая вычисление на стандартные

квантовые вентили. Таким способом предлагается решать сложные комбинаторные задачи: задачу факторизация числа [33, 34] или задачи поиска [27, 35, 36]; а также ресурсоемкие физические задачи, как, например, задача поиска основного состояния в модели Изинга [32]. Однако вопрос об эффективности подобных адиабатических вычислений остается дискуссионным [37].

1.4. Вычисления на многоуровневых квантовых элементах

1.4.1. Понятие кудита

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

Однако в природе значительно чаще встречаются квантовые системы с большим числом уровней, называемые в литературе по квантовым вычислениям «кудитами». Термин «кудит» аналогичен термину «кубит» и используется в общих случаях для обозначения ¿/-уровневых квантовых объектов. Также встречаются другие эквивалентные понятия, например, «кутрит» и «кукварт», обозначающие трех- и четырехуровневые кудиты соответственно.

В качестве кудитов можно рассматривать квадрупольные ядра со спином /> 1/2, атомы и ионы в ловушках, молекулярные магнетики с многоуровневыми электронными состояниями, спиновые кластеры с сильным спин-спиновым взаимодействием, также кудиты могут быть получены с использованием бифо-тонов и сверхпроводников.

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

Список литературы диссертационного исследования кандидат наук Ермилов, Андрей Сергеевич, 2013 год

Список литературы

1. Feynman R. Simulating Physics with Computers // Int. J. Theor. Phys. - 1982. -V. 21.-P. 467.

2. Feynman R. Quantum Mechanical Computers // Found. Phys. - 1986. - V. 16. -P. 507.

3. Квантовый компьютер и квантовые вычисления. - Ижевск: НИЦ «Регулярная и хаотическая динамика», 1999. - 288 с.

4. Манин Ю. И. Вычислимое и невычислимое. / Ю. И. Манин. - М.: Сов. радио, 1980.- 128 с.

5. Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines // J. Stat. Phys. - 1980. - V. 22. - P. 563.

6. Benioff P. Quantum mechanical Hamiltonian model of Turing machines // J. Stat. Phys. - 1982. - V. 29. - P. 515.

7. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer // Proc. R. Soc. Lond. A. - 1985. - V. 400. - P. 97.

8. Bennett C. Logical reversibility of computation // IBM J. Res. Develop. - 1973. -V. 17.-P. 525.

9. Deutsch D., Jozsa R. Rapid solution of problems by quantum computation // Proc. R. Soc. Lond. A. - 1992. - V. 439. - P. 553.

10. Нильсен M., Чанг И. Квантовые вычисления и квантовая информация. / М. Нильсен, И. Чанг. - М.: Мир, 2006. - 824 с.

11. Прескилл Дж. Квантовая информация и квантовые вычисления. Том 1. / Дж. Прескилл. - Ижевск: НИЦ «Регулярная и хаотическая динамика», 2008.-464 с.

12. Валиев К. А., Кокин А. А. Квантовые компьютеры: надежды и реальность. / К. А. Валиев, А. А. Кокин. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 352 с.

13. Зобов В. Е., Ермилов А. С. О выполнении квантового адиабатического алгоритма факторизации на двух кудитах // ЖЭТФ. - 2012. - Т. 141. - В. 6. -С. 1060.

14. Зобов В. Е., Ермилов А. С. Последовательности импульсов для реализации квантового преобразования Фурье на многоуровневых системах // Письма в ЖЭТФ. - 2006. - Т. 83. - В. 10. - С. 539.

15. Зобов В. Е., Шауро В. П., Ермилов А. С. Выполнение квантового алгоритма поиска порядка подстановки на двух кудитах // Письма в ЖЭТФ. - 2008. -Т. 87.-В. 6.-С. 385.

16.

17.

18.

19.

20.

21.

22.

23,

24,

25,

26

27

28

29

30

Ермилов А. С., Зобов В. Е. Представление квантового преобразования Фурье на многоуровневых базовых элементах с помощью последовательности операторов селективных поворотов // Опт. и спектр. - 2007. - Т. 103. - С. 994. Зобов В. Е., Ермилов А. С. О реализации стандартных квантовых вычислительных сетей посредством адиабатической эволюции // ТМФ. - 2007. -Т. 150. -№3,- С. 462.

Ермилов А. С., Зобов В. Е. Реализация квантового преобразования Фурье посредством адиабатической эволюции: моделирование для случая трех ядерных спинов // Вестник КрасГУ. - 2006. - № 9. - С. 26. Ermilov A. S., Zobov V. Е. Implementation of the quantum order-finding algorithm by adiabatic evolution of two qudits // Quantum Computers and Computing. - 2009. - V. 9. - P. 39.

Vandersypen L. M. K., Chuang I. L. NMR techniques for quantum control and

computation // Rev. Mod. Phys. - 2005. - V. 76. - P. 1037.

Fujii K., Funahashi K., Kobayashi T. Jarlskog's parametrization of unitary matrices

and qudit theory // Int. J. Geom. Meth. Mod. Phys. - 2006. - V. 3. - P. 269.

Vandersypen L. M. K., Steffen M.,.Breyta G. et al. Experimental realization of

Shor's quantum factoring algorithm using nuclear magnetic resonance

//Nature. -2001.-V. 414.-P. 883.

Dorai K., Suter D. Efficient implementations of the Quantum Fourier Transform: an experimental perspective // Int. J. Quantum Inform. - 2005. - V. 03. - P. 413. Vandersypen L. M. K., Steffen M., Breyta G. et al. Experimental Realization of Order-Finding Algorithm with NMR Quantum Computer // Phys. Rev. Lett. - 2000. - V. 85. - P. 5452.

Сачков В. H. Введение в комбинаторные методы дискретной математики. / В. Н. Сачков. - М.: Наука, 1982. - 384 с. Кофман А. Введение в прикладную комбинаторику. / А. Кофман. - М.: Наука, 1975. - 480 с.

Childs А. М., Farhi Е., Preskill J. Robustness of adiabatic quantum computation // Phys. Rev. A. - 2001. - V. 65. - P. 012322.

Siu M. S. From quantum circuits to adiabatic algorithms // Phys. Rev. A. - 2005. -V. 71.-P. 062314.

Aharonov D., van Dam W., Kempe J. et al. Adiabatic quantum computation is equivalent to standard quantum computation // SIAM J. Comput. - 2007. -V. 37.-P. 166.

Kempe J., Kitaev A., Regev O. The complexity of the local Hamiltonian problem // SIAM J. Comput. - 2006. - V. 35. - P. 1070.

31.

32.

33.

34.

35.

36.

37,

38

39

40

41

42

43

44

45

46

Das A., Chakrabarti В. K. Quantum annealing and analog quantum computation // Rev. Mod. Phys. - 2008. - V. 80. - P. 1061.

Johnson M. W., Amin M. H. S., Gildert S. et al. Quantum annealing with

manufactured spins // Nature. - 2011. - V. 473. - P. 194.

Schaller G., Schitzhold R. The role of symmetries in adiabatic quantum

algorithms // Q. Information and Computation. - 2010. - V. 10. - P. 0109.

Peng X., Liao Z., Xu N. et al. A quantum adiabatic algorithm for factorization and

its experimental implementation // Phys. Rev. Lett. - 2008. - V. 101. - P. 220405.

Farhi E., Goldstone J., Gutmann S., Sipser M. Quantum computation by adiabatic

evolution// arXiv.org: quant-ph/0001106.

Roland J., Cerf N. J. Quantum search by local adiabatic evolution

// Phys. Rev. A. - 2002. - V. 65. - P. 042308.

Dickson N. G., Amin M. H. S. Algorithmic approach to adiabatic quantum optimization // Phys. Rev. A. - 2012. - V. 85. - P. 032303. Motzoi F., Gambetta J. M., Rebentrost P., Wilhelm F. K. Simple pulses for elimination of leakage in weakly nonlinear qubits // Phys. Rev. Lett. - 2009. -V. 103.-P. 110501.

Gambetta J. M., Motzoi F., Merkel S. Т., Wilhelm F. K. Analytic control methods for high-fidelity unitary operations in a weakly nonlinear oscillator //Phys. Rev. A.-2011,-V. 83.-P. 012308.

Ralph Т. C., Resch K. J., Gilchrist A. Efficient Toffoli gates using qudits // Phys. Rev. A. - 2007. - V. 75. - P. 022313.

Lanyon B. P., Barbieri M., Almeida M. P. et al. Simplifying quantum logic using higher-dimensional Hilbert spaces // Nat. Phys. - 2009. - Y. 5. - P. 134. Fedorov A., Steffen L., Baur M. et al. Implementation of a Toffoli gate with superconducting circuits // Nature. - 2012. - V. 481. - P. 170. Низовцев А. П., Килин С. Я., Jelezko F. и др. Квантовый компьютер на NV-центрах в алмазе. Оптически детектируемые нутации одиночных электронного и ядерного спинов // Опт. и спектр. - 2005. - Т. 99. - С. 248. Кессель А. Р., Ермаков В. JI. Физическая реализация трехкубитных вентилей на отдельной квантовой частице // Письма в ЖЭТФ. - 2000. - Т. 71. - С. 443. Кессель А. Р., Ермаков В. JI. Виртуальные кубиты - многоуровневость вместо многочастичности // ЖЭТФ. - 2000. - Т. 117. - С. 571. Ermakov V. L., Fung В. М. Experimental realization of a continuous version of the Grover algorithm // Phys. Rev. A. - 2002. - V. 66. - P. 042310.

47.

48.

49.

50.

51.

52,

53

54

55

56

57

58

59

60

61

Das R., Kumar A. Use of quadrupolar nuclei for quantum-information processing by nuclear magnetic resonance: Implementation of a quantum algorithm // Phys. Rev. A. - 2003. - V. 68. - P. 032304.

Khitrin A. K., Fung В. M. Nuclear magnetic resonance quantum logic gates using quadrupolar nuclei // J. Chem. Phys. - 2000. - V. 112. - P. 6963. Kampermann H., Veeman W. S. Characterization of quantum algorithms by quantum process tomography using quadrupolar spins in solid-state nuclear magnetic resonance // J. Chem. Phys. - 2005. - V. 122. - P. 214108. Khitrin A. K., Fung В. M. NMR simulation of an eight-state quantum system // Phys. Rev. A. - 2001. - V. 64. - P. 032306.

Murali К. V. R. M., SinhaN., Mahesh T. S. et al. Quantum-information processing by nuclear magnetic resonance: Experimental implementation of half-adder and subtractor operations using an oriented spin-7/2 system // Phys. Rev. A. - 2002. -V. 66.-P. 022313.

Araujo-Ferreira A. G., Brasil C. A., Soares-Pinto D. O. et al. Quantum state tomography and quantum logical operations in a three qubits NMR quadrupolar system // Int. J. Quantum Inform. - 2012. - V. 10. - P. 1250016. Das R., Kumar A. Experimental implementation of a quantum algorithm in a multiqubit NMR system formed by an oriented 7/2 spin // Appl. Phys. Lett. -2006,-V. 89.-P. 024107.

Hirayama Y., Miranowicz A., Ota T. et al. Nanometre-scale nuclear-spin device for quantum information processing // J. Phys. Condens. Matter. - 2006. -V. 18. - P. 885.

Leuenberger M. N., Loss D. Quantum computing in molecular magnets //Nature. - 2001.-V. 410.-P. 789.

Ahn J., Weinacht Т. C., Bucksbaum P. H. Information storage and retrieval through quantum phase // Science. - 2000. - V. 287. - P. 463. Gottesman D. Fault-tolerant quantum computation with higher-dimensional systems //Lect. Not. Сотр. Sci. - 1999. -V. 1509. - P. 302. Gottesman D., Kitaev A., Preskill J. Encoding a qubit in an oscillator // Phys. Rev. A. - 2001. - V. 64. - P. 012310.

Сликтер Ч. Основы теории магнитного резонанса. / Ч. Сликтер. - М.: Мир, 1981.-448 с.

Vlasov A. Yu. Noncommutative tori and universal sets of nonbinary quantum gates // J. Math. Phys. - 2002. - V. 43. - P. 2959.

Klimov А. В., Guzman R., Retama J. C., Saavedra C. Qutrit quantum computer with trapped ions // Phys. Rev. A. - 2003. - V. 67. - P. 062313.

62.

63.

64.

65.

66.

67.

68,

69

70

71

72

73

74

75

76

77

Muthukrishnan A., Stroud (Jr.) C. R. Multivalued logic gates for quantum computation // Phys. Rev. A. - 2000. - V. 62. - P. 052309. Daboul J., Wang X., Sanders B. C. Quantum gates on hybrid qudits // J. Phys. A: Math. Gen. - 2003. - V. 36. - P. 2525.

Bartlett S. D., de Guise H., Sanders B. C. Quantum encodings in spin systems and harmonic oscillators // Phys. Rev. A. - 2002. - V. 65. - P. 052316. Bullock S. S., O'Leary D. P., Brennen G. K. Asymptotically optimal quantum circuits for d-level systems // Phys. Rev. Lett. - 2005. - V. 94. - P. 230502. Khan F. S., Perkowski M. M. Synthesis of ternary quantum logic circuits by decomposition // arXiv.org: quant-ph/0511041.

McHugh D., Twamley J. Trapped-ion qutrit spin molecule quantum computer // arXiv.org: quant-ph/0506031.

Cen L., Hou B., Chen M. Implementation of qutrit-based quantum information processing via state-dependent forces on trapped ions // arXiv.org: quant-ph/0608105.

Brennen G. K., O'Leary D. P., Bullock S. S. Criteria for exact qudit universality //Phys. Rev. A. -2005. - V. 71.-P. 052318. O'Leary D. P., Brennen G. K., Bullock S. S. Parallelism for quantum computation with qudits // Phys. Rev. A. - 2006. - V. 74. - P. 032334. Moreva E. V., Maslennikov G. A., Straup S. S., Kulik S. P. Realization of four-state qudits using biphotons // Phys. Rev. Lett. - 2006. - V. 97. - P. 023602. Soares-Pinto D. O., Celeri L. C., Auccaise R. et al. Nonclassical correlation in NMR quadrupolar systems // Phys. Rev. A. - 2010. - V. 81. - P. 062118. Das R., Mitra A., Kumar V., Kumar A. Quantum information processing by NMR: Preparation of pseudopure states and implementation of unitary operations in a single-qutrit system // Int. J. Quantum Inf. - 2003. - V. 1. - P. 387. Gopinath T., Kumar A. Geometric quantum computation using fictitious spin-1/2 subspaces of strongly dipolar coupled nuclear spins // Phys. Rev. A. - 2006. -V. 73.-P. 022326.

Mehring M., Scherer W., Weidinger A. Pseudoentanglement of spin states in the multilevel 15N@C60 system // Phys. Rev. Lett. - 2004. - V. 93. - P. 206603. Kessel A. R., Yakovleva N. M. Implementation schemes in NMR of quantum processors and the Deutsch-Jozsa algorithm by using virtual spin representation // Phys. Rev. A. - 2002. - V. 66. - P. 062322.

Jones J. A. Quantum computing with NMR // Prog. NMR. Specrosc. - 2011. -V. 59. - P. 91.

78.

79.

80.

81.

82.

83,

84,

85

86

87

88

89

90

91

92

93

Lee J.-S., Khitrin А. К. PseudopureNtate of a twelve-spin system //J. Chem. Phys. - 2005. - V. 122.-P. 041101.

Кессель A. P., Ермаков В. JI. Многокубитный спин // Письма в ЖЭТФ. -1999.-Т. 70.-С. 59.

Бауместер Д., Экерт А., Цайлингер А. Физика квантовой информации. / Д. Бауместер, А. Экерт, А. Цайлингер. - М.: Постмаркет, 2002. - 376 с. Muthukrishnan A., Stroud (Jr.) С. R. Quantum fast Fourier transform using multilevel atoms // J. Mod. Optics. - 2002. - V. 49. - P. 2115. Berman G. P., Doolen G. D., Lopez G. V., Tsifrinovich V. I. Nonresonant effects in the implementation of the quantum Shor algorithm // Phys. Rev. A. - 2000. -V. 61.-P. 042307.

Зубарев Д. H. Неравновесная статистическая термодинамика / Д. Н. Зубарев. - М.: Наука, 1971. - 416 с.

Лундин А. А., Зобов В. Е. Форма крыльев спектров магнитного резонанса и адиабатические инварианты в спиновой системе // ЖЭТФ. - 1993. - Т. 103. -С. 1070.

Steffen М., van Dam W., Hogg Т., et al. Experimental implementation of an adiabatic quantum optimization algorithm // Phys. Rev. Lett. - 2003. - V. 90. -P.067903.

Weinstein Y. S., Pravia M. A., Fortunato E. M. et al. Implementation of the quantum Fourier transform // Phys. Rev. Lett. - 2001. - V. 86. - P. 1889. Xu N., Zhu J., Lu D. et al. Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system // Phys. Rev. Lett. - 2012. - V. 108. -P. 130501.

Bian Z., Chudak F., Macready W. G. et al. Experimental determination of Ramsey numbers//Phys. Rev. Lett. - 2013. - V. 111.-P. 130505. KhanejaN., Reiss Т., Kehlet С. et al. Optimal control of coupled spin dynamics: design of NMR pulse sequences by gradient ascent algorithms // J. Magn. Reson. - 2005. - V. 172. - P. 296.

Lu D., Xu N., Xu R. et al. Simulation of chemical isomerization reaction dynamics

on a NMR quantum simulator // Phys. Rev. Lett. - 2011. - V. 107. - P. 020501.

Зобов В. E., Шауро В. П. Об оптимальном по времени управлении методом

ЯМР состояниями кутритов, представленных квадрупольными ядрами со

спином 1= 1 //ЖЭТФ.-2011.-Т. 140.-С. 211.

Friedman J. R., Sarachik M. P. Single-molecule nanomagnets

//Annu. Rev. Condens. Matter Phys. - 2010. - V. l.-P. 109.

Strauch F. W. Quantum logic gates for superconducting resonator qudits

//Phys. Rev. A.-2011.-V. 84.-P. 052313.