Возможно ли ускорение факторизации числа симуляцией квантовых вычислений?

Question

[flacs]

Всем известно, что факторизация числа, задача с большой вычислительной сложностью.
Лучшие алгоритмы раскладывают полупростое число на множители за субэкспоненциальное время, но не полиминальное. Факторизация с полиноминальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора.
В принципе, симуляция простейших квантовых операторов(вентилей) возможна и на классическом компьютере. Все сводиться в основном к операциям над матрицами. Операции над которыми, можно распаралелить на N компьютерах.

Теперь собственно вопрос:
Если мы применим распараллеливание вычислений для операций над матрицами в сети из компьютеров, возможно ли то, что мы можем потратить меньше времени (в О-нотации), чем если бы мы пользовались стандартными алгоритмами факторизации?

Прошу дать конструктивный ответ.

Answer 1

[Tyranron]

Теоретически и bruteforce можно распараллелить так, чтобы каждая машина проверяла всего один вариант, но тогда нам надо кол-во равное кол-ву операций, тогда bruteforce будет мгновенным, но где столько машин то взять?)
То-есть нужно брать листочек и карандаш (или клаву и какой-нибудь python), и рассчитывать оптимальные соотношения времени выполнения к количеству ресурсов. Если получаются варианты, которые можно реализовать в реальном мире - тогда да, если нет - увы.
Все же склоняюсь к варианту "нет", иначе много умников уже бы давно поломали RSA, DH, и иже с ними, так как известно, что квантовый компьютер - смерть асимметричной криптографии (полная ли?). Да и симуляция - всего лишь симуляция, и работает медленнее задуманного оригинала. Ведь если мы Жигулям присобачим корпус Тойоты, то ездить как Тойота Жигули не станут)...а если переделать все внутри как у Тойоты, то это уже будут не Жигули, а Тойота)
Насчет последней фразы - могу ошибаться, так как не знаю тонкостей реализации симуляторов и КК (квантового компьютера).