Основы теории построения квантовых компьютеров и моделирование квантовых алгоритмов (373,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

Стр.7

. МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Инженерно-технологическая академия В. Ф. ГУЗИК, С. М. ГУШАНСКИЙ Е. В. ЛЯПУНЦОВА, В. С. ПОТАПОВ ОСНОВЫ ТЕОРИИ ПОСТРОЕНИЯ КВАНТОВЫХ КОМПЬЮТЕРОВ И МОДЕЛИРОВАНИЕ КВАНТОВЫХ АЛГОРИТМОВ Монография Москва ‒ Ростов-на-Дону ‒ Таганрог Физматлит ‒ Издательство Южного федерального университета 2019

Стр.2

УДК 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

Стр.3

ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ .............................................................................................. 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 3

Стр.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 4

Стр.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 5

Стр.6

Оглавление 5.8. Использование задач теории игр в области квантовых вычислений ........................................................................................... 265 5.9. Использование квантовых нейронных сетей для вычислений ........ 270 Влияние запутанного состояния на вычисления в квантовой нейронной сети........................................................................................................................ 271 Вычисление XOR-функции с помощью КНС ..................................................... 273 Алгоритм обучения квантовой нейронной сети на основе суперпозиции ........................................................................................................................... 276 ЗАКЛЮЧЕНИЕ ............................................................................................. 278 СПИСОК ЛИТЕРАТУРЫ ............................................................................ 280 6

Стр.7