Эксперименты с квантовым вычислением и алгоритмом Шора
- Небольшая теоретическая справка
- Что в репозитории
- Как запустить
- Использованные материалы
Факторизацией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики.
В отличие от задачи распознавания простоты числа, факторизация предположительно является вычислительно сложной задачей. В настоящее время неизвестно, существует ли эффективный алгоритм факторизации целых чисел. Даже самым современным алгоритмам требуется экспоненциальное время, чтобы найти коэффициенты целого числа. Это означает, что с достаточно большими числами решить эту задачу практически невозможно, несмотря на огромную вычислительную мощность. Однако доказательства того, что не существует решения этой задачи за полиномиальное время, также нет.
Предположение о том, что для больших чисел задача факторизации является вычислительно сложной, лежит в основе широко используемых алгоритмов (например, RSA).
В 1994 году Питер Шор теоретизировал алгоритм квантовых вычислений с полиномиальным временем для целочисленной факторизации. Алгоритм Шора использует как классические, так и квантовые (определение периода) вычисления. Однако преобладающая оптимизация алгоритма Шора обусловлена эффективностью квантового преобразования Фурье и модульным возведением в степень путем многократного возведения в квадрат.
Алгоритм Шора, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование).Таким образом, реализация масштабируемого квантового компьютера поставит крест на большей части современной криптографической защиты. Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом.
Важно отметить, что алгоритм Шора имеет вероятностный характер. Первый источник случайности встроен в классическое вероятностное сведение разложения на множители к нахождению периода некоторой функции. Второй источник появляется из необходимости наблюдения квантовой памяти, которое также даёт случайные результаты.
Директория books содержит книги, статьи и прочие материалы, которые использовались для работы.
Директория src содержит исходный код проекта.
Директория report содержит данные для отчета и сам отчет по работе.
Программа написана для запуска на квантовом симуляторе от IBM. Воспользоваться им можно на данном сайте.
Можно также запустить код локально. Для этого понадобятся следующие зависимости:
pip install numpy
pip install qiskit
Также в коде потребуется заменить бэкэнд вычислений.
# для выполнения на симуляторе IBMQ
simulation = execute(circuit, backend = provider.get_backend('ibmq_qasm_simulator'), shots = number_shots)
# для выполнения на стандартном симуляторе
simulation = execute(circuit, backend = Aer.get_backend('qasm_simulator'), shots = number_shots)Можно попробовать запустить программу и на реальной квантовой машине с достаточным количеством кубитов. Сам я не тестировал этого))).
Список материалов, которые были использованы мной для изучения данной темы и написания программы:
-
Сысоев С. С. Введение в квантовые вычисления. Издательство Санкт-Петербургского государственного университета, 2019. 7–109 с.
-
Курс "Квантовые вычисления (Quantum computing)" Электронный ресурс
-
Документация IBM Quantum Электронный ресурс
-
Документация к библиотеке Qiskit Электронный ресурс