Квантовые вычисления. Теория и практика
Покупка
Новинка
Тематика:
Квантовая механика
Издательство:
Издательский Дом НИТУ «МИСиС»
Автор:
Ширкин Сергей Владимирович
Год издания: 2024
Кол-во страниц: 203
Дополнительно
Вид издания:
Учебник
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-907833-10-4
Артикул: 882917.01.99
В учебнике рассматриваются основные принципы квантовых вычислений, работа многокубитных схем квантовых компьютеров, физические и математические основы квантовых алгоритмов, а также их конкретные примеры: алгоритмы Дойча, Саймона, Бернштейна - Вазирани, Гровера, Шора и т.д. Учебник содержит задания с решениями и примеры практических работ, в которых рассматривается создание программ для квантовых симуляторов и квантовых компьютеров, написанные с использованием Python. Предназначен для студентов, обучающихся в магистратуре по направлениям подготовки 01.03.04 «Прикладная математика», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика».
Тематика:
ББК:
УДК:
ОКСО:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Москва 2024 МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ УНИВЕРСИТЕТ НАУКИ И ТЕХНОЛОГИЙ МИСИС ИНСТИТУТ КОМПЬЮТЕРНЫХ НАУК Кафедра инженерной кибернетики С.В. Ширкин КВАНТОВЫЕ ВЫЧИСЛЕНИЯ ТЕОРИЯ И ПРАКТИКА Учебник Рекомендовано редакционно-издательским советом университета № 4500
УДК 51:004.8 Ш64 Р е ц е н з е н т ы : канд. канд. техн. наук, доц., НИТУ МИСИС А. И. Широков; канд. техн. наук, доц., кафедра МЭУ РГГУ С. В. Никифоров Ширкин, Сергей Владимирович. Ш64 Квантовые вычисления. Теория и практика : учебник / С.В. Ширкин. – Москва : Издательский Дом НИТУ МИСИС, 2024. – 202 с. ISBN 978-5-907833-10-4 В учебнике рассматриваются основные принципы квантовых вычислений, работа многокубитных схем квантовых компьютеров, физические и математические основы квантовых алгоритмов, а также их конкретные примеры: алгоритмы Дойча, Саймона, Бернштейна – Вазирани, Гровера, Шора и т.д. Учебник содержит задания с решениями и примеры практических работ, в которых рассматривается создание программ для квантовых симуляторов и квантовых компьютеров, написанные с использованием Python. Предназначен для студентов, обучающихся в магистратуре по направлениям подготовки 01.03.04 «Прикладная математика», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика». УДК 51:004.8 Ширкин С. В., 2024 ISBN 978-5-907833-10-4 НИТУ МИСИС, 2024
Оглавление Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 Глава 1. Основные понятия квантовых вычислений . . . . . . .9 1.1. Кубит . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.2. Квантовые вычисления в искусственном интеллекте . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 1.3. Основные типы реализаций квантовых компьютеров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 1.4. Программные средства для квантовых вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15 1.5. Суперпозиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 1.6. Операции в классическом и квантовом компьютере . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18 1.7. Гильбертово пространство и скалярное произведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24 1.8. Тензорное произведение . . . . . . . . . . . . . . . . . . . . . . .27 1.9. Квантовый вентиль X . . . . . . . . . . . . . . . . . . . . . . . . .30 1.10. Эрмитовы и унитарные матрицы . . . . . . . . . . . . . . .32 1.11. Оператор Адамара . . . . . . . . . . . . . . . . . . . . . . . . . . .35 1.12. Процесс квантовых вычислений . . . . . . . . . . . . . . .37 1.13. Сфера Блоха . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 1.14. Теорема о запрете клонирования . . . . . . . . . . . . . . .42 1.15. Изображение квантовой схемы . . . . . . . . . . . . . . . .44 1.16. Квантовые вентили S и T . . . . . . . . . . . . . . . . . . . . .46 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . .48 Глава 2. Многокубитные операции . . . . . . . . . . . . . . . . . . . .50 2.1. Оператор CNOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
Оглавление 2.2. Квантовая запутанность . . . . . . . . . . . . . . . . . . . . . . .52 2.3. Операторы CZ и CY . . . . . . . . . . . . . . . . . . . . . . . . . . .57 2.4. Вентиль Тоффоли . . . . . . . . . . . . . . . . . . . . . . . . . . . .62 2.5. Оператор SWAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64 2.6. Вентиль Фредкина . . . . . . . . . . . . . . . . . . . . . . . . . . .66 2.7. Логические операторы . . . . . . . . . . . . . . . . . . . . . . . .68 2.8. Квантовая телепортация . . . . . . . . . . . . . . . . . . . . . .69 2.9. Сверхплотное кодирование . . . . . . . . . . . . . . . . . . . .75 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . .79 Глава 3. Сложность квантовых алгоритмов . . . . . . . . . . . . .81 3.1. Сложность алгоритмов . . . . . . . . . . . . . . . . . . . . . . . .81 3.2. Классы P и NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .85 3.3. Классы BPP и BQP . . . . . . . . . . . . . . . . . . . . . . . . . . .87 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . .89 Глава 4. Задача Дойча . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91 4.1. Постановка и решение задачи Дойча . . . . . . . . . . . . .91 4.2. Задача Дойча – Йожи . . . . . . . . . . . . . . . . . . . . . . . . .98 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . .105 Глава 5. Алгоритм Саймона . . . . . . . . . . . . . . . . . . . . . . . .106 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . .114 Глава 6. Алгоритм Бернштейна – Вазирани . . . . . . . . . . .115 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . .118 Глава 7. Алгоритм Гровера . . . . . . . . . . . . . . . . . . . . . . . . .119 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . .129 Глава 8. Алгоритм Шора . . . . . . . . . . . . . . . . . . . . . . . . . . .130 8.1. Асимметричное шифрование . . . . . . . . . . . . . . . . . .130
Оглавление 8.2. Квантовое преобразование Фурье . . . . . . . . . . . . . .137 8.3. Алгоритм Шора . . . . . . . . . . . . . . . . . . . . . . . . . . . . .149 Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . .157 Библиографический список . . . . . . . . . . . . . . . . . . . . . . . .158 Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159 Приложение 1. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . .159 Приложение 2. Решения задач . . . . . . . . . . . . . . . . . . . .164 Приложение 3. Глоссарий . . . . . . . . . . . . . . . . . . . . . . . .190 Приложение 4. Программирование с использованием Qiskit . . . . . . . . . . . . . . . . . . . . . . . . . .195 П4.1. Создание квантовой запутанности ...................195 П4.2. Реализация алгоритма квантовой телепортации ........................................................197 П4.3. Реализация алгоритма Гровера .......................199
ПРЕДИСЛОВИЕ Квантовые вычисления – это перспективное направление информационных технологий, которое изучает вычисления с использованием законов квантовой физики, в частности, с применением таких эффектов, как суперпозиция и квантовая запутанность. Квантовые вычисления на практике стали возможны с появлением первых квантовых компьютеров, хотя теоретические основы таких вычислений, как и многие квантовые алгоритмы, были заложены раньше. В наше время квантовые компьютеры, как правило, располагаются в лабораториях, в которых созданы необходимые условия для их работы, но уже появились и первые настольные квантовые компьютеры, хотя и с очень скромными возможностями. Так как при изучении квантовых вычислений нет необходимости в непосредственной работе с квантовыми компьютерами, то и нет необходимости посещать лаборатории (разве что для расширения кругозора либо при разработке железа для компьютеров), так как с определенного времени стало возможным работать на квантовых компьютерах дистанционно, получая к ним доступ как к сервису. Для студентов, изучающих квантовые вычисления, квантовый компьютер важен не как цель, а скорее как средство. Квантовый компьютер вполне может находиться в нескольких тысячах километров от студента, а подключиться к нему можно зачастую через облачный сервис. Для работы с таким компьютером не понадобятся какая-то особая квантовая клавиатура, квантовая мышь или квантовый монитор, так как в качестве «терминала», обеспечивающего работу с вводимой и выводимой информацией, может использоваться обычный классический компьютер, в роли которого может выступить стационарный ПК, ноутбук, планшет или даже обычный смартфон. Главное, чтобы в таком устройстве была среда разработки или обычный интернет-браузер, с по
Предисловие мощью которого можно при необходимости создавать программы и запускать их в облачном сервисе. Но даже если облачный сервис недоступен или в том случае, когда требуется отладка небольших частей программы, достаточно будет использовать квантовый симулятор, встроенный в библиотеку квантовых вычислений. Также нужно понимать, что программный код, используемый в квантовых вычислениях, достаточно прост по сравнению с теорией квантовых вычислений, поэтому в данном издании основное внимание уделено математике квантовых вычислений, хотя программная часть также присутствует. На основе полученных знаний можно будет писать небольшие программы, реализующие алгоритмы квантовых вычислений, но основная сложность состоит не в создании программного кода как такового, а в понимании математики операций, которые этот код запускает. Для написания программ мы будем использовать язык программирования Python. Этот язык является наиболее распространенным в искусственном интеллекте, также он стал востребованным в квантовых вычислениях. Для специалистов по квантовым вычислениям, так же как и для специалистов по искусственному интеллекту (ИИ) важно, чтобы программы можно было создавать быстро. Интерфейс библиотек, используемых как в ИИ, так и в квантовых вычислениях, достаточно простой. При этом сами библиотеки ИИ написаны на быстрых языках программирования – C/C++, Fortran и т.д., так что тот факт, что Python не самый быстрый язык программирования, не влияет на скорость работы нейронных сетей и других столь же сложных моделей ИИ. В квантовых вычислениях ситуация аналогичная – библиотеки Python для квантовых вычислений используют синтаксис Python для ввода команд, а наиболее важная часть программы, та, в которой важна скорость, переводится квантовым компилятором в команды более низкого уровня, кото
Предисловие рые затем выполняются на квантовом компьютере. Использовать язык с более сложным синтаксисом не имеет смысла, так как в любом случае наиболее сложные расчеты будут производиться на квантовом компьютере. Также не нужно забывать, что важна не только скорость работы программ, но и скорость их разработки, так как время программистов является важным ресурсом. Программы на Python создаются на порядок быстрее, чем на многих других языках программирования. Настолько же быстро производится отладка программ и поиск ошибок в них, что также очень важно для работоспособности программ. Если у вас есть какие-то знания по квантовой физике, то они могут вам пригодиться в этом курсе, но все-таки квантовые вычисления – это самостоятельное направление, которое требует знания лишь отдельных разделов квантовой физики, хотя более полное знание этой науки, конечно, позволит отдельные вещи понимать глубже. Так что если параллельно с изучением квантовых вычислений вы будете изучать и квантовую физику, это будет только в плюс. Но нужно знать, что в этом курсе все же будет дана наиболее необходимая (хотя и краткая) информация по квантовой физике, без которой изучать квантовые вычисления невозможно. Помимо разделов квантовой физики необходимо знать основы линейной алгебры и комплексных чисел. Если линейная алгебра в наши дни широко используется во многих ИТ-дисциплинах, особенно в искусственном интеллекте, то комплексные числа не настолько распространены в ИТ, но в процессе прохождения данного предмета вы поймете, что в квантовых вычислениях без них не обойтись.
ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ КВАНТОВЫХ ВЫЧИСЛЕНИЙ 1.1. Кубит Кубит – основная единица информации в квантовых вычислениях. Это слово происходит от соединения слов quantum и bit, так что этот термин дословно можно перевести как квантовый бит. Если в классических вычислениях бит может находиться только в двух состояниях – 0 и 1, то с кубитом все гораздо сложнее: он может быть сразу в двух состояниях одновременно. Для начала разберемся с опытом Штерна – Герлаха, сыгравшем важную роль в квантовой физике. В начальной части установки, задействованной в данном опыте, расположен источник атомов серебра, из которого атомы выходят в виде пучка. Этот пучок проходит между двух магнитов – нижнего, повернутого южной стороной вверх, и верхнего магнита, у которого северный полюс направлен вниз. У верхнего магнита заострен нижний конец, так что возле заостренной части создается большая, чем в нижней части, концентрация линий магнитного поля. На рис. 1.1 изображена упрощенная схема опыта. Если представить, что каждый атом серебра – это небольшой магнит, а также предположить, что он повернут южной стороной к верхнему магниту, то за счет большей концентрации линий магнитного поля на верхнем магните атом серебра будет больше притягиваться к верхнему магниту, чем к нижнему. В обратном случае, когда атом серебра повернут северной стороной вверх, он будет сильнее отталкиваться от верхнего магнита, чем от нижнего. Но, конечно же, атом может располагаться и в одном из промежуточных начальных положений. До проведения опыта считалось, что атом серебра в таком случае в результате прохождения между
магнитами не отклонится строго вверх или вниз, а пойдет по некоторому промежуточному пути. N S Рис. 1.1. Опыт Штерна – Герлаха Для того чтобы узнать этот путь, в конце прибора расположили пластинку, на которую должны попадать атомы серебра. В соответствии с предсказаниями классической физики атомы серебра, попадающие на пластинку, должны образовывать непрерывную полоску, так как северный и южный полюсы каждого из них будут по-разному ориентированы относительно верхнего и нижнего магнита, так что они будут отклоняться на разный угол при прохождении через прибор. Но после того как опыт был произведен, оказалось, что атомы серебра отклонились либо вверх, либо вниз, так что вместо полоски на пластинке образовалось