Представьте себе: к вам приходит человек и говорит, что у него есть прорицатель, и что этот прорицатель может раскрыть непостижимые тайны вселенной. Вы заинтригованы, но вряд ли ему поверите. Вы обязательно захотите убедиться в том, что прорицатель говорит правду, и для этого вам нужен будет какой-то способ или метод.
В этом суть одной из главных проблем компьютерных наук. Некоторые задачи слишком трудно решить в разумные сроки. Но их решение легко проверить. По этой причине ученые, работающие в области теории вычислительных систем, хотят знать: насколько сложной может быть задача, имеющая решение, которое поддается проверке?
Оказывается, ответ таков: она может быть невероятно сложной.
В апреле два ученых-программиста опубликовали научную работу, где многократно увеличили количество задач, которые трудно решить, но легко проверить. Они описали метод, позволяющий проверить решение задач почти невероятной сложности. «Это похоже на безумие», — сказал специалист по вычислительной технике Томас Видик (Thomas Vidick), работающий в Калифорнийском технологическом институте, и не участвовавший в этой новой работе.
Исследование касается квантовых компьютеров, которые выполняют вычисления по противоречащим здравому смыслу правилам квантовой механики. Квантовые компьютеры только начинают появляться, но в будущем они могут произвести переворот в вычислениях и расчетах.
По сути дела, поведенное новое научное исследование дает нам возможность влиять на описанного в начале статьи прорицателя. Даже если он пообещает нам дать ответы на те задачи, которые мы сами решить не в состоянии,- так вот, даже в этой вроде бы безнадежной ситуации у нас все равно будет способ проверить прорицателя и убедиться, что он говорит правду (или обманывает).
ДО СМЕРТИ ВСЕЛЕННОЙ
Когда задачу трудно решить, но легко проверить, поиск решения занимает много времени, а вот проверка правильности приведенного решения — нет.
Вот пример. Представьте себе, что вам дают рисунок. Это совокупность точек (вершин), которые соединены линиями (гранями). Вас спрашивают, можно ли закрасить эти точки фигуры всего тремя цветами таким образом, чтобы соединенные линиями точки были разных цветов.
Такую «трехцветную» задачу трудно решить. В целом количество времени, необходимое для составления трехцветной фигуры (или для определения того, что она не может существовать), растет в геометрической прогрессии по мере увеличения размеров фигуры. Скажем, если у фигуры 20 точек соединения линий, то решение задачи занимает 3 в двадцатой степени наносекунд, то есть несколько секунд в переводе на привычные нам единицы времени. А вот если фигура будет с 60 точками, то на поиск решения потребуется в 100 раз больше времени, чем составляет предполагаемый нами возраст вселенной.
Но давайте представим себе: кто-то заявляет, что составил такую трехцветную фигуру. Чтобы проверить правдивость его утверждения, нам понадобится немного времени. Мы просто начнем проверять точки соединения линий одну за другой. По мере увеличения фигуры время проверки тоже будет медленно увеличиваться. Это так называемое полиномиальное время. В результате получается, что времени на проверку трехцветной фигуры с 60 вершинами у компьютера уходит не намного больше, чем на проверку фигуры с 20 точками соединения линий.
«Проверить, что эта схема работает, довольно легко — при условии, что это настоящая трехцветная фигура», — говорит физик Джон Райт (John Wright) из Массачусетского технологического института, написавший новую работу совместно с Анандом Натараджаном (Anand Natarajan) из Калифорнийского технологического института.
В 1970-е годы программисты выделили класс задач, которые легко проверить, хотя иногда трудно решить. Они дали этому классу название НПВ — недетерминированное полиномиальное время. С тех пор эти задачи очень интенсивно изучают многие специалисты в области компьютерных наук. В частности, ученым хочется узнать, как меняется этот класс задач, когда у проверяющего появляются новые способы проверить правильность решения.
ПРАВИЛЬНЫЕ ВОПРОСЫ
До появления работы Натараджана и Райта в деле проверки правильности решения были совершены два важных открытия. Они сильно увеличили нашу способность проверять сверхтрудные задачи.
Для понимания сути первого прорывного открытия представьте себе, что вы дальтоник. Перед вами на стол кладут два кубика, а вас спрашивают, одинакового они цвета или разного. Для вас эта задача невыполнима. Более того, вы не в состоянии проверить решение другого человека.
Но вам разрешено расспросить этого человека, которого мы будем называть доказывающим. Допустим, доказывающий говорит вам, что пара кубиков разного цвета. Первый кубик мы обозначим буквой «А», а второй буквой «Б». Вы берете кубики, прячете их за спиной и несколько раз перекладываете из руки в руку. Затем вы показываете кубики и просите доказывающего показать кубик А.
Если кубики разного цвета, все предельно просто. Доказывающему известно, что кубик А, скажем, красного цвета, и он каждый раз будет верно его указывать.
Но если кубики одного цвета, то есть доказывающий сказал неправду, говоря, что цвет у них разный, он может только догадываться, где какой кубик. Из-за этого он будет правильно указывать кубик А только в 50 процентах случаев. Значит, многократно спрашивая доказывающего о решении, вы сможете проверить его правильность.
«Проверяющий может задавать доказывающему вопросы, — сказал Райт. — И может быть, в конце разговора уверенность проверяющего усилится».
В 1985 году трио программистов доказало, что такие интерактивные доказывания можно использовать для проверки решений задач, которые сложнее класса задач НПВ. В результате их работы на свет появился новый класс задач под названием ИПВ — интерактивное полиномиальное время. Тот метод, что используется для проверки цвета двух кубиков, можно применять для проверки решений более сложных задач и вопросов.
Второй важный шаг был сделан в том же самом десятилетии. Здесь все следует логике полицейского расследования. Если у вас есть два подозреваемых, которые, по вашему мнению, совершили преступление, вы не будете допрашивать их вместе. Вы допросите их в разных комнатах, а потом сопоставите данные ими ответы. Допрашивая этих людей по отдельности, вы сможете узнать больше правды, чем в том случае, если у вас будет лишь один подозреваемый.
«Два подозреваемых не смогут создать некую правдоподобную и согласованную версию, потому что они просто не будут знать ответы друг друга», — сказал Райт.
В 1988 году группа ученых-компьютерщиков из четырех человек доказала, что если двум компьютерам предложить раздельно решить одну и ту же задачу, а потом раздельно допросить об ответах, то можно проверить даже более обширный класс задач, чем ИПВ. Этот класс получил название ИДМД — интерактивное доказательство со многими доказывающими.
Используя такой подход, можно, например, проверить «трехцветные» задачи по последовательности фигур, которые увеличиваются в размере гораздо быстрее, чем фигуры в недетерминированном полиномиальном времени. В недетерминированном полиномиальном времени размер фигур увеличивается линейно — количество точек соединения линий может возрастать от 1 до 2, потом до 3, потом до 4 и так далее. Таким образом, в размере фигуры никогда не будет огромных диспропорций с количеством времени, необходимого для проверки ее трехцветности. Но если мы ведем речь об интерактивном доказательстве со многими доказывающими, то здесь количество точек в фигуре увеличивается в геометрической прогрессии.
В результате эти фигуры становятся слишком большими, и не вмещаются в память проверяющего компьютера, из-за чего он не может проверить их трехцветность, пробегая по списку соединительных точек. Но проверить трехцветность все-таки возможно, задавая двум доказывающим отдельные, но связанные между собой вопросы.
В классе задач ИДМД у проверяющего достаточно памяти для запуска программы, позволяющей определить, связаны ли две точки в фигуре линией. Проверяющий может затем попросить каждого доказывающего назвать цвет одной из двух соединенных линией точек, после чего легко может сопоставить ответы доказывающих, дабы убедиться, что трехцветная фигура верна.
Повышение уровня задач, которые трудно решить, но легко проверить, от НПВ до ИПВ, а потом до ИДМД, можно было обеспечить за счет классических компьютеров. Квантовые компьютеры работают иначе. На протяжении десятилетий было непонятно, как они меняют картину, то есть, труднее или легче с их помощью проверить решение.
Новая работа Натараджана и Райта дает ответ на этот вопрос.
КВАНТОВЫЙ ОБМАН
Квантовые компьютеры выполняют вычисления, манипулируя квантовыми битами (кубиты). У них есть странное свойство, суть которого в том, что они могут спутываться друг с другом. Когда два кубита или даже крупные системы кубитов спутываются друг с другом, это означает, что их физические свойства определенным образом их разыгрывают.
В своей новой работе Натараджан и Райт рассматривают сценарий с двумя отдельными квантовыми компьютерами, у которых есть общие спутанные кубиты.
Казалось бы, такого рода схема работает против проверки. Убедительность интерактивного доказательства со многими доказывающими объясняется как раз тем обстоятельством, что вы можете допросить двух доказывающих раздельно, а потом сопоставить их ответы. Если эти ответы совпадают, то скорее всего, они правильные. Но если два доказывающих в спутанном состоянии, то у них больше возможностей последовательно и согласованно давать неправильные ответы.
Действительно, когда в 2003 году впервые был предложен сценарий с двумя спутанными квантовыми компьютерами, ученые предположили, что запутанность ослабит возможности по проверке. «У всех, и в том числе у меня, реакция была вполне очевидная: теперь у доказывающих будет больше сил и убедительности, — сказал Видик. — Они смогут использовать запутанность для того, чтобы согласовывать свои ответы».
Несмотря на этот первоначальный пессимизм, Видик несколько лет пытался доказать обратное. В 2012 году он вместе с Цуеси Ито (Tsuyoshi Ito) доказал, что при помощи спутанных квантовых компьютеров все-таки возможно проверить все задачи класса ИДМД.
Сейчас Натараджан и Райт доказали, что ситуация и того лучше. С запутанностью можно проверить более обширный класс задач, чем без нее. Связи между спутанными квантовыми компьютерами можно обратить на пользу проверяющего.
Чтобы понять как, вспомним порядок проверки трехцветных фигур, размер которых увеличивается в геометрической прогрессии, если используется интерактивное доказательство со многими доказывающими. У проверяющего недостаточно памяти, где можно сохранить всю фигуру, но достаточно, чтобы идентифицировать две связанные точки и спросить доказывающих, какого они цвета.
Если говорить о тех задачах, которые рассматривают Натараджан и Райт — а они относятся к классу под названием недетерминированное дважды экспоненциальное время (НДЭВ) — то в них размер фигуры увеличивается даже быстрее, чем в задаче класса ИДМД. Фигура в НДЭВ увеличивается «дважды экспоненциальными» темпами. То есть, это двойная геометрическая прогрессия. Фигура увеличивается не со скоростью 21-я, 22-я, 23-я степень, а «в степени степеней». Из-за этого фигуры увеличиваются так быстро, что проверяющий не может обнаружить отдельную пару соединенных точек.
«Чтобы отметить точку, нужно 2n бит, а это экспоненциально большее количество, чем имеется в рабочей памяти проверяющего», — говорит Натараджан.
Но Натараджан и Райт доказывают, что можно проверить трехцветную раскраску дважды экспоненциальной фигуры, не имея возможности определить, о каких точках надо спрашивать доказывающих. Дело в том, что доказывающие сами задают вопросы.
По мнению ученых, идея предложить компьютерам самим проверить собственные решения методом опроса такая же разумная, как и идея попросить подозреваемых в совершении преступления самим себя допросить. То есть, это полная глупость. Правда, Натараджан и Райт доказывают, что это не так. Причина в запутанности.
«Запутанное состояние — это общий ресурс, — говорит Райт. — Весь наш протокол нацелен на то, чтобы понять, как использовать этот общий ресурс для подготовки связанных вопросов».
Если квантовые компьютеры в спутанном состоянии, то выбор ими точек будет взаимосвязан, и они выдадут правильный набор вопросов для проверки трехцветности.
В то же время, проверяющему не нужно, чтобы два квантовых компьютера были слишком тесно взаимосвязаны, так как их ответы на эти вопросы будут согласованы (это равноценно тому, что два подозреваемых договариваются между собой о ложном алиби). Эту проблему устраняет другая странная квантовая особенность. В квантовой механике принцип неопределенности мешает нам одновременно знать положение частицы и импульс ее силы. Если вы измерите одно, то уничтожите информацию о другом. Принцип неопределенности строго ограничивает ваши знания о двух «взаимодополняющих» свойствах квантовой системы.
Натараджан и Райт воспользовались этим в своей работе. Чтобы вычислить цвет вершины, они используют два квантовых компьютера, которые выполняют измерения, дополняя друг друга. Каждый компьютер вычисляет цвет своих точек, и поступая таким образом, он уничтожает всю информацию о точках другого компьютера. Иными словами, запутанность позволяет компьютерам формулировать взаимосвязанные вопросы, но принцип неопределенности мешает им сговориться, отвечая на них.
«Надо заставить доказывающего забыть [о ложной версии событий], и это главное, что они [Натараджан и Райт] сделали в своей работе, — сказал Видик. — Они вынуждают доказывающего удалить информацию, когда тот проводит измерения».
Их работа имеет огромные и очень важные последствия. До появления этой работы предел количества знаний, которыми мы могли обладать с полной уверенностью, был существенно ниже. Если бы нам дали ответ задачи ИДМД, нам пришлось принять бы его на веру, так как иного выбора у нас нет. Но Натараджан и Райт сняли это ограничение и сделали возможной проверку ответов на гораздо большее количество вычислительных задач.
Но теперь, когда они это сделали, стало непонятно, где находится лимит проверки правильности.
«Это может зайти намного дальше, — сказал Ланс Фортнау (Lance Fortnow), занимающийся компьютерными науками в Технологическом институте Джорджии. — Они оставляют возможность для того, чтобы сделать еще один шаг».
