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

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

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

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

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

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

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

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

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

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

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

Долгий путь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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