Bristlecone. Парамет­ры компь­юте­ра точ­но неиз­вес­тны. Видимо, они были неидеаль­ны, потому что о кван­товом пре­вос­ходс­тве в Google загово­рили лишь в октябре 2019 года, а дос­тичь его уда­лось на 53-кубит­ном компь­юте­ре Sycamore. info Кван­товым пре­вос­ходс­твом называ­ют ситу­ацию, ког­да кван­товый компь­ютер реша­ет такую задачу, которая прос­тому компь­юте­ру не по зубам. За 200 секунд Sycamore получил резуль­тат, который клас­сичес­кий супер­компь­ютер искал бы 10 тысяч лет. Хотя в Intel компь­ютер­ное пре­вос­ходс­тво Google оспо­рили и в целом ока­залось, что задача была искусс­твен­но сос­тавле­на под резуль­тат, ста­ло ясно, что в рай­оне 50 кубит находит­ся гра­ница, за которой кван­товый компь­ютер может «побить» клас­сичес­кий. Прав­да, толь­ко в узком клас­се спе­цифи­чес­ких задач. В кон­це 2020 года китай­ские иссле­дова­тели из Науч­но‑тех­ничес­кого уни­вер­ситета Китая объ­яви­ли о решении на их кван­товом компь­юте­ре задачи, которая в прин­ципе не может быть решена на клас­сичес­ком компь­юте­ре, пос­коль­ку для это­го пот­ребова­лось бы вре­мя, рав­ное полови­не жиз­ни Зем­ли. Ис­сле­дова­тели из IBM в то же вре­мя заяви­ли, что уже в 2021 году пла­ниру­ют пос­тро­ить кван­товый компь­ютер с 127 кубита­ми, в 2022 году они наде­ются иметь 433 кубита, в 2023 году 1121 кубит, а далее они видят пер­спек­тиву дой­ти аж до мил­лиона кубитов и более. Пла­нов гро­мадье! Проб­лема, одна­ко, не толь­ко в количес­тве кубитов. При работе кван­товых вен­тилей, то есть при выпол­нении уни­тар­ных опе­раций над кубита­ми, неиз­бежно воз­ника­ют ошиб­ки. Их веро­ятность невели­ка, но не нулевая. В про­цес­се вычис­лений ошиб­ки накап­лива­ются, и без кор­рекции труд­но получить пра­виль­ный резуль­тат. Под дей­стви­ем окру­жающей сре­ды про­исхо­дит декоге­рен­ция сис­темы, то есть раз­рушение ее кван­тового сос­тояния (сос­тояния запутан­ности кубитов изо­лиро­ван­ной сис­темы). Вре­мя декоге­рен­ции, то есть вре­мя под­держа­ния сис­темы кубитов изо­лиро­ван­ной от окру­жающей сре­ды, — прин­ципи­аль­ный фак­тор при пос­тро­ении боль­шого кван­тового компь­юте­ра. Если это вре­мя мень­ше вре­мени, необ­ходимо­го для кван­товых вычис­лений, в сис­теме при вычис­лении воз­ника­ют ошиб­ки и в резуль­тате вычис­лений мы получим толь­ко ран­домизи­рован­ный шум. Изо­ляция сис­темы, умень­шение уров­ня оши­бок на вен­тилях и соз­дание эффектив­ных алго­рит­мов, кор­ректи­рующих ошиб­ки, — эти нап­равле­ния работы ста­новят­ся в пос­леднее вре­мя при­ори­тет­ными и активно раз­рабыты­вают­ся в ведущих иссле­дова­тель­ских цен­трах. Что­бы кор­ректи­ровать ошиб­ки, в кван­товых алго­рит­мах при­меня­ются логичес­кие кубиты, сос­тоящие из нес­коль­ких физичес­ких кубитов. Сос­тояние еди­нич­ного кубита кодиру­ется в перепу­тан­ных сос­тояниях нес­коль­ких кубитов. Поэто­му в кван­товом компь­юте­ре с кор­рекци­ей оши­бок реаль­ных кубитов пот­ребу­ется нам­ного боль­ше. Нап­ример, один из пер­вых пред­ложен­ных для кор­рекции оши­бок 7-кубито­вый код Сти­на (Stean) исполь­зует семь кубитов для хра­нения одной еди­ницы (кубита) кван­товой информа­ции. Па­рал­лель­но с работой над физичес­кой реали­заци­ей кван­тового компь­юте­ра раз­рабаты­вают­ся кван­товые алго­рит­мы. На при­лав­ках уже появи­лись науч­но‑популяр­ные бро­шюры, помога­ющие всем жела­ющим начать изу­чать осно­вы кван­тового прог­рамми­рова­ния. Осо­бое мес­то занима­ет про­ект IBM Quantum Experience, поз­воля­ющий соз­давать кван­товые алго­рит­мы и запус­кать их на кван­товых компь­юте­рах IBM и симуля­торах. При­меры выпущен­ных в пос­леднее вре­мя популяр­ных бро­шюр, пос­вящен­ных кван­товым вычис­лени­ямОт себя пореко­мен­дую упо­мяну­тый фун­дамен­таль­ный труд Ниль­сена и Чан­га, нас­читыва­ющий уже десяток пере­изда­ний. Есть перевод на рус­ский язык одно­го из пер­вых изда­ний, кни­га называ­ется «Кван­товые вычис­ления и кван­товая информа­ция». В Рос­сии тоже есть спе­циалис­ты, готовые к соз­данию боль­шого кван­тового компь­юте­ра. В МГУ готовят магис­тров по прог­рамме «Кван­товые вычис­ления», есть прог­раммы по кван­товой крип­тогра­фии и свя­зи, по кван­товым опти­чес­ким тех­нологи­ям. В МФТИ чита­ют лек­ции по кван­товой теории информа­ции, в дру­гих уни­вер­ситетах есть похожие кур­сы. Причем здесь криптография? Кван­товый компь­ютер раци­ональ­но исполь­зовать для решения очень неболь­шого клас­са задач. Это модели­рова­ние кван­товых сис­тем. Нап­ример, в химии это рас­четы химичес­ких реак­ций или рас­четы прос­транс­твен­ной струк­туры молекул при соз­дании новых матери­алов или лекарств. Это задачи опти­миза­ции, нап­ример в рас­четах слож­ной логис­тики (типа задачи ком­миво­яже­ра). Это крип­тоана­лиз сущес­тву­ющих шиф­ров. Имен­но пуб­ликация алго­рит­ма Шора (Shor) в 1994 году, исполь­зующе­го быс­трое кван­товое пре­обра­зова­ние Фурье для фак­ториза­ции боль­ших чисел, подог­рела инте­рес к кван­товому компь­юте­ру, выз­вала бум иссле­дова­ний в этой области и нап­равила на их раз­витие огромные ресур­сы. Есть аме­рикан­ская орга­низа­ция ASC X9, где раз­рабаты­вают гло­баль­ные финан­совые стан­дарты, в том чис­ле в области крип­тогра­фичес­кой защиты финан­совых дан­ных. Чле­нами этой орга­низа­ции явля­ются Bank of America, Citigroup, JPMorgan Chase, Федераль­ная резер­вная сис­тема, пла­теж­ная сис­тема VISA и Агентство наци­ональ­ной безопас­ности США. Фир­ма веников не вяжет, как говорят в народе. И вот в янва­ре 2018 года эта струк­тура оза­боти­лась рис­ками для финан­совых орга­низа­ций от кван­тового компь­юте­ра и в начале 2019 года выпус­тила информа­цион­ный отчет ASC X9 IR 01—2019. Отчет при­водит такую логику: если пред­положить, что к 2028 году ожи­дает­ся появ­ление кван­тового компь­юте­ра, спо­соб­ного взло­мать защиту, нап­ример, плас­тиковых карт, рас­счи­тан­ных на пять лет исполь­зования, то при­мене­ние клас­сичес­кой крип­тогра­фии дол­жно быть прек­ращено и защита переве­дена на кван­тово устой­чивую крип­тогра­фию как минимум за пять лет до потен­циаль­ной ата­ки. Если учесть вре­мя на переход от клас­сики к пост­кван­товой крип­тогра­фии, то переход дол­жен быть начат уже сей­час. С ого­вор­ками и без окон­чатель­ных выводов, в информа­цион­ном отче­те оце­нива­ется еже­год­ный при­рост чис­ла кубитов в 35%. Не закон Мура, но все же. Такими тем­пами тысяче­кубит­ный кван­товый компь­ютер может быть сде­лан через семь‑восемь лет. Но на самом деле для обос­нован­ного прог­ноза пока очень мало дан­ных. При­меча­тель­но, что в АНБ изме­нили рекомен­дации по шиф­ронабо­рам для защиты информа­ции. Из так называ­емо­го Suite B (сей­час это CNSA Suite) исчезла Curve P-256 для ECDH и ECDSA, хотя модули 3072 bit для RSA оста­лись. Ал­горит­мы NSA Suite B в зависи­мос­ти от крип­тостой­кос­ти и уров­ня сек­ретнос­ти в преж­них пуб­ликаци­яхА ведь всег­да счи­талось, что по крип­тостой­кос­ти P-256 и RSA-3072 рав­ны и соот­ветс­тву­ют стой­кос­ти сим­метрич­ного алго­рит­ма AES-128. Срав­нитель­ная стой­кость крип­тоал­горит­мов в преж­них пуб­ликаци­ях NISTНо AES-128 хотя бы для SECRET в обновлен­ном Suite B тоже нет, толь­ко AES-256 для TOP SECRET. В FAQ АНБ и Цен­траль­ной служ­бы безопас­ности (CSS) Минобо­роны США по CNSA Suite и кван­товым вычис­лени­ям MFQ-U-OO-815099-15 чет­ко разъ­ясне­но, что в наци­ональ­ных сис­темах безопас­ности (NSS) сле­дующие алго­рит­мы, ранее одоб­ренные для SECRET, не дол­жны исполь­зовать­ся: ECDH and ECDSA with NIST P-256; SHA-256; AES-128; RSA with 2048-bit keys; Diffie-Hellman with 2048-bit keys. Та­ким обра­зом, CNSA Suite сей­час вклю­чает в себя сле­дующие алго­рит­мы (отдель­но под­чер­кну­то, что до момен­та, ког­да будут раз­работа­ны кван­тово устой­чивые алго­рит­мы). Ре­комен­дован­ные NSA алго­рит­мыЕс­ли это свя­зать с опти­мис­тичны­ми прог­нозами о раз­работ­ке кван­товых компь­юте­ров, то мож­но пос­тро­ить прав­доподоб­ную вер­сию. Так, в 2017 году иссле­дова­тели из Microsoft Research опуб­ликова­ли статью, в которой дали сле­дующую оцен­ку: для вычис­ления дис­крет­ного логариф­ма на стан­дар­тной эллипти­чес­кой кри­вой P-256 над конеч­ным полем дос­таточ­но 2330 кубитов, в то вре­мя как для фак­ториза­ции RSA с модулем 3072 необ­ходимо 6146 кубитов, то есть поч­ти в три раза боль­ше. По­луча­ется, что для кван­товых вычис­лений P-256 и RSA-3072 по крип­тогра­фичес­кой стой­кос­ти сов­сем не рав­ны. В АНБ, веро­ятно, мог­ли получить ана­логич­ные дан­ные ранее, при этом мы не можем исклю­чить сущес­тво­вание более глу­бокой опти­миза­ции алго­рит­ма Шора для эллипти­чес­ких кри­вых. Ес­ли в течение десяти лет будет пос­тро­ен кван­товый компь­ютер с 2300 кубита­ми, он, пред­положи­тель­но, смо­жет с помощью алго­рит­ма Шора взло­мать корот­кие клю­чи ECC, начиная с 256-битовых клю­чей, а с помощью алго­рит­ма Гро­вера (Grover), реша­юще­го задачу перебо­ра, осла­бить при­мер­но в два раза сим­метрич­ные клю­чи AES. То есть крип­тостой­кость AES-128 умень­шит­ся до 264 опе­раций, что в обоз­римом будущем может ока­зать­ся неп­рием­лемым, крип­тостой­кость же AES-256, сни­зив­шись до 2128 опе­раций, оста­нет­ся дос­таточ­ной, пос­коль­ку сегод­ня счи­тает­ся, что выпол­нение 2128 опе­раций недос­тижимо. Вот любопыт­ный при­мер того, как идет работа над совер­шенс­тво­вани­ем кван­товых алго­рит­мов. В кон­це 2015 года выш­ла статья «Оцен­ка кван­товых ресур­сов для при­мене­ния алго­рит­ма Гро­вера к AES», и рас­четы авто­ров показы­вали, что для взло­ма AES-128 необ­ходимо 2953 кубита (вто­рой стол­бец таб­лицы ниже). А в 2019-м иссле­дова­тели из сол­нечной Фло­риды опти­мизи­рова­ли кван­товый алго­ритм и рас­счи­тали, что для взло­ма AES-128 необ­ходимо лишь 865 кубитов (тре­тий стол­бец таб­лицы). Пред­став­ляет­ся, одна­ко, что, даже ког­да будет тысяче­кубит­ный кван­товый компь­ютер, необ­ходимое для ата­ки огромное количес­тво вычис­лений ока­жет­ся пока прак­тичес­ки неподъ­емным. И понят­но, почему АНБ оста­вило RSA-3072: такой дли­ны ключ пока так­же будет стой­ким. Ил­люс­тра­ция воз­можнос­тей опти­миза­ции