Квантовые компьютеры научили вычислять пи-функцию
Значение пи-функции для первых 60 натуральных значенийИспанские ученые Хосе Латорре и Герман Сьерра из университетов Барселоны и Мадрида предложили эффективный квантовый алгоритм вычисления пи-функции. Препринт статьи исследователей доступен на сайте arXiv.org, сама статья пока не подана в рецензируемый журнал.
Пи-функция π (k) равна количеству простых (то есть делящихся на себя и на единицу) чисел, не превосходящих k. Эта функция представляет собой важнейший элемент современной теории чисел и, следовательно, криптографии. Знаменитая гипотеза Римана о нулях дзета-функции эквивалентна утверждению об оценки скорости роста π (k).
В рамках работы ученые рассматривали систему из n кубитов - квантовых битов, способных находиться в суперпозиции двух состояний. При помощи последовательного применения уже известных квантовых алгоритмов (например, алгоритм Гровера для поиска решения уравнений для булевых функций) построить состояние, которое соответствует некоей суперпозиции всех простых чисел, не превосходящих 2n. Это состояние ученые назвали простым состоянием (prime state).
Сами ученые предлагают несколько способов использования полученного состояния. Так, например, его можно применять для подсчета количества простых чисел-близнецов. Это простые числа, разность между которыми равна двум. До сих пор неизвестно, конечно или бесконечно множество таких чисел.
Использование преобразования Фурье (точнее его квантового аналога) позволяет приблизительно вычислять значение π (2n). По утверждению исследователей, это вычисление выполняется гораздо эффективнее классических алгоритмов. Сами ученые предлагают свой алгоритм для экспериментальной проверки гипотезы Римана.
