Max Home IndustryНовый квантовый алгоритм позволяет вычислять ряд функций простых чисел далеко за пределами возможностей обычного компьютера. Возможно даже, что это могло бы решить гипотезу Римана на миллион долларов.
Квантовые компьютеры сейчас в моде, но их очень сложно сделать. До сих пор нам удавалось создавать машины, в которых небольшое количество кубитов — 4 или 5 — и самый известный квантовый алгоритм, факторинг Шора, на практике сумел разложить только значение 15. Учитывая, что для того, чтобы превзойти возможности обычных машин, квантовому компьютеру потребуется около 1000 кубитов, мы все еще далеки от успешного реального приложения.
Итак, если бы вы искали потенциальную проблему реального мира для квантового компьютера, вы бы искали более простую или более сложную проблему?
Оказывается, задача вычисления различных функций простых чисел сложнее, но, как это ни парадоксально, более многообещающе для реального квантового компьютера.
Наиболее известной из функций простых чисел является π (x), которая дает количество простых чисел, меньших или равных x. Обратите внимание, что это дает распределение простых чисел по всем числам, и в этом смысле это фундамент теории чисел. Проблема в том, что эту функцию сложно разработать, и в настоящее время мы знаем ее значения только до x = 1024. Теорема о простых числах утверждает, что π (x) ≈Li (x) при увеличении x, а Li — это логарифмический интеграл, который намного легче вычислить.
Связь с гипотезой Римана состоит в том, что если она верна, то разница между π (x) и Li (x) должна быть порядка √x log x. Итак, если вы можете экспериментально показать, что расхождение намного больше, чем это, вы можете сделать вывод, что гипотеза Римана неверна, и потребовать миллион долларов от Института математики Клэя.
Чтобы сделать это с помощью обычного компьютера, потребуется очень и очень много времени, и в настоящее время это выходит далеко за рамки того, на что мы могли бы надеяться.
Однако Хосе Латорре из Университета Барселоны в Испании вместе с Херманом Сьеррой из Автономного университета Мадрида построили квантовый алгоритм, который может сопоставить π (1024), используя только 80-кубитную машину (т.е. вам нужно около 80 бит для представления 1024). Ключом к алгоритму является создание запутанного состояния кубита, в котором участвуют только простые числа.
Например, для n = 3 состояние будет следующим:
где стрелки представляют состояния вращения каждого из трех битов, необходимых для представления значения от 0 до 7.
Тот факт, что такое состояние вообще можно построить, вызывает удивление, но все, что для этого нужно, — это перевод на квантовые термины классического алгоритма проверки простоты. В данном примере используется хорошо известный тест Миллера-Рабина для построения простого состояния. Идея состоит в том, чтобы использовать алгоритм поиска Гровера с тестом на простоту в качестве оракула для выбора только простых элементов из суперпозиции всех возможных состояний.
Последний алгоритм может построить простое состояние примерно за √n операций, и как только у вас есть простое состояние, его можно подвергнуть квантовому счетному алгоритму для получения π (n) или другим алгоритмам для создания связанных функций.
Здесь у нас есть квантовый алгоритм, который может предоставить нам новую информацию с использованием квантового оборудования, которое значительно меньше, чем, скажем, для алгоритма Шора. Обратите внимание, однако, что этот экспериментальный подход может только опровергнуть гипотезу Римана. Если результаты согласуются с гипотезой Римана, то это не доказательство, а просто отсутствие противоречия, которое может все еще существовать при больших значениях n.