Главная » Хабрахабр » [Перевод] Аспирантка решила задачу подтверждения квантовых вычислений

[Перевод] Аспирантка решила задачу подтверждения квантовых вычислений

Урмила Махадев провела восемь лет в магистратуре в поисках ответа на один из наиболее базовых вопросов квантовых вычислений: откуда нам знать, что квантовый компьютер сделал хоть что-то на квантовом уровне?

Она только что решила важнейшую проблему квантовых вычислений – области изучения компьютеров, черпающих свои возможности из странных законов квантовой физики. Весной 2017 года Урмила Махадев оказалась в неплохом положении, с точки зрения большинства аспирантов. «слепые вычисления», сделал «очевидным тот факт, что она является восходящей звездой», — сказал Скот Ааронсон, специалист по информатике из Техасского университета в Остине. Вместе с более ранними её работами, новый результат Махадев, описывающий т.н.

И вот, наконец, она смогла составить «прекрасную докторскую диссертацию», — сказал Умеш Вазирани, её куратор в Беркли.
Но Махадев не закончила учиться в том году. Махадев, которой на тот момент было 28, уже седьмой год была в магистратуре в Калифорнийском университете в Беркли – гораздо дольше, чем срок, который требуется большинству студентов, чтобы потерять терпение и захотеть уже закончить обучение. Она ещё не закончила. Она даже не рассматривает этот вопрос.

А именно: если вы просите квантовый компьютер произвести для вас вычисление, откуда вам знать, следует ли он вашим инструкциям, да и вообще, делает ли что-то на квантовом уровне? Более пяти лет она работала с другой исследовательской задачей, которую Ааронсон назвал «одним из наиболее базовых вопросов, который можно задать в области квантовых вычислений».

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

Если не верить обычному компьютеру, в теории можно тщательно изучить каждый шаг его вычислений самостоятельно. Но как только квантовый компьютер сможет проводить вычисления, на которые не способен классический, откуда нам знать, что он проводит их правильно? Для начала, их работа чрезвычайно сложна: чтобы записать описание внутреннего состояния компьютера, состоящего всего из нескольких сотен квантовых битов, или кубитов, потребуется жёсткий диск размером больше наблюдаемой Вселенной. Но квантовые компьютеры по своей сути сопротивляются подобным проверкам.

Внутреннее состояние квантового компьютера обычно представляет собой суперпозицию многих не квантовых, а классических состояний (как у кота Шрёдингера, который одновременно жив и мёртв). И даже если бы у вас было место для записи этого описания, его никак нельзя было бы разобрать. Загляните внутрь квантового компьютера с 300 кубитами – и вы увидите только 300 классических бит, нолей и единиц, вежливо улыбающихся вам в ответ. Но как только вы измерите квантовое состояние, оно тут же схлопнется в одно из классических.

«Квантовый компьютер – штука мощная, но таинственная», — сказал Вазирани.

«Достаточно ли сильным будет взаимодействие между квантовым и классическим мирами, чтобы сделать такой диалог возможным?» – спросила Дорит Ахаронова, специалист по информатике из Еврейского университета в Иерусалиме. Учитывая подобные ограничения, специалисты по информатике давно уже думали о том, может ли квантовый компьютер обеспечить абсолютно надёжную гарантию, что он реально сделал то, что заявляет.

В последующие годы она пыталась использовать то один подход к ней, то другой. На втором году магистратуры Махадев захватила эта задача, и она даже не совсем понимает, почему. «У меня было много таких моментов, когда мне казалось, что я всё делаю правильно, а затем всё ломалось – либо очень быстро, либо через год», — сказала она.

Махадев продемонстрировала такой уровень неизменной решимости, который Вазирани до этого не встречал. Но она отказывалась сдаваться. «В этом смысле Урмила совершенно необыкновенная», — сказал он.

Она создала интерактивный протокол, при помощи которого пользователь, не обладающий квантовыми возможностями, тем не менее, может при помощи криптографии обуздать квантовый компьютер и направлять его, куда угодно, имея полную уверенность в том, кто квантовый компьютер подчиняется приказам. И вот, после восьми лет магистратуры, Махадев это удалось. Подход Махадев, сказал Вазирани, даёт пользователю «рычаг давления, от которого компьютер не способен избавиться».

«Совершенно поразительно», что такого результата смог в одиночку добиться аспирант, сказал Ааронсон.

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

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

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

Долгий путь

Махадев выросла в Лос-Анджелесе, в семье врачей, и обучалась в Южно-Калифорнийском университете, где переходила от одной области к другой, изначально убеждённой только в том, что она сама не хочет быть врачом. Затем она очень заинтересовалась курсом теоретической информатики, который вёл Леонард Эйдлман, один из создателей знаменитого алгоритма шифрования RSA. Она поступила в магистратуру в Беркли, в пояснительной записке указав, что её интересуют все аспекты теоретической информатики – кроме квантовых вычислений.

«Это было чем-то совершенно чуждым, о чём я имела меньше всего представления», — сказал она.

Он познакомил её с вопросом поиска протокола для подтверждения квантовых вычислений, и эта задача «по-настоящему заставила работать её изображение», — сказал Вазирани. Но, попав в Беркли, она вскоре поменяла своё мнение под влиянием доступных объяснений Вазирани.

– Мне с ними проще, чем с другими вопросами, поскольку тут сразу можно начинать думать о протоколах, разбивать их на части, и смотреть, как они работают». «Протоколы похожи на головоломки, — пояснила Махадев. Она выбрала эту задачу для своей докторской, встав на «очень долгий путь», как сказал Вазирани.

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

Иначе говоря, классический компьютер не просто не может их решить, он даже не может распознать, правильным ли будет предложенное решение. Однако специалисты по информатике считают (и недавно сделали шаг по направлению к доказательству), что многие задачи, которые мог бы решить квантовый компьютер, лишены такой особенности. В результате в 2004 году Дэниел Готтсман – физик-теоретик из Института Периметра в Ватерлоо – задал вопрос, возможно ли придумать какой-либо протокол, по которому квантовый компьютер смог бы доказать не квантовому наблюдателю, что он реально выполнил то, что заявляет.

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

Однако их подход был специально разработан для такого сценария, и задача, казалось, упёрлась в тупик, сказал Готтсман. А в 2012 году команда исследователей, куда входил и Вазирани, показала, что полностью классический проверяющий может проверить квантовые вычисления, если они проводились парой квантовых компьютеров, не общавшихся друг с другом. «Я думаю, что, вероятно, были люди, считавшие, что дальше уже не пройти».

Сначала она пыталась выдать «безусловный» результат, без предположений о том, что может и чего не может делать квантовый компьютер. Примерно в это время Махадев столкнулась с проблемой подтверждения. (Такие методы, как алгоритм RSA, использующийся для шифрования онлайн-переводов, не относятся к пост-квантовым — крупный квантовый компьютер способен взломать их, поскольку их безопасность зиждется на трудности разложения на множители больших чисел). Но, после того, как она некоторое время работала над задачей без успеха, Вазирани предложил вместо этого возможность использования «пост-квантовой» криптографии – то есть, криптографии, взлом которой, по мнению исследователей, находится за пределами возможностей даже квантовых компьютеров, хотя точно им это неизвестно.

Совместно с Полом Кристиано, специалистом по информатике из OpenAI, компании из Сан-Франциско, они разработали способ использования криптографии для того, чтобы заставить квантовый компьютер перейти в «секретное состояние» – такое состояние, описание которого известно классическому проверяющему, но не самому квантовому компьютеру. В 2016 году, работая над другой задачей, Махадев и Вазирани совершили прорыв, который в дальнейшем окажется решающим.

(В тот момент исследователи ещё не знали, как сделать подходящую ловушку – это пришло позже). Их процедура основывается на функции-«ловушке» – такой, которую легко выполнить, но тяжело обратить, если только у вас нет секретного криптографического ключа. К примеру, можно представить себе функцию, возводящую числа в квадрат – кроме числа 0, для каждого результата (например, 9) есть два соответствующих ему входных числа (3 и -3). Функция также должна обладать свойством «два в одно», что означает, что для каждого набора выходных данных есть два различных набора входных данных.

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

Измерение схлопывает состояние до одного из возможных наборов выходных данных, а входное состояние схлопывается так, чтобы соответствовать ему, поскольку они запутаны – к примеру, если мы используем функцию квадрата, то, если выходное состояние будет равно 9, тогда входное схлопнется до суперпозиции 3 и -3. Затем вы приказываете компьютеру измерить итоговое состояние и сообщить результат.

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

При помощи таких функций-ловушек она смогла создать квантовую версию «слепых» вычислений, при помощи которых пользователи систем облачных вычислений могут скрывать свои данные, чтобы компьютеры облака не могли их считывать, даже если они выполняют вычисления с ними. В 2017 году Махадев поняла, как создавать функции-ловушки, на которых основан метод с секретным состоянием, используя криптографию под названием "обучение с ошибками" (LWE). Вскоре после этого Махадев, Вазирани и Кристиано объединились с Видиком и Цвикой Бракерски (из института Вейцмана в Израиле), чтобы ещё сильнее улучшить качество этих функций, и использовать метод секретного состояния для разработки гарантированного способа, которым квантовый компьютер способен генерировать доказуемо случайные числа.

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

Но, сказала она, «я проводила время за обучением интересующим меня вещам, поэтому это времяпрепровождение нельзя назвать пустой тратой». Иногда неуверенность в способности решить эту задачу давила на неё.

Высечено на камне

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

Именно здесь и вступает в игру метод секретного состояния. Сложность будет в том, как поняла Махадев, чтобы заставить квантовый компьютер пообещать сделать какое-либо определённое измерение до того, как он узнает, о каком именно измерении его попросит проверяющий – иначе компьютеру будет очень просто обмануть его. И только потом компьютер узнаёт, какое измерение необходимо проводить. Протокол Махадев требует от квантового компьютера сначала создать секретное состояние, а затем запутать его с состоянием, которое он должен измерять.

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

– писал Видик. «Это настолько чудесная идея! – Она поражает меня каждый раз, когда Урмила её объясняет».

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

Единственный вариант, при котором квантовый компьютер может обмануть протокол – если кто-то из мира квантовых вычислений придумает, как взломать LWE, что само по себе станет примечательным достижением. В любом случае, уверенность протокола в LWE делает работу Махадев выигрышной в любом случае, писал Видик.

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

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

Ведь всего пять лет назад, сказал Видик, исследователи считали, что до тех пор, пока квантовые компьютеры не смогут решить какую-либо задачу, на которую не способны классические компьютеры, пройдёт ещё очень много лет. И, учитывая, как быстро развивается эта область, этот этап может наступить раньше, чем ожидалось. «А теперь, — сказал он, — люди считают, что это произойдет уже через год-два».

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

– Я с нетерпением жду новых результатов от Урмилы». «Мне кажется, что за ней последует множество производных идей, — сказал Ааронсон.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Введение в ptrace или инъекция кода в sshd ради веселья

Конечно, это несколько искусственная задача, так как есть множество других, более эффективных, способов достичь желаемого (и с гораздо меньшей вероятностью получить SEGV), однако, мне показалось клёвым сделать именно так. Цель, которой я задался, была весьма проста: узнать введённый в sshd ...

Дайджест свежих материалов из мира фронтенда за последнюю неделю №339 (12 — 18 ноября 2018)

Предлагаем вашему вниманию подборку с ссылками на новые материалы из области фронтенда и около него.     Медиа    |    Веб-разработка    |    CSS    |    Javascript    |    Браузеры    |    Занимательное Медиа • Подкаст «Frontend Weekend» #79 – Олег Поляков об основании CodeDojo и о том, как это стало основным местом работы• Подкаст «Пятиминутка React» ...