Основы теории построения квантовых компьютеров и моделирование квантовых алгоритмов

. МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное

учреждение высшего образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Инженерно-технологическая академия

В. Ф. ГУЗИК, С. М. ГУШАНСКИЙ 

Е. В. ЛЯПУНЦОВА, В. С. ПОТАПОВ 

ОСНОВЫ ТЕОРИИ ПОСТРОЕНИЯ КВАНТОВЫХ 

КОМПЬЮТЕРОВ И МОДЕЛИРОВАНИЕ 

КВАНТОВЫХ АЛГОРИТМОВ

Монография

Москва ‒ Ростов-на-Дону ‒ Таганрог

Физматлит ‒ Издательство Южного федерального университета

2019

УДК 004.38
ББК 32.973

Г753

Печатается по решению экспертной группы комитета по инженерному 

направлению науки и образования при ученом совете Южного 

федерального университета (протокол № 7 от 17 апреля 2019 г.)

Рецензенты:

доктор физико-математических наук, профессор Г. В. Куповых

доктор технических наук, профессор В. И. Божич

Гузик, В. Ф.

Г753     Основы теории построения квантовых компьютеров и моделирова
ние квантовых алгоритмов : монография / В. Ф. Гузик, С. М. Гушанский, Е. В. Ляпунцова, В.С. Потапов. – Москва : Физматлит ; 
Ростов-на-Дону ‒ Таганрог : Издательство Южного федерального 
университета, 2019. – 287 с.

ISBN 978-5-9221-1792-0 (Издательство Физматлит)
ISBN 978-5-9275-3232-2 (Издательство ЮФУ)

Монография посвящена основам теории построения квантовых компьютеров. 

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

Работа выполнена в рамках проектной части госзадания Минобрнауки России 

№ 2.3928.2017/4.6, кафедра вычислительной техники Института компьютерных 
технологий и информационной безопасности Южного федерального университета.

УДК 004.38
ББК 32.973

ISBN 978-5-9221-1792-0 (Издательство Физматлит)
ISBN 978-5-9275-3232-2 (Издательство ЮФУ)

© Физматлит, 2019
© Гузик В. Ф., Гушанский С. М., 

Ляпунцова Е. В., Потапов В. С., 2019

© Оформление. Макет. Издательство 

Южного федерального университета, 2019

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ .............................................................................................. 7
ВВЕДЕНИЕ ...................................................................................................... 9
1. ОСНОВНЫЕ ПРИНЦИПЫ И МЕТОДЫ ПОСТРОЕНИЯ СКВ,
АКТУАЛЬНОСТЬ МОДЕЛИРОВАНИЯ ИХ ФУНКЦИОНИРОВАНИЯ .. 30

1.1. Основные понятия квантовой теории информации ........................... 30
1.2. Формализм квантовых вычислений.................................................... 33
1.3. Квантовые алгоритмы.......................................................................... 42
1.4. Квантовая запутанность и ее меры ..................................................... 47

2. ФИЗИЧЕСКАЯ РЕАЛИЗАЦИЯ КВУ ....................................................... 59

2.1. Использование низколежащих энергетических уровней ионов,

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

2.2. Ядерные спины с I = 1/2 и метод ядерно-магнитного резонанса 

(ЯМР) ...................................................................................................... 60

2.3. Использование двух спиновых или орбитальных электронных

состояний в квантовых точках............................................................... 63

2.4. Квантовый вычислитель на жидком гелии......................................... 64
2.5. Квантовый вычислитель на электронных волнах .............................. 66
2.6. Ионный кристалл как квантовый вычислитель.................................. 66
2.7. Квантовый вычислитель в алмазе ....................................................... 67
2.8. Использование квантовых электродинамических полостей и

фотонных кристаллов............................................................................. 68

2.9. Квантовый компьютер на основе углеродных нанотрубок ............... 69
2.10. Квантовый компьютер на миллиардах спинов................................. 70
2.11. Твердотельный квантовый чип ......................................................... 72
2.12. Анионы ............................................................................................... 73
2.13. Фотонный квантовый компьютер. Физическая аппаратура ............ 73
2.14. Оптические квантовые компьютеры................................................. 75
2.15. Схема для микроволнового захваченного ионного квантового 

компьютера............................................................................................. 79

2.16. Управление квантовыми гейтами азотно-замещённой 

вакансией в алмазе ................................................................................. 88

Оглавление

4

3. РАЗРАБОТКА МЕТОДИКИ ПОСТРОЕНИЯ МОДЕЛИ КВУ ..............109

3.1. Достижения и перспективы разработки и исследования модели 

квантового вычислителя.......................................................................109

3.2. Сравнение моделей квантовых вычислителей (МКВ)......................110

Архитектурные особенности МКВ............................................................................ 116
Программные особенности МКВ................................................................................ 118
Симуляция квантовых эффектов / физических процессов......................... 119
Пользовательский интерфейс МКВ........................................................................... 121
Прочее........................................................................................................................................... 123
Результаты сравнения и классификации сред моделирования................ 123

3.3. Оценка МКВ .......................................................................................125

Разработка обобщенной архитектуры моделирующей среды ................. 128
Разработка интерфейса пользователя....................................................................... 130
Интерфейс МКВ ..................................................................................................................... 133
Область манипуляции КС................................................................................................ 134
Область определения начального состояния квантовых битов .............. 135

3.4. Алгоритм исполнения моделирующей среды...................................139

4. АРХИТЕКТУРА СИМУЛЯТОРОВ КВУ................................................144

4.1. Симуляторы квантовых вычислительных устройств .......................144
4.2. Открытая архитектура симулятора квантового вычислителя..........153

Принципы открытой архитектуры симулятора КВ......................................... 153
Взаимодействие элементов симулятора  квантового вычислителя...... 153

4.3. Определение оптимального уровня модульности симулятора

квантового вычислителя.......................................................................155
Реализация в языках программирования ............................................................... 155
Модульная организация симулятора квантового вычислителя .............. 155
Оценка уровня модульности симулятора КВ...................................................... 156

4.4. Выполнение набора экспериментов по нахождению оптимального 

симулятора квантового вычислителя (СКВ) .......................................156
Выполнение полного или дробного набора экспериментов ..................... 157
Вывод матрицы набора экспериментов .................................................................. 158
Постановка задачи регрессионного анализа........................................................ 163

4.5. Классификация СКВ...........................................................................166

5. МОДЕЛИРОВАНИЕ КВАНТОВЫХ АЛГОРИТМОВ...........................178

5.1. Понятие квантового алгоритма..........................................................180
5.2. Общая структура квантового алгоритма...........................................183

Оглавление

5

5.3. Разработка квантовых алгоритмов.................................................... 188
5.4. Оценка сложности КА по функции трудоемкости........................... 191
5.5. Описание алгоритмов ........................................................................ 196

Алгоритм Дойча......................................................................................................................196
Алгоритмы, основанные на квантовых Фурье-преобразованиях...........197
Поисковый алгоритм Гровера........................................................................................197
Алгоритм факторизации Шора .....................................................................................198
Алгоритм нахождения периода функции...............................................................199
Алгоритм Бернштейна – Вазирани.............................................................................199
Алгоритм Залки – Визнера...............................................................................................200
Алгоритм Саймона................................................................................................................200
Алгоритмы, основанные на квантовом случайном блуждании...............202
Адиабатические квантовые алгоритмы ...................................................................205
Распознавание образов на квантовом компьютере ..........................................207
Квантовый алгоритм свёрточного декодирования Витерби......................209
Квантовый криптоанализ ..................................................................................................210
Абелева скрытая подгруппа ............................................................................................211
Неабелева скрытая подгруппа .......................................................................................212
Связное дерево.........................................................................................................................212
Квантовый алгоритм нахождения минимума функции ................................213
Квантовый алгоритм для нахождения подмножества ...................................213
Машинное обучение.............................................................................................................215
Квантовые алгоритмы контролируемого / неконтролируемого 
машинного обучения ...........................................................................................................219
Строковая перезапись..........................................................................................................220
Квантовые нейронные сети в процессах обучения и управления..........221
Квантовый алгоритм Монте – Карло ........................................................................223
Алгоритм квантового хеширования...........................................................................226
Программирование с «d-wave»: Алгоритм раскраски карты ....................229
Алгоритм двумерной упаковки.....................................................................................233
Алгоритм, усложняющий «экзаменационные задачи» для КвК .............237
Алгоритм квантового отжига .........................................................................................241

5.6. Классификация квантовых алгоритмов ............................................ 250
5.7. Реализация квантовых алгоритмов с применением запутанности и 

теории игр............................................................................................. 252

Оглавление

6

5.8. Использование задач теории игр в области квантовых 

вычислений ...........................................................................................265

5.9. Использование квантовых нейронных сетей для вычислений ........270

Влияние запутанного состояния на вычисления в квантовой 
нейронной сети........................................................................................................................ 271
Вычисление XOR-функции с помощью КНС..................................................... 273
Алгоритм обучения квантовой нейронной сети на основе 
суперпозиции ........................................................................................................................... 276

ЗАКЛЮЧЕНИЕ.............................................................................................278
СПИСОК ЛИТЕРАТУРЫ ............................................................................280

ПРЕДИСЛОВИЕ

В современной науке и технике постоянно возникает необходимость 

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

В последнее время наблюдается стремительный рост интереса к 

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

компьютерам возрос после того, как Канадская компания D-Wave Systems
объявила о продаже первого в мире коммерческого квантового компьютера 
«Орион» 
мощностью 
16 
кубитов. 
Его 
презентация 
прошла 
в 

Калифорнийской Силиконовой Долине, в музее компьютерной истории.

В настоящее время во многих передовых странах мира интенсивно 

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

Данная монография посвящена решению задачи исследования и 

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

Предисловие

8

В монографии приведены основные теоретические и практические 

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

университета (ВТ ИКТИБ ЮФУ) под руководством доктора технических 
наук, профессора Гузика В. Ф. занимаются более 15 лет.

Монография содержит анализ способов физической реализации 

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

На основе анализа семидесяти моделей разработана модульная модель 

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

Эти исследования подтверждают научную и практическую ценность 

монографии. Монография, выполненная в рамках проектной части 
Госзадания Минобрнауки России №2.3928.2017/4.6 кафедрой ВТ ИКТИБ 
ЮФУ, 
предназначена 
специалистам, 
работающим 
в 
области 

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

ВВЕДЕНИЕ

Квантовый компьютер (КвК) [1] – это вычислительный прибор, кото
рый основан на использовании
для вычислений таких квантово
механических явлений, как суперпозиция и запутывание (перепутывание) 
для преобразования входных данных в выходные. В классическом компьютере количество данных измеряется битами, а в квантовом компьютере –
кубитами. Основополагающий принцип квантовых вычислений состоит в 
использовании квантово-механических объектов для представления данных и их обработки [57].

Стремление повысить вычислительную мощность компьютеров и 

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

Интерес к квантовому компьютингу был стимулирован открытием в 

середине 1990-х гг. нескольких алгоритмов, позволяющих за рациональное 
время решать на таком устройстве безвыходные для обычного компьютера 
задачи. Хотя квантовые вычисления еще не готовы к переходу от теории к 
практике, тем не менее можно обоснованно догадываться, какую форму, 
возможно, квантовый компьютер примет или, что более важно для дизайна 
языка программирования, по какому интерфейсу можно будет взаимодействовать с таким квантовым компьютером [101].

Лет 20 назад ученым удалось создать искусственные ловушки для 

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