пришел звиздец RSA

http://www.vz.ru/society/2007/2/16/68719.html

[подредактировал название темы ввиду дикого количества пинков со стороны прогрессивной общественности]

 

грядут гамы на рей трейсе =)

 

1. Рано делать выводы, несколько лет еще у RSA есть
2. Но это же не теоретическое решение. Проблема NP-полноты - чисто математическая.
3. Непонятна фраза про аналоговую машину

4. Программировать параллельную обработку - искусство, будем учиться

 

Вот, и еще хочу сказать (для всех, особенно начинающих), что потребуется большое количество специалистов по алгоритмам параллельной обработки. Такие уже есть, но возникает качественно иная возможность их применения. Так что, вперед, к покорению кубитов.

 

Во-первых, как уже правильно заметил crypto, проблема P-NP не имеет никакого отношения к ускорению некоторых вычислений на квантовом компьютере. Во-вторых какое-то практическое значение будут иметь только системы начиная с сотен кубитов, тот же алгоритм Шора требует log(n) кубитов. Интересных фактов пока два: 1) первый раз рекорд поставлен коммерческой организацией 2) к концу 2008 они обещают 1024 кубита, подождем

 

Господа программисты, если они не гонят про 1024 бита за год-полтора, то, кажется, нам скоро придет конец. По крайней мере, традиционные языки программирования можно будет накрывать простыней и пускай ползут на кладбище.

 

Жаль, что не в России

 

Stiver

У меня этот факт вызывает тень сомнения в достоверности оглашённой информации.

Пока что мы и первые 16 пощупать не имеем возможности.

crypto

Проекты инструментов, умеющих распараллеливать задачи (как на уровне железа, так и на уровне софта) получат второе дыхание. Мне кажется, что их до настоящего времени слабо финансировали... Может, они решили утку запустить, чтоб денежек выбить из меценатов, гос. бюджетов и т.д.???...

 

http://www.ixbt.com/news/hard/index.shtml?07/80/44

 

В цифровой схемотехнике большинство алгоритмов рассчитаны на параллельную обработку.

 

Алгоритмы параллельной обработки никакого отношения к квантовым алгоритмам не имеют. То, что для моделирования 16-кубитного процессора нужно 2^16 обычных (работающих на той же частоте), не значит, что 16-кубитный процессор способен перебирать варианты в 2^16 раз быстрее. Для некоторых задач, есть более эффективные алгоритмы (никак не связанные с параллельными алгоритмами) на квантовом компьютере, но для подавляющего большинства задач таких алгоритмов нет. Поэтому использование квантовых компьютеров в 3d графике приведет лишь (в лучшем случае) к замедлению в пару миллионов раз.

 

интересно, но мало верится.. а вы подумали о о той монополии которая сейчас есть, даже если они это и реализуют в лучшем виде, то на конвеер не поставят, им просто не дадут сильные мира сего.. это же милионы рабочих мест, это значит что нужно выбросить на свалку оборудование которе стоит космические цены..
вспомните когда придумали паровой двигатель, то только через большой промежуток времени его начали использовать.
так что имхо в ближайшые лет 5-n нас это не коснётся

 

slackhead
Те же монополии купят разработчиков с потрохами и быстренько переориентируют производство, потому что капиталисты не дураки и новые триллионы долларов вряд ли упустят.

 

любое великое достижение лучше использовать, чем прятать
и это уже давно все поняли.
Сам не используешь - используют китайчеги

 

Сам Б. Гейтс в интервью на каком-то кабельном канале не так давно говорил, что пристально следит за новейшими разработками, часто посещает университеты и исследовательские центры, чтоб успеть перекупить то, что потенциально может перерости в ещё один Гугль или подобную угрозу его корпорации.

 

начал смотреть сериал Numb3rs - во второй серии 1-ого сезона вспоминали P vs NP, один герой пытался решить, но к концу серии бросил
качать тут: http://thepiratebay.org

 

кстати, а что, кто-то показал, что на квантовом компьютере можно решить хоть одну NP-полную задачу за полиномиальное время?

 

1) специалисты возможно но понадобятся. Потому как штука дорогая и вряд ли будет у кого попало иметься (скорее только у правительства)
2) то что она модет ломать RSA это не факт. Мы ничего про этот агрегат не знаем. Если подбирать ключ в 65536 раз быстрее, он всё равно не сломается.

 

Никто. Более того, на данный момент придумано лишь 4 алгоритма квантовых вычислений, которые реально лучше своих детерминированных аналогов:
Shor's algorithm, Grover's algorithm, Deutsch-Jozsa algorithm и сортировка.
См. http://en.wikipedia.org/wiki/Quantum_algorithm и далее по ссылкам.
NP-полнота тут никаким боком.

Про теорию сложности (в том числе и квантовую) можно почитать в книжке
А.Китаев, А.Шень, М.Вялый. "Классические и квантовые вычисления"
ftp://ftp.mccme.ru/users/vyalyi/qcomp/qps00205.zip

Вот еще обзорная статья "Квантовые компьютеры и квантовые вычисления": http://ifolder.ru/1181747

 

RElf
вот-вот!
Заголовкок темы не в тему получился...

а адрес книжки немного другой: ftp://ftp.mccme.ru/users/shen/quantum/qps00205.zip