УДК 519.688, 510.52

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

Шемякина Марина Андреевна – студент магистратуры Института сферы обслуживания и предпринимательства (филиала) Донского государственного технического университета в г. Шахты.

Аннотация: Статья посвящена исследованию квантовых вычислений, а именно квантовым алгоритмам. Были рассмотрены три квантовых алгоритма: алгоритм Дойча (демонстрирует преимущество квантовых вычислений перед классическими); алгоритм Гровера (представляет квантовый алгоритм поиска); алгоритм Шора (решает задачу факторизации). Показаны основные преимущества перед классическими алгоритмами, а также представлено их моделирование на классическом компьютере.

Ключевые слова: Квантовый бит, квантовые вычисления, квантовый алгоритм Дойча, Квантовый алгоритм Гровера, квантовый алгоритм Шора.

Как уже отмечалось в [1], квантовая парадигма вычислений позволяет решать задачи, которые невозможно решить, используя классическую парадигму вычислений. Однако в настоящее время не существует полноценного квантового компьютера, поэтому исследование квантовых алгоритмов возможно на данный момент только моделируя их на классическом компьютере.

1. Квантовый алгоритм Дойча

 Данный алгоритм демонстрирует принципы квантового параллелизма, который позволяет вычислять значение некоторой двоичной функции одновременно на всём множестве входных значений. Цель задачи Дойча – определить, является ли функция ƒ, реализованная в черном ящике, константой или сбалансированной. Ясно, что при использовании классических вычислений одного вызова функции недостаточно. Необходимо вызвать ее для каждого параметра, т.е. два раза. Квантовый алгоритм Дойча позволяет определить, является ли функция ƒ(х) константой или сбалансированной при помощи только одного вычисления ƒ(х).

2. Квантовый алгоритм Гровера

В 1996 году американский математик Лов Гровер разработал квантовый алгоритм поиска, который также называют алгоритмом Гровера. Полученный алгоритм можно использовать не только для поиска некоторого параметра в заданном неупорядоченном пространстве, но и для ускорения многих классических алгоритмов, в которых используется метод перебора. Классический алгоритм решает описанную задачу методом перебора, в лучшем случае х будет найден с первой попытки, а в худшем придётся перебрать 2n вариантов. Алгоритм Гровера позволяет ускорить метод поиска – до O( ) операций [2].

3. Квантовый алгоритм Шора

В 1994 году американский ученый Питер Шор разработал квантовый алгоритм, который получил название – алгоритм факторизации или алгоритм Шора [3]. Данный алгоритм позволяет решить задачу факторизации, т.е. разложить составное число на множители. На данный момент не существует классического алгоритма, который смог бы эффективно за полиномиальное время решить данную задачу.

4. Реализация программной системы

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

На рисунке 1 представлена архитектура проектируемой системы.

1

Рисунок 1. Диаграмма сервис-ориентированной архитектуры.

На рисунке 2 приведена диаграмма классов для реализуемой программной системы.

2

Рисунок 2. Диаграммы классов.

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

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

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

3

Рисунок 3. Диаграмма деятельности алгоритма Дойча.

Если введенные данные корректны, система переходит к выполнению квантовой части.

На рисунке 4 представлена диаграмма деятельности для алгоритма Гровера. Выполнение алгоритма Гровера также, как и алгоритма Дойча, начинается с проверки данных, которые были введены пользователем. Если данные некорректны, тогда система должна попросить пользователя повторить ввод. Данные считаются некорректными, если:

  • были введены буквы и другие символы;
  • в поле для ввода пространства поиска были введены цифры от 2 до 9;
  • для каждого элемента пространства поиска было введено больше одной цифры;
  • в поля для ввода количества выполнений итерации Гровера и количество выполнений квантовой части были введены отрицательные значения.

4

Рисунок 4. Диаграмма деятельности для алгоритма Гровера.

Когда введенные данные корректны, поток управления переходит к выполнению квантовой части алгоритма.

Диаграмма деятельности для алгоритма Шора представлена на рисунке 5. Также, как и в двух предыдущих случаях, выполнение алгоритма Шора начинается с проверки данных, которые были введены пользователем. Если данные некорректны, тогда система должна предложить пользователю повторить ввод. Данные считаются некорректными, если:

  • были введены буквы и другие символы;
  • были введены отрицательные значения.

5

Рисунок 5. Диаграмма деятельности для алгоритма Шора.

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

Заключение

В результате проведенного исследования были сделаны следующие выводы:

  1. В рамках квантовых вычислений для некоторых задач можно реализовывать более эффективные алгоритмы, чем в классических вычислениях.
  2. Создание квантовых компьютеров позволит решить проблему экспоненциального роста сложности алгоритмов.
  3. Эмуляция алгоритмов возможна на классических компьютерах, но при этом не было обнаружено никакой выгоды по сравнению с классической вычислительной моделью.
  4. Квантовые алгоритмы эффективны только на квантовых компьютерах и на больших входных данных.

Результаты исследования свидетельствуют, что квантовые вычисления можно эмулировать на классическом компьютере на небольшом размере входных данных.

Список литературы

  1. Шемякина М.А. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ. КЛАССИФИКАЦИЯ КВАНТОВЫХ АЛГОРИТМОВ // Modernscience. М., 2019. — № 12-1. — С. 642-645.
  2. Гуц А.К. Основы квантовой кибернетики. – Омск: Полиграфический центр КАН, 2008. – 204 с.
  3. Душкин Р. В. Квантовые вычисления и функциональное программирование. — 2014 г. — 318 с., ил.
  4. Ляшов М.В., Берёза А.Н., Бабаев А.М., Алексеенко Ю.В., Авдеева Т.Г. Применение сервис-ориентированной архитектуры для создания распределенных вычислительных систем // Фундаментальные исследования. – 2016. – № 10-2. – С. 312-316.

Интересная статья? Поделись ей с другими: