Основы теории построения квантовых компьютеров и моделирование квантовых алгоритмов
Покупка
Основная коллекция
Тематика:
Квантовая электроника
Издательство:
Южный федеральный университет
Авторы:
Гузик Вячеслав Филиппович, Гушанский Сергей Михайлович, Ляпунцова Елена Вячеславовна, Потапов Виктор Сергеевич
Год издания: 2019
Кол-во страниц: 287
Дополнительно
Вид издания:
Монография
Уровень образования:
ВО - Магистратура
ISBN: 978-5-9275-3232-2
Артикул: 736661.01.99
Доступ онлайн
В корзину
Монография посвящена основам теории построения квантовых компьютеров. В ней рассмотрены физико-технические принципы построения современных квантовых вычислителей. Приводится описание разработанных спмуляторов квантовых вычислительных устройств. Описана разработанная открытая архитектура модели квантового вычислителя. Рассмотрена реализация широкого плана квантовых алгоритмов, предназначенных для реализации самых разнообразных задач науки и техники. Книга может быть полезна специалистам, работающим в области информационных технологий и вычислительной техники, а также студентам и аспирантам, обучающимся по этим специальностям. Работа выполнена в рамках проектной части госзадания Минобрнауки России №2.3928.2017/4.6, кафедра вычислительной техники Института компьютерных технологий и информационной безопасности Южного федерального университета.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Магистратура
- 02.04.02: Фундаментальная информатика и информационные технологии
- 09.04.01: Информатика и вычислительная техника
- 09.04.02: Информационные системы и технологии
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
. МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Инженерно-технологическая академия В. Ф. ГУЗИК, С. М. ГУШАНСКИЙ Е. В. ЛЯПУНЦОВА, В. С. ПОТАПОВ ОСНОВЫ ТЕОРИИ ПОСТРОЕНИЯ КВАНТОВЫХ КОМПЬЮТЕРОВ И МОДЕЛИРОВАНИЕ КВАНТОВЫХ АЛГОРИТМОВ Монография Москва ‒ Ростов-на-Дону ‒ Таганрог Физматлит ‒ Издательство Южного федерального университета 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 назад ученым удалось создать искусственные ловушки для одиночного иона (или атома), а в последние годы появились ловушки, в которых можно удерживать много атомов или ионов. В ловушках легко исследовать физические свойства изолированных атомов, управлять их излучением, воздействуя на атом извне световыми импульсами, электрическими и магнитными полями, меняя температуру. В случае большого количе
Введение 10 ства атомов – исследовать их коллективные свойства (в частности, сверххолодную жидкость – бозе – конденсат). В связи с появлением таких «макроатомов» возникла идея использо вать их для создания квантовых компьютеров. В них элементарной ячейкой-битом является один атом (ион) с двумя устойчивыми квантовыми состояниями. Такая ячейка памяти была названа кубитом (русское написание английского слова qubit, где qu – сокращение от quantum – квантовый). Переключения (переходы) между двумя состояниями кубита осуществляются при воздействии на атом (ион) излучения с частотой, равной расстоянию (в частотных единицах) между уровнями энергии атома. Важно понять, что и в гигантских ЭВМ, и в КвК действует один и тот же исходный принцип выбора между двумя разными информационными состояниями. Это может быть выбор между «0» и «1». Но может и между двумя квантовыми состояниями в атоме. Промышленных образцов квантового компьютера в природе пока нет. К настоящему времени формируются лишь принципы их работы, в лабораторных условиях созданы прототипы логических квантовых ячеек. Появление же реально действующих устройств – дело уже следующего века и всецело зависит от прогресса новейших высоких технологий, в том числе нанотехнологии, имеющей дело с микродеталями размером порядка длины световой волны и даже меньше, а также с прогрессом нанофотоники – науки, изучающей свойства и законы излучения атомов в нанорезонаторах. Известно, что корпорация IBM и ее исследовательский центр с 1998 по 2001 гг. продемонстрировали экспериментальные устройства в 2, 3, 5, 7 кубитов, громко названные квантовыми компьютерами. Однако они относятся, скорее, не к КвК, а к проблеме квантовой информации, криптографии и телепортации. Тем более, что неустойчивость в работе этих установок сами их создатели объясняли «нарушением когерентности состояний». Физик-теоретик Владислав Фёдорович Чельцов, область его научных интересов – разработка теории управления излучением атомов с помощью микрорезонаторов (чаще используется другой термин – нанорезонатор), что имеет прямое отношение к проблеме создания так называемых квантовых компьютеров (КвК) – является крупным учёным в области КвК. На эти исследования его благословили когда-то академики М. Леонтович и Р. Хохлов, представлявшие к защите кандидатскую диссертацию Чельцова. В области развития КвК он отмечает следующее: миниатюризация
Введение 11 компьютерной техники может дойти буквально до размеров длины световой волны. Его оценка в развитии КвК лет 10 назад была скромной, носила попу лярный характер, и время, необходимое для создания КвК, отнюдь не связывалось с началом нового века. У промышленного, или, как теперь говорят, коммерческого, устойчиво работающего КвК, когда его на самом деле создадут, будут два потрясающих преимущества. Прежде всего, для отдельных его модулей мы будем иметь дело с размерами порядка световой волны. А усиление быстродействия будет связано со скоростями излучения и поглощения фотонов в специальных устройствах (от 108 до 1018 см/с). Из чего следуют все остальные преимущества и нынешние рекламно-фантастические их интерпретации. На пути к КвК возникает целый ряд задач фундаментального свойства. И в их решении в начале нового века действительно достигнуты серьезные результаты, которые, конечно же, были бы невозможны без концентрации значительного исследовательского потенциала. В Соединенных Штатах, при Университете штата Нью-Мексико на средства гранта Национального научного фонда США в 2005 г. создан Центр квантовой информации и контроля. При нем работает научный семинар, где с сообщениями выступают специалисты стран, прямо или косвенно ведущих исследования по созданию квантовых компьютеров. В эти исследования вложены большие средства, и в них участвуют многие научные коллективы США, Канады, Австрии, Германии, Норвегии, Франции, Швеции, Швейцарии. В Соединенных Штатах эти исследования ведутся в таких крупных научных центрах, как Национальная лаборатория Сандиа (термоядерный синтез), Национальная лаборатория в Лос-Аламосе (ядерная физика), Национальный институт стандартов и технологий в Боулдере, Калифорнийский институт технологий, Массачусетский институт технологий, а также в университетах отдельных штатов, располагающих соответствующей экспериментальной базой. Практически при каждом крупном университете США и других стран-участников этих работ созданы аналогичные центры. В феврале 2007 г. СМИ обнародовали сенсацию: первый в мире ком мерческий КвК мощностью 16 кубитов – его назвали «Орион» – создан ка
Введение 12 надской компанией D-Wave Systems. Его презентация прошла в Калифорнийской Силиконовой Долине, в Музее компьютерной истории. В интернете можно найти довольно оптимистические прогнозы, свя занные с этим событием. Вот, например, один из них, размещенный под заголовком «Квантовый компьютер: революция в электронике» на сайте «Наука. «Известия» (inauka.ru): «По оценкам, квантовый компьютер должен был родиться лишь к 2030 г. По мнению профессора Центра квантовых вычислений Оксфордского университета Эндрю Штайна, построить работающий квантовый компьютер – все равно что овладеть холодным термоядерным синтезом. Уже в 2008 г. D-Wave собирается создать систему в 1000 кубитов, что позволит обрабатывать больше потоков данных, чем существует частиц во Вселенной. Доступ программистов для работы с «Орионом» будет открыт уже в 2007 г. Среди первых задач квантовых компьютеров – предсказание погоды и расчет климатических изменений, создание онкологических препаратов, обработка сигналов из Вселенной для поиска внеземных цивилизаций. Вместе с тем квантовый компьютер, который никто не собирается засекречивать, моментально сделает легковесной всю современную криптографию, все кодовые системы, что вызовет хаос в областях, связанных с безопасностью и конфиденциальностью. Что касается сенсаций, в том числе и о создании КвК мощностью 1000 кубитов и других, профессор В. Чельцев считает, что здесь просто имеет место путаница между так называемой квантовой телепортацией и квантовым компьютером. В престижном научном журнале «Природа. Физика» (№ 10.Т.2, 2006) опубликована статья о квантовой телепортации с использованием двух кубитов как у отправителя, так и у получателя. Среди прорывов 2009 г. физики выделяют дебют квантового компью тера – прототипное устройство было представлено в ноябре и получило одобрение научного сообщества (с подробностями можно ознакомиться на Physics world.com). Собственно, прорыв был двухступенчатым: в августе Джонатан Хоум (Jonathan Home) из Национального института стандартов и технологий (National Institute of Standardsand Technology) и его коллеги сообщили о первом устройстве, которое получило условное название квантового компьютера. Это был чип, который выполнял ряд квантовых логических операций без потери информации. Над его созданием ученые работали не один год. Но к концу 2009 г. наконец удалось объединить все промежуточные
Введение 13 достижения в единое устройство, что, по мнению редакции специализированного портала Physicsworld, является настолько важным этапом, что его можно выделить в категорию «Прорыв года в области физики». Устройство (рис. В.1) даже выглядит немного похожим на чип первого поколения компьютеров, но, как отмечает Physics world, не следует ожидать, что «скоро будет запущена квантовая версия операционной системы Windows». Рис. В.1. Внешний вид КвК Точность выполнения операций квантовым чипом составляет 94 %, что впечатляет, если принять во внимание пионерский опыт квантовых вычислений, однако этого совершенно недостаточно для полноценного использования компьютера, в котором объединено много таких процессоров. Здесь требуется точность 99,99 %. Эксперты в сфере квантовых вычислений характеризуют работу кол лег из Национального института стандартов и технологий как большой шаг вперед. Борис Блинов (Boris Blinov) из Вашингтонского университета (University of Washington) в Сиэтле назвал ее tour-de-force, т.е. проявлением высочайшей изобретательности. Речь идет о работе группы под руководством Дэвида Ханнеке (David Hanneke), в которую вошел и Джонатан Хоум, сообщивший в ноябре о создании квантового компьютера на двух ионах бериллия, удерживаемых магнитной ловушкой при температуре, близкой к абсолютному нулю. Эти ионы представляют собой кубиты (квантовые биты), и система из двух ионов бериллия под влиянием ультрафиолетовых лазерных импульсов выполнила, по меньшей мере, 160 различных операций квантового вычисления.
Доступ онлайн
В корзину