Завершает ли алгоритм Шора поиск алгоритмов факторинга в квантовом мире вычислений?

10

Другими словами, останутся ли исследования факторинга исключительно в классическом мире или в квантовом мире проводятся интересные исследования, связанные с факторингом?

Р. Шопен
источник
1
Знание одного алгоритма для эффективного решения проблемы не означает, что нет других алгоритмов, которые были бы лучше (в целом или в определенных обстоятельствах)
GLS
2
Вы спрашиваете, был ли алгоритм Шора доказан оптимальным, или вы спрашиваете, все еще полезно ли исследование классических алгоритмов факторинга?
ahelwer
Я спрашиваю последнее. Я уверен, что поиск продолжится в классическом мире, потому что никто не знает, существует ли быстрое решение или нет, но как насчет квантовых вычислений? Все ли довольны алгоритмом Шора до точки перехода в другие области?
Р. Шопен
1
Я думаю, что вы имеете в виду «останутся ли исследования факторинга исключительно в классическом мире ...»
Марк С.

Ответы:

7

Асимптотически алгоритм Шора действительно эффективен. В основном это просто: суперпозиция, модульное возведение в степень (самый медленный шаг) и преобразование Фурье. Модульное возведение в степень - это то, что вы делаете для фактического использования криптосистемы RSA. Это означает, что для квантового компьютера законное шифрование / дешифрование RSA будет примерно такой же скоростью, как при использовании алгоритма Шора для взлома системы. Поэтому я скептически отношусь к тому, что в основной идее будут какие-то улучшения.

Тем не менее, любое улучшение целочисленного сложения, целочисленного умножения или квантового преобразования Фурье улучшило бы алгоритм Шора, и это все очень общие подпрограммы, над которыми люди почти наверняка будут работать. Короткий поиск в Google Scholar показывает множество исследований по улучшению квантовых арифметических схем.

Я думаю, что будет больше исследований классических / квантовых компромиссов в алгоритме Шора. То есть, если у вас небольшой или шумный квантовый компьютер, можете ли вы изменить алгоритм Шора так, чтобы он все еще работал, но, возможно, потребуется гораздо больше предварительной и последующей обработки на классическом компьютере или, возможно, с меньшей вероятностью успеха, так далее.? В этой области есть квантовые алгоритмы для вычисления коротких дискретных логарифмов и факторизации целых чисел RSA . Есть также сито поля квантовых чиселподход, при котором «маленький» квантовый компьютер (слишком мал, чтобы использовать алгоритм Шора напрямую) используется в качестве подпрограммы сита с классическим числовым полем, немного улучшая сложность времени (хотя я лично убежден, что для исправления ошибок для этого потребуется больше физические кубиты, чем алгоритм ванили Шора).

Короче говоря, я не ожидаю каких-либо радикально новых алгоритмов квантового факторинга, и я не думаю, что кто-то работает над этим. Но есть много интересных твиков, которые нужно сделать, чтобы соответствовать конкретным случаям использования.

Сэм Жак
источник
1
Я полагаю, вы найдете Post-квант RSA интересным чтением. Большое спасибо за интересные ссылки, добавленные в ваш ответ.
Р. Шопен
2

Как дополнение к ответу Сэма:

Нет, отчасти потому, что подход Шора - не единственный способ факторизации чисел.

Факторизация также может быть записана как задача оптимизации .

Эту проблему можно решить с помощью машины D-Wave , а также с помощью квантового компьютера на основе затвора .

ниппон
источник
1

Напомним, что алгоритм Шора реализован в модели вычислений гейта .

(N-ИксY)2ИксYN

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

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

Смотрите более подробную информацию в этой статье Пэн, Ляо, Сюй, Ган Цинь, Чжоу, Сутер и Ду - их фиг. 3 моделирования времени выполнения предполагают квадратичное соответствие; Однако; Я не уверен, было ли проведено какое-либо дальнейшее исследование, чтобы доказать такое соответствие или предоставить больше доказательств даже полиномиального времени выполнения.

Метки
источник