[Перевод] Эпохальное доказательство в информатике стало причиной доказательств в физике и математике
В 1935-м Альберт Эйнштейн, работая с Борисом Подольским и Натаном Розеном, благодаря свежим открытиям в квантовой физике обнаружил такую возможность: две частицы могут оказаться в запутанном состоянии — или взаимосвязаны — даже на огромном расстоянии друг от друга.
На следующий год Алан Тьюринг сформулировал первую общую теорию информатики и доказал, что существует проблема, которую компьютеры никогда не смогут решить.
Обе эти идеи произвели революцию в своих областях науки. На первый взгляд, между ними нет никакой связи. Но теперь эпохальное доказательство объединило их при решении целого ряда открытых проблем в информатике, физике и математике.
Согласно новому доказательству, квантовые компьютеры, которые вычисляют с помощью запутанных квантовых битов (кубитов), а не обычных единиц и нулей, теоретически могут использоваться для проверки ответов на невероятный широкий ряд нерешённых вопросов. Взаимосвязь между запутанностью и вычислениями оказало на многих исследователей эффект разорвавшейся бомбы.
«Это было абсолютной неожиданностью», — говорит Мигель Наваскес, изучающий квантовую физику в Институте квантовой оптики и квантовой информации в Вене.
Авторы доказательства очертили границы подхода к проверке решений вычислительных задач. Он требует использования квантовой запутанности. Установив границы, исследователи практически в качестве побочного эффекта решили две другие задачи: проблему Цирельсона в физике (как математически смоделировать квантовую запутанность) и связанную с ней математическую проблему Конна (гипотеза о вложении).
Это запустило цепочку решений различных проблем, словно падающие домино.
«Все идеи пришли одновременно. Замечательно, что эти темы были снова подняты таким неожиданным образом», — говорит Генри Юэн из Университета Торонто, входящий в коллектив авторов вместе с Женьфень Дзи из Сиднейского технологического университета, Анандом Натараджаном и Томасом Видиком из Калифорнийского технологического института, а также Джоном Райтом из Техасского университета (Остин). Все пятеро исследователей являются специалистами в информатике.
Юэн, Видик, Джи, Натараджан и Райт.
Нерешаемые задачи
Тьюринг определил основные рамки осмысления компьютерных вычислений ещё до того, как появились компьютеры. Он почти на одном дыхании продемонстрировал, что существуют определённые проблемы, с которыми компьютеры, вероятно, не справятся. Это связано с тем, может ли остановиться выполнение программы.
Обычно компьютерные программы получают на вход информацию и выдают результат. Но иногда они застревают в бесконечном цикле и работают вечно. Если это происходит у вас дома, то остаётся сделать только одно.
Остановить программу вручную. Просто убить её.
Тьюринг доказал, что не существует универсального алгоритма, способного определить, что программа остановится или будет работать бесконечно. Чтобы это выяснить, программу нужно запустить.
Вышеперечисленные учёные совместно написали доказательство проверки ответов на вычислительные задачи, тем самым решив главные проблемы в математике и квантовой физике.
«Допустим, вы прождали миллион лет в ожидании остановки программы. Нужно ли прождать ещё два миллиона лет? Это невозможно понять», — говорит Уильям Слофстра, математик из Университета Ватерлоо.
С технической точки зрения Тьюринг доказал, что задача с остановкой программы не может быть решена. На это не способны даже самые мощные компьютеры, какие только можно представить.
После Тьюринга специалисты по информатике начали классифицировать другие задачи по их сложности. Более сложные задачи требуют для своего решения больше вычислительных ресурсов: больше процессорного времени, больше памяти. Это называют исследованием вычислительной сложности.
В целом, каждая задача ставит перед нами два главных вопроса: «Насколько трудно её решить?» и «Насколько трудно проверить корректность решения?».
Допросить, чтобы проверить
Если задачи относительно просты, вы можете проверить решение самостоятельно. Но по мере усложнения задачи даже проверка решения может быть очень трудным делом. Однако в 1985-м учёные поняли, что можно выработать уверенность в корректности ответа, даже если не получается проверить его самостоятельно.
Этот метод использует логику полицейского допроса.
Если подозреваемый рассказывает какие-то подробности, возможно, вы не сможете все их проверить. Но задавая верные вопросы, вы сможете подловить человека на лжи или придти к уверенности, что история правдивая.
С точки зрения информатики два участника допроса — это мощный компьютер, который предлагает решение задачи (доказывающий) и менее мощный компьютер (проверяющий), который хочет задать доказывающему вопросы, чтобы определить корректность решения.
Рассмотрим простой пример. Допустим, что вы не различаете цвета, и кто-то (доказывающий) утверждает, что лежащие перед вами две бусины имеют разный цвет. Вы не можете это проверить, но с помощью умного допроса вы сможете определить, правда ли это.
Спрячьте бусины за спину и перемешайте. Затем попросите доказывающего сказать, какой цвет у каждой из них. Если цвета и правда различаются, то доказывающий каждый раз будет давать верный ответ. Если же бусины на самом деле одного цвета, то есть выглядят идентично, то доказывающий в половине случаев будет угадывать неверно.
«Если вы будете давать верный ответ гораздо чаще, чем в половине случаев, то наверняка бусины разных цветов», — утверждает Видик.
Задавая вопросы доказывающему, вы можете проверять решения более широкого спектра задач, чем доступно вашей самостоятельной проверке.
В 1988-м учёные рассмотрели ситуацию, когда решение одной задачи предлагают два доказывающих. Если подозреваемых двое, то ещё легче раскрыть преступление, то есть проверить решение, потом что вы можете заставить подозреваемых играть друг против друга.
«Это даёт проверяющему больше инструментов. Вы допрашиваете, задаёте соответствующие вопросы, перекрёстно проверяете ответы», — говорит Видик. Если подозреваемые говорят правду, их ответы чаще всего будут соответствовать друг другу. Если они лгут, ответы будут чаще противоречить.
Исследователи показали, что раздельно допрашивая двух доказывающих, вы можете быстро проверить корректность их решений применительно к ещё более широкому спектру задач, чем если бы вы допрашивали только одного доказывающего.
Вычислительная сложность на первый взгляд выглядит совершенно теоретической темой. Но она тесно связана с практикой. Ресурсы, необходимые компьютерам для решения и проверки задач — память и время, — более чем материальны. Поэтому новые открытия в физике способны изменить вычислительную сложность.
«Если взять другой раздел физики, например, квантовую физику, то там уже совсем иная теория сложности», — говорит Натараджан.
Новое доказательство — это результат противостояния между учеными-информатиками XXI века и одной из самых странных идей физики XX века — квантовой запутанностью.
Проблема Конна (гипотеза о вложении)
Если две частицы запутываются, то они не могут влиять друг на друга: между ними нет причинно-следственной связи. Эйнштейн и его соавторы развили эту идею в научной работе 1935 года. Позднее физики и математики пытались создать математическое описание квантовой запутанности.
Результаты получились несколько сумбурными. Учёные пришли к двум разным математическим моделям, и не было понятно, эквивалентны ли они друг другу.
В конечном итоге это привело к возникновению математической проблемы Конна — гипотезы о вложении. В свою очередь, она стала лазейкой, которой воспользовались пять вышеперечисленных учёных при при разработке своего доказательства.
В первом варианте моделирования квантовой запутанности частицы считались пространственно изолированными друг от друга. Например, одна на Земле, вторая на Марсе. Именно расстояние мешает возникновению причинно-следственной связи. Это называется моделью с тензорным произведением.
Но в некоторых ситуациях не совсем очевидно, когда две частицы теряют причинно-следственную связь друг с другом. Поэтому математики придумали второй, более общий вариант описания причинно-следственной независимости.
Если порядок выполнения двух операций не влияет на результат, то операции являются «коммутирующими»: 3×2 — это то же самое, что 2×3. Во второй модели частицы запутываются, когда их свойства коррелируют, однако порядок выполнения вами измерений не играет роли: вы измеряете частицу А, чтобы предсказать импульс частицы Б, и наоборот. Таким образом, вы получаете один и тот же результат. Это называется модель квантовой запутанности с коммутирующим оператором.
В обоих описаниях квантовой запутанности используются массивы чисел, состоящие из строк и столбцов — то есть матрицы. В модели с тензорным произведением используются матрицы с конечным количество строк и столбцов. А в модели с коммутирующим оператором используется более общее решение, при котором функции выступают в роли матриц с бесконечным количеством строк и столбцов.
Со временем математики начали изучать эти матрицы сами по себе, как интересные объекты исследования, безо всякой связи с физическим миром. В 1976-м математик Алан Конн выдвинул гипотезу, что возможно аппроксимировать многочисленные матрицы с бесконечной размерностью в матрицы с конечной размерностью. Это одно из следствий гипотезы о вложении Конна.
В следующем десятилетии физик Борис Цирельсон сформулировал версию этой проблемы. Он выдвинул гипотезу, что модели с тензорным умножением и коммутирующим оператором примерно эквивалентны. Вполне логично, поскольку теоретически это два разных способа описания одного и того же физического феномена. В последующей работе было показано, что благодаря связи между матрицами и использующими их физическими моделями гипотеза Конна и проблема Цирельсона взаимосвязаны: если решишь одну, то тем самым решишь и вторую.
И решение обеих проблем пришло со стороны.
Физика для телешоу
В 1960-х физик Джон Белл создал тест для определения, является ли квантовая запутанность реальным физическим феноменом, а не теоретическим умозаключением. Тест подразумевал проведение своеобразной игры, в результате которой можно было понять, задействуется ли что ещё кроме обычной неквантовой физики.
Позднее специалисты по информатике поняли, что этот тест на квантовую запутанность можно использовать и как инструмент для проверки решений очень сложных проблем.
Но сначала давайте разберёмся с игрой. У нас есть два игрока, Таня и Ваня, а также решётка 3×3. Судья назначает Тане ряд и просит вписать в каждую ячейку 0 или 1, чтобы сумма чисел была нечётной. Ване назначают столбец и просят заполнить его так, чтобы сумма была чётной. Игроки побеждают, если ставят на пересечении строки и столбца одинаковое число. Общаться им нельзя.
В обычных условиях игроки могут побеждать не более чем в 89% случаев. Но в квантовых условиях результат можно улучшить.
Допустим, Таня и Ваня разделили пару запутанных частиц. Они проводят измерения каждый со своей частицей и используют результаты, чтобы сообщать, какие числа записывают в ячейки. Поскольку частицы запутаны, результаты измерений будут коррелировать, а значит и ответы — Таня и Ваня будут выигрывать в 100% случаев.
Так что если вы видите, что два игрока выигрывают аномально часто, то можете предположить, что они используют что-то ещё, помимо классической физики. Такие эксперименты называют «нелокальными» играми (nonlocal games) и проводятся в физических лабораториях.
«Учёные годами занимаются этими экспериментами и показали, что квантовая запутанность действительно существует», — говорит Юэн.
Вы можете спросить, насколько часто игроки могут выигрывать в нелокальной игре, если будут играть наиболее эффективно? Например, в пасьянсе можно вычислить вероятность выигрыша при идеальной игре.
Однако в 2016-м Уильям Слофстра доказал, что не существует универсального алгоритма вычисления минимальной вероятности выигрыша в нелокальных играх. Исследователи задались вопросом:, а можно ли хотя бы прикинуть максимальную вероятность выигрыша?
Специалисты по информатике нашли ответ с помощью двух моделей квантовой запутанности. Минимальное значение («пол») вычисляется с помощью алгоритма на основе модели с тензорным умножением, а максимальное значение («потолок») — с помощью алгоритма на основе модели с коммутирующим оператором.
Чем дольше работают алгоритмы, тем точнее результаты их работы. Если гипотеза Цирельсона верна и две модели действительно эквивалентны, то пол и потолок должны сближаться, стремясь к одному значению приблизительной максимальной вероятности выигрыша.
А если гипотеза Цирельсона ошибочна и две модели не эквивалентны, то «потолок и пол никогда не соединятся». Не будет способа вычислить даже приблизительной вероятности выигрыша в нелокальных играх.
В своей новой работе пятеро учёных использовали вопрос корректности проблемы Цирельсона для поиска ответа на другой вопрос: можно ли проверить решение для вычислительной задачи?
Запутанная помощь
В начале 2000-х в информатике возник вопрос: как меняется диапазон задач, доступных вам для проверки, если вы допрашиваете двух доказывающих, которые используют запутанные частицы?
Большинство учёных считали, что квантовая запутанность мешает проверке. Ведь двоим подозреваемым будет проще говорить согласованную ложь, если у них есть возможность координировать свои ответы.
Но в последние несколько лет учёные выяснили, что это не так: если допрашивать доказывающих, которые используют запутанные частицы, то вы сможете проверить гораздо больше задач.
«Квантовая запутанность — это способ создания корреляций, которые, как вам кажется, могут помочь им соврать или обмануть» — говорит Видик. «Но на самом деле вы можете обратить это себе на пользу».
Чтобы понять, как это сделать, необходимо сначала осмыслить почти невообразимое количество задач, решения которых вы можете проверить с помощью этой интерактивной процедуры.
Представим себе граф — набор точек (вершин), соединённых линиями (рёбрами). Можно ли раскрасить вершины с помощью трёх цветов так, чтобы не было ни одной пары вершин, соединённых одним ребром и покрашенных в один цвет? Если удастся, то этот граф можно назвать «трёхцветным».
Допустим, у вас есть два доказывающих с запутанными частицами, и очень большой граф. Доказывающие утверждают, что его можно раскрасить в три цвета. Как вы может это проверить?
В случае с очень большими графами невозможно проверить это напрямую. Вместо этого можно попросить каждого из доказывающих назвать вам цвет одной из двух соединённых вершин. Если они каждый раз будут называть разные цвета, то вы будете уверены, что этот граф действительно трёхцветный.
Но граф настолько большой, что в нём больше вершин и рёбер, чем атомов во вселенной, то описанная стратегия не сработает. Даже задать конкретный вопрос («Назови цвет вершины XYZ») будет сложнее, чем вы можете себе представить: объём данных, необходимых для маркировки конкретной вершины, превышает доступную вам рабочую память.
Но запутанность позволяет доказывающим самим придумывать вопросы.
«Проверяющий не должен вычислять вопросы. Он заставляет делать это для него доказывающих», — говорит Райт.
Проверяющий хочет, чтобы доказывающие сообщали цвета соединённых вершин. Если вершины не соединены, то ответы на вопросы ничего нам не скажут о том, является ли граф трёхцветным. Иными словами, проверяющий хочет, чтобы доказывающие задавали соответствующие вопросы: один спрашивает о вершине ABC, второй о вершине XYZ. Они надеются, что вершины соединены друг с другом, даже если ни один из них не знает, о какой вершине думает другой. Так же, как Таня и Ваня надеются, что они вводят одно и то же число в один и тот же квадрат, хотя оба они не знают, о какой строке или каком столбце спрашивали другого игрока.
Если бы двое доказывающих задавали эти вопросы исключительно самостоятельно, то мы не могли бы заставить их выбрать соединённые, или коррелирующие вершины таким образом, чтобы проверяющий смог проверить ответы. Но именно такую корреляцию обеспечивает квантовая запутанность.
«Мы хотим с помощью запутанности переложить всю работу на доказывающих. Мы заставим их самостоятельно выбирать вопросы», — говорит Видик.
В конце этой процедуры каждый доказывающий называет цвет. Проверяющий сравнивает ответы. Если граф действительно трёхцветный, то доказывающие никогда не назовут один и тот же цвет.
«В случае трёхцветности доказывающие смогут убедить вас, что это так», — говорит Юэн.
Получается, что процедура проверки — это ещё один пример нелокальной игры. Доказывающие «выигрывают», если им удаётся убедить вас в корректности их решения.
В 2012-м Видик и Цуёши Ито доказали, что можно играть с запутанными доказывающими в самые разные нелокальные игры, проверяя решения как минимум для такого же количества задач, какое вы проверили бы при допросе двух обычных компьютеров. То есть использование запутанных доказывающих не мешает проверке. А в прошлом году Натараджан и Райт доказали, что взаимодействие с запутанными доказывающими на самом деле даже расширяет спектр доступных для проверки задач.
Однако учёные-информатики не знали, как много задач можно проверить таким образом. До недавнего времени.
Цепочка последствий
В новой научной работе пятеро учёных доказали, что допрос запутанных доказывающих позволяет проверять решения для нерешаемых задач, включая проблему остановки программы.
«Способность проверять модели такого типа поражает воображение», — говорит Юэн.
Но ведь проблему остановки решить нельзя. Этот факт стал ключевым толчком, который привёл к финальному доказательству.
Допустим, вы дали программу двум запутанным доказывающим и просите их сказать вам, остановится ли она. Вы приготовились проверить их ответы с помощью нелокальной игры: доказывающие отвечают и «побеждают» за счёт координации своих ответов.
Если программа действительно останавливается, то доказывающие должны выигрывать в 100% случаев. Как и в примере с графом, который на самом деле можно раскрасить в три цвета, запутанные доказывающие никогда не назовут одинаковый цвет для двух соединённых вершин. Если программа не останавливается, то доказывающие выигрывают случайно, в 50% случаев.
Это означает, что если кто-то попросит вас определить приблизительную максимальную вероятность выигрыша в конкретной нелокальной игре, вам сначала нужно решить задачу остановки. А это невозможно. То есть задачу вычисления примерной максимальной вероятности для нелокальной игры решить нельзя, как и задачу остановки.
Это, в свою очередь, означает, что ответом на проблему Цирельсона будет «нет»: две модели квантовой запутанности не эквивалентны. В противном случае вы могли бы соединить пол и потолок для вычисления приблизительной максимальной вероятности выигрыша.
«Такой алгоритм невозможен, поэтому две модели должны быть разными», — говорит Давид Перез-Гарсия из Университета Комплутенсе де Мадрид.
В новой работе доказано, что класс задач, которые можно проверить с помощью запутанных квантовых доказывающих — класс MIP* — полностью эквивалентен классу задач, которые не сложнее задачи остановки, то есть класса RE. В статье явно утверждается: «MIP* = RE».
В ходе доказательства эквивалентности двух классов сложности специалисты по информатике доказали, что проблема Цирельсона имеет отрицательный ответ. А это означает, что такой же ответ имеет и гипотеза Конна.
Для исследователей, работающих в этой области, стало ошеломляющей новостью, что такие большие проблемы решены с помощью доказательства в информатике, которое, на первый взгляд, не имеет никакого отношения.
«Если бы увидел статью, в которой сказано, что MIP* = RE, то я никак не связал бы это со своей работой», — говорит Наваскез, один из авторов работы, в которой была проведена связь между проблемой Цирельсона и гипотезой Конна. «Для меня это было полной неожиданностью».
Квантовые физики и математики только начинают переваривать эту новость. До этой работы математики задавались вопросом, можно ли избежать аппроксимации матриц бесконечной размерности, заменив их матрицами конечной размерности. Теперь известно, что нет.
«Их результат говорит о том, что это невозможно», — говорит Слофстра.
Сами учёные-информатики не пытались ответить на гипотезу Конна, а следовательно, они находятся не в лучшем положении, чтобы объяснить последствия одной из проблем, которую они в итоге решили.
«Я не математик. Я плохо понимаю оригинальную формулировку гипотезы встраивания Конна», — говорит Натараджан.
Он и его соавторы надеются, что математики переведут полученный ими результат на язык своей науки. В статье, в которой сообщалось о доказательстве, Видик написал: «Я не сомневаюсь, что в конечном итоге для формулирования чисто математических последствий теория сложности не понадобится».
Однако, по мере того, как другие исследователи работают с доказательством, породившее его направление исследований завершается. На протяжении более трех десятилетий ученые, занимающиеся информатикой, пытаются выяснить, насколько далеко заведёт их интерактивная проверка. Теперь у них есть ответ в виде длинной работы с простым названием и отголосками работ Тьюринга.
«Существует длинная последовательность работ, в которых авторы задаются вопросом, насколько мощной может быть процедура проверки с двумя запутанными квантовыми доказывающими», — говорит Натараджан. «Теперь мы знаем её возможности. Эта история подошла к концу».
