Претендент №1 на «научного Оскара» в 2021
Международное исследование четырех авторов из Австралии, США и Канады, поданное в январе 2020 на рецензирование, выполнено на стыке физики, информатики и математики, и его название сильно смахивает на Е = mc². Эта 165-ти страничная работа, содержащая 155 формул размером до 6 строк, называется « MIP * = RE».
Рецензировать работу такого объема будут до года. И как считают некоторые весьма авторитетные ученые, она успешно пройдет рецензирование. А после этого начнется большой бэнц. Ведь эта работа не только опровергает пару крутейших современных теорий (одну из физики, вторую из математики). Она еще и открывает новый горизонт будущей науки, которая настолько превзойдет современный уровень, что будет решать задачи, сегодня считающиеся неразрешимыми. Речь идет о расширении границ проверяемых знаний. А точнее, знаний, поддающихся компьютерной проверке.
Современная наука устанавливает горизонт доступных нам проверяемых знаний. Что за горизонтом, — не известно. А чтобы отодвинуть этот горизонт, нужны другие законы физики, описывающие нашу реальность. При ином описании реальности иными законами физики, возможно использование более сложной теории вероятностей с иными, более сложными причинно-следственными связями. И возможно, тогда удастся заглянуть за горизонт проверяемых знаний и, среди прочего, понять, как построить сильный ИИ.
Но ведь у нас уже есть иная физика с иными законами, описывающими нашу же реальность, но с другими причинно-следственными отношениями. Это квантовая теория.
И что — это реально работает и позволяет решать какие-то неразрешимые для современной науки проблемы?
Новое исследование доказывает, что да. Это работает. И еще как!
Неразрешимые проблемы
Дело в том, что в цифровом мире для любой задачи есть два ключевых вопроса.
· Насколько сложно это решить?
· Насколько сложно проверить правильность ответа?
Со сложностью решения можно бороться деньгами, привлекая больше спецов и наращивая вычислительные мощности.
А вот со вторым, увы, это работает не всегда. Т.к. при определенном уровне вычислительной сложности никакие деньги не помогут — проверка правильности ответа становится теоретически невозможной. Иными словами, мы сталкиваемся с неразрешимой проблемой. Следовательно, нам остается лишь смирить гордыню и признать — мы достигли границы проверяемых знаний.
Открытие же, о котором рассказывает этот пост, заключается в том, что
придуман метод, позволяющий проверить ответы на решение задач почти непостижимой и, даже можно сказать — эзотерической сложности.
Вот всем понятный пример такой проблемы.
Проблема остановки.
Еще Алан Тьюринг придумал задачу, которую современные компьютеры никогда не смогут решить. Это т.н. «проблема остановки» (или проблема останова).
Допустим, есть некий алгоритм, записанный в виде программы, и входные данные для нее.
Вопрос: остановится ли эта программа или зациклится и будет выполняться вечно?
Тьюринг доказал, что не существует универсального алгоритма (реализуемого машиной Тьюринга), который мог бы определить, остановится ли компьютерная программа или нет. Вы должны запустить программу, чтобы узнать это.
Но что, если вы запустили программу, и она не остановилась за год, а потом и за 10 лет, и век спустя? Все равно ответа нет. Может она через 327 лет остановится. Или через 100 тыс. лет. А может и не остановится никогда.
Т.е. согласно доказательству Тьюринга,
проблема остановки неразрешима — даже самый мощный современный компьютер не сможет ее решить ни за какое конечное время.
После Тьюринга ученые-компьютерщики начали классифицировать другие проблемы по их вычислительной сложности. И обнаружилось, что есть и другие неразрешимые на компьютерах проблемы.
Интерактивные доказательства
Когда проблемы относительно просты, вы можете проверить ответ самостоятельно. Но как быть с чрезвычайно сложными для проверки задачами?
В 1985 году придумали использовать метод, основанный на логике полицейского допроса. Если подозреваемый рассказывает чрезвычайно сложную для проверки историю, вам нет надобности искать подтверждение каждой детали. Вместо этого, просто задавая правильные вопросы, вы можете поймать своего подозреваемого на лжи или увериться, что он говорит правду.
Допустим, вы дальтоник и вам нужно определить, одинаков ли цвет двух кубиков А и Б или разный (допустим, зеленый и красный).
Сосед утверждает, что кубики разного цвета: А зеленый, а Б красный. Но как определить, не врет ли он? Не ошибается ли? Правильное ли это решение задачи?
И тогда вы используете хитрую процедуру.
· Прячете кубики за спиной и там их тасуете, запоминая при этом, в какой руке окажется в итоге кубик А (по словам соседа, зеленый) и кубик Б (якобы, красный).
· Предъявляете кубики соседу и спрашиваете: в какой руке какой кубик?
· Фиксируете ответ и повторяете снова с п.1.
Если кубики действительно разного цвета, сосед не будет ошибаться (как тут ошибешься: зеленый — он и в Африке зеленый, равно как и красный). Если же сосед дал вам неверный ответ (и на самом деле, кубики одного цвета), он будет ошибочно отгадывать вашу загадку примерно в половине случаев (как с отгадыванием орла или решки при случайном бросании монеты).
С точки зрения информатики, такую схему легко повторить. Взять мощный компьютер для решения задачи — назовем его «Решающий» (Prover). И менее мощный компьютер, который будет задавать вопросы Решающему, чтобы определить, является ли ответ Решающего правильным. Этот второй компьютер назовем «Проверяющий» (Verifier).
Подобные стратегии, получившие название «интерактивные доказательства», позволяют проверять решения задач, имеющих класс вычислительной сложности IP (Interactive polynomial time). Этот класс сложнее класса P (Polynomial time) — такие задачи легко решаются и проверяются (за полиноминальное время). Класс IP также сложнее класса NP — класс проблем, которые легко проверить, даже если некоторые из них трудно решить.
Еще более мощные интерактивные доказательства включают несколько Решающих.
Этот более сложный сценарий похож на допрос в полиции двух подозреваемых, находящихся в отдельных комнатах, которые не могут согласовать свои ответы, чтобы обмануть следователя. Такая схема проверки дает больше рычагов для Проверяющего. Если подозреваемые говорят правду, их ответы большую часть времени будут совпадать. Если же они лгут, ответы будут зачастую конфликтовать.
Такой класс сложности задач называется MIP (Multi-proven interactive proofs). Для него было доказано, что при опросе двух Решающих можно быстро проверять решения большего класса задач, чем при одном Решающем.
Т.о. получилось следующее.
· Множество задач класса сложности MIP самое большое. Оно включает в себя множество задач класса IP.
· Последний, в свою очередь, включает в себя множество задач класса NP,
· А класс NP, в свою очередь, включает в себя множество задач класса P.
Все это было бы хорошо, — но выяснилось следующее.
Класс сложности MIP исчерпывает возможности проверки правильности решений на классических компьютерах.
Проверка правильности решения неразрешимых проблем (типа проблемы остановки) не по зубам даже MIP. Т.е. все неразрешимые для современной науки задачи (включая задачу остановки) так и остаются неразрешимыми.
Мы натолкнулись на границу современной науки. Горизонт доступных нам проверяемых знаний. Что за горизонтом, мы не знаем. А чтобы пересечь границу и попытаться отодвинуть горизонт, нужно изменить законы физики.
Ибо физика определяет реальность.
Изменив законы физики, мы попадем в другую реальность, в которой, например, будет более сложная теория вероятностей.
Имея более сложную теорию вероятностей, мы сможем усложнить причинно-следственные связи и тем самым замахнуться на более высокий, чем MIP класс вычислительной сложности.
И оказывается, подрывная идея лежала под ногами. Просто, если мы исчерпали возможности классических компьютеров для трудно решаемых, но легко проверяемых задач классов P, NP, IP и MIP, надо перейти на квантовые компьютеры.
Теоретически просто. А как на практике?
Осталось понять, как там с возможностями проверки конкретных задач большей сложности.
Запутывание — как средство решения неразрешимых проблем
Квантовая физика открыла нам одно из самых странных и непостижимых разумом явлений — квантовое «запутывание».
В 1935 году (за год до того, как Тьюринг доказал неразрешимость проблемы остановки) Эйнштейн, Подольский и Розен открыли новый закон квантовой физики: две частицы могут быть запутаны или коррелированы, находясь друг от друга на любых сколь угодно огромных расстояниях. Когда две частицы запутаны, они фактически не влияют друг на друга — у них нет причинно-следственной связи.
А раз так, возникает довольно сумасшедшая мысль в контексте стратегий допроса двух подозреваемых.
Что будет, если установить между подозреваемыми квантовую связь посредством запутанности?
На вскидку, кажется, что подобное запутывание будет работать против Проверяющего. Ведь двум подозреваемым легче согласованно лгать, если у них есть способ связи для согласования своих ответов (например, перестукиваясь через стену).
Но оказывается, все наоборот. Запутывание не может обеспечить такую корреляцию показаний подозреваемых, которая бы способствовала их согласованному вранью. А вот следователь может использовать эту корреляцию в своих интересах выяснения истины.
Оказалось, что следователь (Проверяющий), вместо того, чтобы самому задавать вопросы подозреваемым (Решающим), может организовать процедуру так, чтобы подозреваемые допрашивали сами себя. В этом случае запутывание предоставляет фантастическую возможность переложить процесс проверки с Проверяющего на «запутанных Решающих».
Фишка здесь в том, что квантовая механика — это математическая система, не просто описывающая способ взаимодействия субатомных частиц, но и построенная на более сложной версии теории вероятностей.
Этим мы обязаны другому удивительному закону квантовой реальности — принципу неопределенности.
Этот принцип не позволяет нам одновременно знать положение и импульс частицы — если вы измеряете одно свойство, вы уничтожаете информацию о другом. Принцип неопределенности строго ограничивает то, что вы можете знать о любых двух «дополнительных» свойствах квантовой системы.
В случае же «допроса подозреваемых» запутанность позволяет Решающим генерировать взаимосвязанные вопросы, а принцип неопределенности не позволяет им вступить в сговор при ответе на них.
Образно говоря,
принцип неопределенности заставляет Решающих мгновенно забывать свои ответы, и потому они физически не могут вступить в сговор (ведь что сказал каждый из них, они уже забыли).
Прорыв за горизонт
Применение квантовой запутанности нескольких Решающих компьютеров позволяет Проверяющему компьютеру относительно быстро проверять решения более широкого класса задач, чем класс сложности MIP. Этот новый класс сложности, охватывающий и расширяющий все другие уже названные классы, назван MIP *, что означает Multi-Prover Interactive Proof с квантовой запутанностью.
И тут мы, наконец, добираемся до рассказа, почему новое исследование имеет хорошие шансы стать претендентом №1 на «оскара в науке» в 2021.
Во-первых, авторам удалось доказать, что класс сложности MIP * включает в себя все проблемы класса сложности RE. Что, собственно, и следует из названия работы «MIP * = RE».
Но что такое класс сложности RE? А вот что.
Класс RE — это огромное множество задач, названных рекурсивно перечислимыми. А насколько это множество огромно, хорошо определил один из соавторов новой работы Генри Юэн
«Это множество содержит все проблемы, которые могут быть решены с помощью компьютеров, и еще некоторые».
Это значит, что, теоретически, устройство класса MIP * может проверить решение даже неразрешимых проблем, включая проблему остановки. Т.е. если некий универсальный алгоритм способен решить для любой программы, остановится ли она, устройство класса MIP * сможет проверить правильность этого решения.
Звучит фантастически! Но есть огромное сомнение. И даже два.
· Сначала ведь задачу нужно решить, а уж потом проверять.
· Это ведь теоретически, а как на практике, слабо доказать что-то доселе неразрешимое?
А нисколечко, — отвечают авторы. Ща возьмем и решим.
И разрешили две проблемы о том, может ли нечто действительно бесконечное быть представлено его конечным приближением.
Проблемы Конна и Цирельсона
Когда была поставлена задача создания математической модели квантового запутывания, придумали два варианта.
В первом варианте договорились считать частицы пространственно изолированными друг от друга. Например, одна на Земле, а другой на Юпитере. И тогда само расстояние между ними предотвращает любые причинно-следственные связи. Такой вариант математического описания квантовой запутанности представляется моделью тензорного произведения.
Второй вариант более практичный (до Юпитера ведь долететь надо, чтоб туда частицу отвезти). Тогда решили просто считать, что частицы запутываются, если их свойства коррелированы, но порядок, в котором выполняются измерения показателей этих частиц, не имеет значения. Т.е. операции измерения обладают свойством коммутативности (типа, 3 x 2 — то же самое, что 2 x 3). На деле это означает: измеряете частицу A, чтобы предсказать импульс частицы B или наоборот, в любом случае, получите тот же ответ. Эту модель запутывания называли моделью коммутирующего оператора (или коммутирующей операторной — кому как нравится).
А теперь, в чем соль. Обе модели описываются матрицами. Но!
· Модель тензорного произведения использует матрицы с конечным числом строк и столбцов.
· А модель коммутирующего оператора использует матрицу с бесконечным числом строк и столбцов.
Известный математик по имени Ален Конн предположил в 1976 году, что квантовые системы с бесконечным числом измеримых переменных могут быть аппроксимированны более простыми системами с конечным числом измеримых переменных. Это предположение было следствием из т.н. гипотезы вложения Конна.
Эта проблема чисто математическая. Однако спустя 10 лет после Конна «бывший наш» прекрасный физик Борис Цирельсон переложил эту проблему для физики.
Он предположил, что тензорное произведение и коммутирующие операторные модели запутывания примерно эквивалентны. Основанием такого предположения был здравый смысл. Ведь теоретически это два разных способа описания одного и того же физического явления.
Последующая работа подтвердила, что математически, гипотеза о вложении Конна и проблема Цирельсона про одно и то же — может ли нечто действительно бесконечное быть представлено его конечным приближением. Из этого следовало: докáжете гипотезу Конна — решите проблему Цирельсона. И наоборот.
Решали долго. Но так и не пришли к итоговому решению.
А потом появилась работа «MIP * = RE», и как говорится в анекдоте, — “пришел лесник и выгнал из леса и нас, и немцев”.
Неправы оказались и физик, и математик.
Ответ на проблему Цирельсона — нет — т.е. две модели запутанности не эквивалентны.
Ответ на гипотезу Конна — нет — т.е. гипотеза неверна.
Теперь о самом главном
Весь предыдущий текст основан на информации от авторов работы, профильных специалистов и экспертов. Их главные выводы таковы.
Если в результате рецензирования этой работы, ее результаты будут подтверждены, можно будет зафиксировать следующее.
· Преодолён горизонт проверяемых знаний (т.е. знаний, в которых мы абсолютно уверены). Значительно увеличилось число проблем, которые подпадают под категорию «трудно решить, но легко проверить». Насколько увеличилось это число, и где теперь пролегает новая линия горизонта, — пока неизвестно. Но уже ясно, — потенциал возможностей квантовых интерактивных мультипруверов колоссален.
· Замена матмоделей бесконечных систем их конечными приближениями, как многие годы предполагали физики, больше не работает.
· Будут стараться физически реализовать урезанную версию компьютерной системы с квантово-запутанными Решателями. Полная реализация таких систем, вроде как, невозможна, но это еще надо проверять. А первые попытки реализации (на базе транзисторов с квантовой спиновой связью HEMT) уже начались.
Далее следуют мои собственные соображения.
У этой работы есть и 4-ое важнейшее следствие, о котором пока остерегаются писать солидные медиа, и его обсуждают лишь в «курилках» типа Matematics.
Следствие, точнее его логика, — такова.
· Вычислительные машины, имеющие архитектуру фон Неймана,
функционально эквивалентны универсальной машине Тьюринга.
· Согласно «Nogo теореме» Пенроуза, сильный ИИ невозможно создать на машинах, идеальной моделью которых является машина Тьюринга.
· Машина, описанная в работе «MIP * = RE», является более мощной, чем машина Тьюринга (за счет чего она и способна решать проблемы, нерешаемые на машине Тьюринга).
Можно ли на основе «MIP * машины» создать сильный ИИ, пока не понятно.
Тот же Пенроуз считает, что сильный ИИ не реализуем и на классических квантовых компьютерах, строящихся на основе вычислимой квантовой физики.
Нужна другая — невычислимая физика, ибо мозг, помимо вычислительной активности реализует невычислимую активность. А без последней человеческий и человекоподобный интеллект невозможны.
Так ли это, точно пока неизвестно. Но если выводы работы «MIP * = RE» подтвердятся, то описанная в ней идеальная модель, превосходящая вычислительные возможности машина Тьюринга, открывает новое окно возможностей.
Что за этим окном? Ведет ли оно к построению сильного ИИ?
Тоже пока неизвестно. Но это шаг за горизонт современной науки.
И даже если ответ будет подобен тем, что уже получены для гипотезы Конна и проблемы Цирельсона — нет, сильный ИИ невозможен на основе вычислимых законов физики — это будет гигантский научный прорыв, стóящий не одного «научного Оскара».
