Информация

Дата основания
Местоположение
Россия
Сайт
misis.ru
Численность
5 001–10 000 человек
Дата регистрации

Блог на Хабре

Обновить
Комментарии 12
Насколько я помню квантовые компьютеры представляют реальную опасность только для RSA алгоритма (и то начиная от 1000 с хвостиком кубит), у которого есть стойкий аналог ECC, и при малейшем намёке на наличие квантовой машины всё сведётся замене сертификатов и паре патчей для ПО.

Алгоритм Шора решает и задачу разложения числа на множители (RSA) и задачу дискретного логарифмирования (DLP), причем как в поле вычетов, так и на эллиптических кривых (ECC, ECDLP):
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf LECTURE 3: Quantum attacks on elliptic curve cryptography, 2008


Shor’s algorithm, which can calculate discrete logarithms over any cyclic group. In particular, this algorithm can be used to break the Diffie-Hellman key exchange protocol, which assumes that the discrete log problem in Z^x_p (p prime) is hard. However, Shor’s algorithm also breaks elliptic curve cryptography, the main competitor to RSA.… Ironically, Shor’s algorithm takes a comparable number of steps for both factoring and discrete log (regardless of the group involved)

http://arxiv.org/pdf/quant-ph/0301141v2.pdf Shor’s discrete logarithm quantum algorithm for
elliptic curves 2008


It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits.

http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf Алгоритм Шора, АФТУ РАН 2010


В результате получается квантовое решение задачи дискретного логарифма. Эллиптические кривые не спасают — для любой коммутативной группы работает, нужно только умножать уметь.
Мы взломали всю коммутативную криптографию. Что делать? Один ответ — строить квантовую криптографию. Другой ответ — строить некоммутативную криптографию.

См https://en.wikipedia.org/wiki/Post-quantum_cryptography "… cryptographic algorithms (usually public-key algorithms) that are thought to be secure against an attack by a quantum computer."

Что- то в последнее время память меня подводит, но пока можно успокоить себя тем, что даже такие слабые версии требуют много кубит.
Да, можно себя успокоить, что для взлома биткойновой криптографии надо 6*256 = 1536 кубит
http://arxiv.org/pdf/quant-ph/0301141v2.pdf

А квантовый компьютер Google недавно проапргейдили до 1000+ кубит

http://www.wired.com/2015/09/googles-quantum-computer-just-got-a-big-upgrade-1000-qubits/

Спите спокойно, граждане Багдада.

Ну так где-то доказано, что задача оптимизации D-Wave не подходит для взлома шифров?

Какие конкретно операции из алгоритма Шора D-Wave не умеет делать или эти операции нельзя свести к задаче оптимизации?

а где сказано обратное? еслибы гугл реально обладал настоящим квантовым компьютером первым делом бы доказали его «квантовость» взломом ослабленного шифра — скажем бита так 64.
Интересное мнение. Но логическое продолжение — рассказ про квантовую коррекцию ошибок — отсутствует напрочь. Я в этом не силен, но говорят какие-то успехи есть. Причем подходы к этому совершенно разные — от слабых измерений до тупой мажоритарной логики.
Лучший способ изучить процессор — написать его эмулятор.
Кажется, для квантового компьютера их всего один, от гугла, на javascript.
Сложная тема.
Тут не только эмулятор но и реальный
http://www-03.ibm.com/press/us/en/pressrelease/49661.wss

http://habrahabr.ru/post/185936

также ссылки на алгоритмы для квантовых компов
Кстати, а как у квантовых устройств будет обстоять дело с достоверностью расчетов, которая даже на «классике», является проблемой.
Ссылки:
http://www.cs.utep.edu/interval-comp/yakovlev.pdf
http://www2.math.uni-wuppertal.de/~xsc/xsc/pxsc_download.html
«Также завтра мы опубликуем этот материал на нашем портале, где, возможно, между нашими экспертами, молодыми исследователями и автором развернется самая настоящая научная дискуссия. Вероятно, кто-то из уважаемых читателей захочет присоединиться к дискуссии на нашем портале.»
Не могли бы дать ответ здесь или на вашем портале?

Добрый день! Ответ от А.М. Загоскина:


Здравствуйте! Этот вопрос‎ в первую очередь касается цифровых компьютеров и напрямую связан с вопросом о квантовой коррекции ошибок и о пределах применимости математической модели. Для аналоговых устройств все в каком-то смысле проще — их точность ограничена, но пока уравнения для моделируемой системы и для аналогового «решателя» одни и те же, ответ будет приблизительно верным.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.