2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Возможно ли ускорение факторизации числа симуляцией квантовы
Сообщение30.11.2013, 19:43 


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

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

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

 Профиль  
                  
 
 Re: Возможно ли ускорение факторизации числа симуляцией квантовы
Сообщение17.12.2013, 06:04 


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

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

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

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

 Профиль  
                  
 
 Re: Возможно ли ускорение факторизации числа симуляцией квантовы
Сообщение01.01.2014, 01:36 
Заслуженный участник


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group