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

[flacs]

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

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

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

[rtfai]

Что-то подобное мы делаем, но без громких слов о моделировании работы КК.

http://www.mathnet.ru/php/archive.phtml ... n_lang=rus

если интересно дайте мейл, вышлю текст.

Сейчас с помощью такого подхода мы определяем 65% бит сомножителей и есть надежда на 80%.

[Joker_vD]

Нет, это невозможно. Хотя бы потому, что это настолько очевидная идея, что ее гарантировано уже попробовали — и отбросили, потому как вы сами знаете, что проблема факторизации на классических ЭВМ за полиномиальное время до сих пор открыта.

И я даже догадываюсь, в чем тут фокус. Вот например — какая временная сложность у алгоритма Гаусса решения СЛАУ? Экспоненциальная или кубическая?