Исследование методов реализации квантовых алгоритмов для решения задачи поиска данных

ВВЕДЕНИЕ
ГЛАВА 1 АНАЛИЗ АЛГОРИТМОВ ПОИСКА ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ
1.1Классические алгоритмы поиска данных
1.1.1Последовательный поиск
1.1.2Бинарный поиск
1.1.2Интерполяционный поиск
1.1.4 Поиск на основе Хеша
1.2Квантовые алгоритмы поиска данных
1.2.1Алгоритм Гровера.
1.2.2Алгоритмы квантового поиска
1.3Сравнительный анализ классических и квантовых алгоритмов
ГЛАВА 2 ОПИСАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ АЛГОРИТМА
ГРОВЕРА
2.^Классические вычисления
2.2Квантовые вычисления
2.2.1Квантовые состояния и кубиты
2.2.2Несколько кубит
2.2.3Гейты и квантовые схемы
2.2.4Квантовая схемотехника
2.2.5Принципы квантовых вычислений
2.2.6Общая архитектура квантового компьютера
2.3Математическая модель алгоритма Гровера
ГЛАВА 3 РЕАЛИЗАЦИЯ КВАНТОВОГО АЛГОРИТМА
3.1Язык программирования Q#
3.2Язык программирования Haskell 3.2.1Строгая типизация Haskell
3.2.2Программное обеспечение Haskell
3.3Язык программирования Quipper
3.4Описание функциональности компьютерной модели алгоритма Гровера. ГЛАВА 4
РЕЗУЛЬТАТЫ КОМПЬЮТЕРНОГО МОДЕЛИРОВАНИЯ
4.1Результаты расчета компьютерной модели алгоритма Гровера
4.2Сравнительный анализ компьютерной модели на Q# и классической
компьютерной модели на языке С++
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А
ПРИЛОЖЕНИЕ Б
Купить

В последние годы было проведено значительное количество
исследований по квантовым компьютерам – машинам, которые используют
квантово-механические явления для решения математических задач, которые
трудны или трудноразрешимы для обычных компьютеров. Такой вывод можно
сделать на основании:
1. В 2016 году продажу поступает квантовый компьютер D-
Wave2000Q с процессором на 2000 кубит по цене 15 000 000 долларов [0].
2. В 2013 году компания Google купила квантовый компьютер у
компании D-Wave [59].
3. Компания D-Wave, которая занимается постройкой квантовых
вычислительных систем, получила заказ на установку своего нового устройства
D-Wave 2X, которое содержит более 1 тысячи кубитов, в лаборатории
квантового искусственного интеллекта, совместной лаборатории НАСА и
Google, говорится в пресс-релизе компании. Новая установка будет
использоваться для исследований в области машинного обучения,
искусственного интеллекта и в других областях [59].
4. Группа исследователей компании Google под руководством Джона
Мартиниса уже близка к созданию первого универсального квантового
компьютера, который, возможно, сможет превзойти классические
суперкомпьютеры. Как пишет MIT Technology Review, ученые, знакомые с
ходом работы лаборатории Мартиниса, уверены, что уже в 2017 году он может
представить квантовый компьютер с чипом на 50 кубитов [50].
5. Ученые Российского квантового центра, МФТИ (Лаборатория
искусственных квантовых систем при участии Технологического центра),
создали первый в России сверхпроводящий кубит - основной элемент будущих
квантовых компьютеров, которые смогут превзойти самые мощные
современные суперкомпьютеры. Это важный шаг, необходимый для созданияквантовых вычислительных устройств, которые в будущем произведут
революцию в области вычислительной техники [39].
6. Правительство Нидерландов приняло решение вложить 135
миллионов евро в разработку технологий квантовых вычислений, говорится в
сообщении на сайте голландского кабинета министров [48].
7. Компания D-Wave нуждается в том, чтобы привлечь больше
программистов к созданию приложений для своих машин. Для этого
специалисты разработали новый программный инструмент Qbsolv, который
позволит разрабатывать программы для машин D-Wave, не вникая в квантово-
механические тонкости. Этот инструмент позволит создать сообщество
«квантовых» программистов, чтобы расширить потенциальную базу для этого
сообщества, код программы выложен в открытый доступ, и все желающие
смогут модифицировать его «под себя» [49].
8. IBM позволяет заинтересованным людям получить доступ к 5-
кубитному квантовому компьютеру под названием IBM Quantum Experience.
Оборудование размещено в исследовательской лаборатории IBM в штате Нью-
Йорк. Компания предоставляет программный интерфейс и возможность запуска
экспериментальной программы на реальном квантовом компьютере [50].
9. IBM сообщила о создании рабочего прототипа 50-кубитного
квантового процессора. Это большой шаг вперед по сравнению с предыдущим
достижением компании — 17-кубитным квантовым компьютером [43].
10. Компания Google построила квантовый процессор, в котором 72
сверхпроводниковых кубита объединены в двумерный массив. Этот процессор
использует ту же технологию, что и предыдущий 9-кубитный квантовый
компьютер, построенный компанией и имеющий низкий процент ошибок при
вычислениях. Новую разработку компания представила на ежегодной встрече
Американского физического сообщества в Лос-Анджелесе, кратко о ней
сообщается в блоге компании [54].На основе выше сказанного можно сделать вывод о том, что крупные IT
компании и государственные организации вкладывают в квантовые вычисления
большие ресурсы и данная тема исследования является актуальной.
Научная проблема заключается в том, что в большинство квантовых
алгоритмов не реализованы в виде компьютерной модели.
Цель исследования:анализ и математическое моделирование квантовых
алгоритмов, и программная реализация квантовых алгоритмов на языке Q#.
Объект исследования:задача поиска данных.
Предмет исследования: алгоритмы решения задачи поиска данных.
Для решения цели исследования сформулированы и решены следующие
задачи:
исследование классических алгоритмов поиска данных;
исследование квантового Алгоритма Гровера;
исследование алгоритмов квантового поиска;
математическое моделирование рассматриваемых квантовых
алгоритмов;
сравнение квантовых алгоритмов с классическими;
исследование языков программирования для реализации квантовых
вычислений;
разработка программы, реализующий квантовый алгоритм с
помощью языка программирования Q#;
отладка и параметрическое исследование предложенной
программы.
Апробация работы была представлена на следующих конференциях:
III Международная научно-практическая конференция (школе-
семинаре) молодых ученых «Прикладная математика и информатика:
современные исследования в области естественных и технических наук»,
Тольятти, 2017 г.IV Международная научно-практическая конференция (школе-семинаре)
молодых ученых «Прикладная математика и информатика: современные
исследования в области естественных и технических наук», Тольятти, 2018 г.
Научная новизна состоит в том, что квантовые алгоритмы реализованы
на языке Q#.
Теоретические основы исследования включают использование трудов
отечественных и зарубежных авторов по исследованию классических
алгоритмов поиска данных и квантовых алгоритмов поиска данных.
Теоретическая значимость заключается в описании квантовых
алгоритмов поиска.
Практическая значимость состоит в том, что были подобраны
наилучшие алгоритмы, решающие задачу поиска данных, реализованы на языке
программирования, что позволит при разработке квантового компьютера
запустить на нем данную программу.
Достоверность и обоснованность научных положений и выводов,
сделанных в магистерской диссертации, следует из адекватности
математических моделей, используемых в работе, подтверждается сравнением
результатов данной работы с известными экспериментальными
итеоретическими данными, полученными ранее другими авторами.
Основные положения, выносимые на защиту:
1. Превосходство квантовых алгоритмов над классическими
алгоритмами.
2. Компьютерная модель квантового алгоритма Гровера на языке Q#.
Диссертация состоит из введения, четырех глав, заключения, списка
литературы и приложения. Объем диссертации составляет 90 страниц и
содержит 22 рисунка, список литературы включает 59 наименование
источников отечественных и зарубежных авторов.
В первой главе диссертации описываются классические и квантовые
алгоритмы поиска сортированных и несортированных данных, проводитсясравнительный анализ алгоритмов и выполняется постановка задачи
исследования.
Во второй главе проводится описание квантовых вычислений и
описывается построение математической модели.
В третьей главе описывается язык программирования, используемый для
квантовых вычислений, программное обеспечение которое нужно для
использования данного языка и описываются функции компьютерной модели.
Программный продукт состоит из тела программы и функций, реализующих
алгоритмы: математической модели, функцию черного ящика, а также
унитарные операции. Проводится результат компьютерного моделирования
трехкубитного квантового компьютера при корректных и некорректных
данных.
В четвертой главе описываются результаты компьютерной модели
разработанной на языке программирования Q#. Проводится сравнительный
анализ с классической компьютерной моделью на языке С++.
В заключении описаны выводы результатов работы программного
продукта.
В приложение А находится листинг кода программного продукта.
Купить