mi3ch Голосов: 2 Адрес блога: http://mi3ch.livejournal.com/ Добавлен: 2007-10-21 03:56:21 блограйдером Lurk

делить и отнимать

2016-11-30 23:02:11 (читать в оригинале)



Из статьи Ильи Ферапонтова «Навстречу квантовой катастрофе»

Однажды утром у вас не получится отправить электронную почту. По странному совпадению, одновременно упадут все мессенджеры, не откроется фейсбук и еще добрая половина сайтов в интернете. Зависнет и ваше банковское приложение. Вы выйдете на улицу и обнаружите, что банки заперты, банкоматы выключены, а в немногих открытых магазинах принимают только наличные. Перед вами постепенно вырисовывается картина тотальной катастрофы: финансовая система страны полностью парализована, в государственных учреждениях хаос. Надо немедленно бежать — но купить билет на самолет тоже невозможно...

Теракт? Война?! Нет, никакой войны нет, террористы ни при чем. Просто кто-то наконец построил квантовый компьютер.


Поднимите глаза к адресной строке вашего браузера. В самом начале там стоят буквы https. Это последнее s означает, что данные, которыми вы обмениваетесь, шифруются по протоколу SSL.

Криптографические технологии сопровождают вас постоянно. Вы сталкиваетесь с шифрованием всякий раз, когда снимаете деньги в банкомате или заходите в банковское приложение, когда пишете сообщение в мессенджере, когда отправляете электронную почту. Современная банковская система, документооборот крупных компаний, государственные сервисы, системы связи немыслимы без криптографических технологий, не говоря уже о военных и спецслужбах.

Значительная часть этого инструментария основана на использовании асимметрии умножения и обратной операции — разложения на множители. Допустим, вам надо перемножить два двузначных числа — например, 19 и 41. Если вы не обладаете феноменальными способностями, вы станете делать это в столбик, и вся процедура займет у вас, видимо, секунд десять. Если числа трехзначные, времени потребуется чуть больше. Перемножьте пятизначные числа — тут придется повозиться несколько минут, но в целом с увеличением числа знаков время вашего вычисления будет расти почти линейно. Числа увеличились в 10 раз, а время возросло на чуть-чуть.

А теперь скажите, пожалуйста, какие два целых числа надо умножить друг на друга, чтобы получить 391. Промучившись над этой задачкой некоторое время, вы, наверное, все же дадите ответ: 23 х 17. Теперь попробуем другое число: 4717. Что-то нам подсказывает, что эту задачу вы и вовсе не сможете решить без таблиц (ответ на нее: 53 х 89). Число увеличилось опять же в десять раз, но сложность задачи, то есть продолжительность вычисления возрастает экспоненциально.

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

Но при чем тут шифры? А вот при чем. Чтобы обмениваться шифрованными сообщениями, оба участника переписки должны знать общий шифр: один участник шифрует с его помощью сообщение, другой расшифровывает. Но это значит, что в какой-то момент они должны обменяться самим шифром, который кто-то может перехватить (говорят, именно такая неприятность и довела до эшафота Марию Стюарт, королеву Шотландии). Тут-то и приходит на помощь несправедливая асимметрия операций умножения и разложения на множители. На ней основана технология шифрования с открытым ключом.

Ключ к расшифровке — два достаточно больших целых числа (это «закрытый ключ»). Но, чтобы зашифровать сообщение, достаточно знать их произведение («открытый ключ»). Желая получить от вас шифрованную весточку, я просто передам вам это произведение, а сами числа сохраню в тайне. И если наша переписка попадет к злоумышленнику, он может заняться разложением «открытого ключа» на простые множители — если у него есть в запасе 800 тысяч лет. Потому что его компьютер никак не сумеет справиться с этой задачей быстрее.

Если, конечно, его компьютер не квантовый.

Квантовая хитрость

Идее квантового компьютера чуть больше 35 лет — в 1980 году ее мимоходом высказал советский математик Юрий Манин:



Годом позже нобелевский лауреат Ричард Фейнман впервые предложил использовать для моделирования поведения квантовых систем... другие квантовые системы — «квантовые симуляторы». Универсальный квантовый симулятор — это, собственно, и есть квантовый компьютер. Поскольку среднестатистическому читателю эта фраза, скорее всего, ровно ничего не говорит, придется дать небольшое пояснение.

В классическом компьютере процессор обрабатывает нули и единицы — «биты» информации. По сути сам компьютер состоит из ячеек, которые могут быть в состоянии 0 или 1, причем состояние каждой ячейки меняется по определенным правилам в зависимости от состояния других ячеек, каждая из которых в любой момент времени тоже или 0, или 1.

В квантовом компьютере все то же самое, но без слова «или». Квантовая ячейка — «кубит» — находится в суперпозиции двух состояний, подобно опостылевшему всем Шредингерову коту, который жив и мертв одновременно.

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

В его наглядном объяснении квантовая суперпозиция — например, пресловутый полуживой кот или кубит в квантовом компьютере — это не один кот или кубит, а огромное (возможно, бесконечное) число котов или кубитов, проживающих в параллельных вселенных. Каждый кот или жив, или мертв, и вероятность обнаружить в нашей вселенной живого кота, рассчитываемая по формулам квантовой механики, — это просто доля вселенных, в которых кот жив. Или, соответственно, доля вселенных, где кубит принял значение 1.

Чтобы сделать много однотипных вычислений (например, на калькуляторе), вам надо набрать исходные числа, нажать кнопку «=», получить результат, потом повторять процедуру нужное число раз. А теперь представьте себе, что множество ваших копий, рассевшись по параллельным вселенным, одновременно сделают по одному вычислению. Насколько же быстрее пойдет работа!

Именно так, по существу, работает квантовый компьютер.

Впрочем, эта наглядная картинка, при всей ее доходчивости, никак не поможет вам его изобрести. Ученые, занятые проблемой квантовых вычислений, обычно не заморачиваются с параллельными вселенными, используя куда более скучный вариант квантовой механики со всеми ее зубодробительными формулами и без малейшей наглядности. Результат, однако, тот же: число операций, совершаемых за один шаг, стремительно возрастает.

В частности, в 1994 году математик Питер Шор показал, что задача разложения на множители для квантового компьютера будет столь же нехитрой, как обычное умножение: время вычисления будет возрастать с увеличением длины числа одинаково плавно и медленно для обеих операций. Если опять перевести эту хитрость на язык параллельных вселенных, то для разложения на множители 250-значного числа этих вселенных понадобится 10 в пятисотой степени... зато времени — всего минуты. В результате большинство существующих сегодня криптографических систем будут взломаны. Алгоритм Шора очень прост, и для решения этой задачи потребуется квантовый компьютер всего с несколькими сотнями кубитов.

Дело за малым — построить этот самый компьютер.

Насколько все ужасно?

Вряд ли квантовый компьютер удастся сделать незаметно, как сложно было бы сделать незаметно атомную бомбу. Но если это будет сделано, вся инфраструктура современной цивилизации может оказаться под угрозой.

«Это можно назвать информационной атомной бомбой. Если кто-то вдруг окажется обладателем квантового вычислительного устройства, он может устроить для нашей цивилизации настоящую катастрофу — может, например, украсть все деньги в банках, выведать любые военные секреты», — говорит профессор Университета Калгари Александр Львовский, научный руководитель проекта по квантовой криптографии в Российском квантовом центре.

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

Дэниэл Бернстайн из Университета Иллинойса в Чикаго не исключает, что придется вернуться к дорогим и неудобным «физическим» методам защиты данных — например, передавать информацию на флешке в закрытом на замок кейсе, пристегнутом наручниками к запястью доверенного курьера.

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

«Квантовая технология дает нам и противоядие против “квантового хакерства” — криптографические алгоритмы, безопасность которых основывается на фундаментальных физических законах и не по зубам даже квантовому компьютеру», — говорит Львовский. Весь вопрос в том, что будет первым: броня или снаряд.

Сам Львовский является научным руководителем проекта по квантовой криптографии в РКЦ. Эта технология основана не на сверхнадежных методах шифрования, а на снижении риска подслушивания. Информация кодируется в квантовых состояниях фотонов, и если кто-то измеряет их, то это состояние неминуемо меняется. Впрочем, уже сейчас в квантовой криптографии находят уязвимости, связанные с неидеальной работой квантовых устройств.

Вопрос времени

Когда ждать катастрофы? Видимо, когда удастся придумать сам кубит. В принципе, кубиты могут быть созданы на базе самых разных квантовых объектов — ионов, электронов, фотонов. Проблема с ними в том, что все такие объекты в реальных устройствах очень быстро перестают «быть квантовыми», то есть теряют состояние суперпозиции (эту неприятность физики называют «декогеренцией»).

Самыми перспективными на данный момент считаются сверхпроводящие кубиты на базе контактов Джозефсона, микроскопических петель из сверхпроводников, которые в определенной точке разомкнуты тонким слоем диэлектрика — оксидной пленки. Такие петли ведут себя как искусственные квантовые объекты, и технология их создания уже хорошо отработана. Их можно встраивать в обычные электронные схемы. Увы, работают они только при температурах, близких к абсолютному нулю.

Квантовый компьютер может быть создан в течение 10 лет, считает профессор Технологического института Карлсруэ Алексей Устинов, с участием которого был создан первый в России сверхпроводящий кубит. По его словам, это уже чисто инженерная задача. Но «инженерная» не значит «простая». Пока ученым удается удерживать кубиты в когерентном состоянии лишь доли секунды. А ведь нужно удержать это состояние не на одном кубите, а минимум на десятках, и к тому же достаточно времени, чтобы успеть сделать вычисление, то есть заставить кубиты провзаимодействовать.

В решение этой задачи вкладываются миллионы долларов. Свои проекты по созданию квантовых компьютеров развивают Google, IBM, Microsoft, многие государства.

Наиболее известный проект в этой сфере — квантовое вычислительное устройство канадской компании D-Wave, которое состоит из тысяч кубитов. Однако это не «настоящий» квантовый компьютер, а квантовый симулятор, устройство, способное решать одну задачу — задачу квантового отжига, поиска минимума очень сложной функции. Разработчики не так давно заявили, что при решении этой задачи им удалось обнаружить квантовую «прибавку скорости».

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

Наше дело — предупредить читателя о том, к чему это приведет. Чтобы, столкнувшись однажды с утра с неработающим интернетом и зависшими банкоматами, тот не впал в панику, а порадовался за человечество, взявшее еще один рубеж на пути познания.