MIP * = RE
В цифровом мире для любой задачи есть два ключевых вопроса:
• Насколько сложно это решить?
• Насколько сложно проверить правильность ответа?
Со сложностью решения можно бороться деньгами, привлекая больше спецов и наращивая вычислительные мощности.
А вот со вторым, увы, это работает не всегда. При определенном уровне вычислительной сложности никакие деньги не помогут - проверка правильности ответа становится теоретически невозможной.
Иными словами, мы сталкиваемся с неразрешимой проблемой.
Мы достигли границы проверяемых знаний.
Когда проблемы относительно просты, вы можете проверить ответ самостоятельно.
Но как быть с чрезвычайно сложными для проверки задачами?
В 1985 году придумали использовать метод, основанный на логике полицейского допроса. Если подозреваемый рассказывает чрезвычайно сложную для проверки историю, вам нет надобности искать подтверждение каждой детали. Вместо этого, просто задавая правильные вопросы, вы можете поймать своего подозреваемого на лжи или увериться, что он говорит правду.
С точки зрения информатики, такую схему легко повторить.
Взять мощный компьютер для решения задачи - назовем его «Решающий» (Prover). И менее мощный компьютер, который будет задавать вопросы Решающему, чтобы определить, является ли ответ Решающего правильным. Этот второй компьютер назовем «Проверяющий» (Verifier).
Подобные стратегии, получившие название «интерактивные доказательства», позволяют проверять решения задач, имеющих класс вычислительной сложности IP (Interactive polynomial time). Этот класс сложнее класса P (Polynomial time) - такие задачи легко решаются и проверяются (за полиноминальное время). Класс IP также сложнее класса NP - класс проблем, которые легко проверить, даже если некоторые из них трудно решить.
Еще более мощные интерактивные доказательства включают несколько Решающих.
Этот более сложный сценарий похож на допрос в полиции двух подозреваемых, находящихся в отдельных комнатах, которые не могут согласовать свои ответы, чтобы обмануть следователя. Такая схема проверки дает больше рычагов для Проверяющего. Если подозреваемые говорят правду, их ответы большую часть времени будут совпадать. Если же они лгут, ответы будут зачастую конфликтовать.
Такой класс сложности задач называется MIP (Multi-proven interactive proofs).
Для него было доказано, что при опросе двух Решающих можно быстро проверять решения большего класса задач, чем при одном Решающем.
То есть получилось следующее: множество задач класса сложности MIP самое большое. Оно включает в себя множество задач класса IP.
Последний, в свою очередь, включает в себя множество задач класса NP,
А класс NP, в свою очередь, включает в себя множество задач класса P.
Все это было бы хорошо, - но выяснилось следующее:
Класс сложности MIP исчерпывает возможности проверки правильности решений на классических компьютерах.
Проверка правильности решения неразрешимых проблем (типа проблемы остановки) не по зубам даже MIP.
Мы натолкнулись на границу современной науки. Горизонт доступных проверяемых знаний.
Что за горизонтом, мы не знаем.
А чтобы пересечь границу и попытаться отодвинуть горизонт, нужно изменить законы физики.
Ибо физика определяет реальность.
Изменив законы физики, мы попадем в другую реальность, в которой, например, будет более сложная теория вероятностей.
Имея более сложную теорию вероятностей, мы сможем усложнить причинно-следственные связи и тем самым замахнуться на более высокий, чем MIP класс вычислительной сложности.
И оказывается, подрывная идея лежала под ногами.
Квантовая физика открыла нам одно из самых странных и непостижимых разумом явлений - квантовое «запутывание».
А раз так, возникает довольно сумасшедшая мысль в контексте стратегий допроса двух подозреваемых.
Что будет, если установить между подозреваемыми квантовую связь посредством запутанности?
На вскидку, кажется, что подобное запутывание будет работать против Проверяющего. Ведь двум подозреваемым легче согласованно лгать, если у них есть способ связи для согласования своих ответов (например, перестукиваясь через стену).
Но оказывается, все наоборот.
Запутывание не может обеспечить такую корреляцию показаний подозреваемых, которая бы способствовала их согласованному вранью. А вот следователь может использовать эту корреляцию в своих интересах выяснения истины.
Оказалось, что следователь (Проверяющий), вместо того, чтобы самому задавать вопросы подозреваемым (Решающим), может организовать процедуру так, чтобы подозреваемые допрашивали сами себя. В этом случае запутывание предоставляет фантастическую возможность переложить процесс проверки с Проверяющего на «запутанных Решающих».
Фишка здесь в том, что квантовая механика - это математическая система, не просто описывающая способ взаимодействия субатомных частиц, но и построенная на более сложной версии теории вероятностей - принципу неопределенности.
Этот принцип не позволяет нам одновременно знать положение и импульс частицы - если вы измеряете одно свойство, вы уничтожаете информацию о другом.
Принцип неопределенности строго ограничивает то, что вы можете знать о любых двух «дополнительных» свойствах квантовой системы.
В случае же «допроса подозреваемых» запутанность позволяет Решающим генерировать взаимосвязанные вопросы, а принцип неопределенности не позволяет им вступить в сговор при ответе на них.
Образно говоря, принцип неопределенности заставляет Решающих мгновенно забывать свои ответы, и потому они физически не могут вступить в сговор (ведь что сказал каждый из них, они уже забыли).
Применение квантовой запутанности нескольких Решающих компьютеров позволяет Проверяющему компьютеру относительно быстро проверять решения более широкого класса задач, чем класс сложности MIP. Этот новый класс сложности, охватывающий и расширяющий все другие уже названные классы, назван MIP*, что означает Multi-Prover Interactive Proof с квантовой запутанностью.
И вот придуман метод, позволяющий проверить ответы на решение задач почти непостижимой и, даже можно сказать - эзотерической сложности.
Авторам удалось доказать, что класс сложности MIP* включает в себя все проблемы класса сложности RE.
MIP* = RE
Но что такое класс сложности RE?
А вот что:
Класс RE - это огромное множество задач, названных рекурсивно перечислимыми.
Это значит, что, теоретически, устройство класса MIP* может проверить решение даже неразрешимых проблем.
Когда была поставлена задача создания математической модели квантового запутывания, придумали два варианта:
• В первом варианте договорились считать частицы пространственно изолированными друг от друга. Например, одна на Земле, а другой на Юпитере. И тогда само расстояние между ними предотвращает любые причинно-следственные связи. Такой вариант математического описания квантовой запутанности представляется моделью тензорного произведения.
• Второй вариант более практичный (до Юпитера ведь долететь надо, чтоб туда частицу отвезти). Тогда решили просто считать, что частицы запутываются, если их свойства коррелированы, но порядок, в котором выполняются измерения показателей этих частиц, не имеет значения. То есть операции измерения обладают свойством коммутативности (типа, 3 x 2 - то же самое, что 2 x 3). На деле это означает: измеряете частицу A, чтобы предсказать импульс частицы B или наоборот, в любом случае, получите тот же ответ. Эту модель запутывания называли моделью коммутирующего оператора (или коммутирующей операторной).
Обе модели описываются матрицами. Но!
• Модель тензорного произведения использует матрицы с конечным числом строк и столбцов.
• Модель коммутирующего оператора использует матрицу с бесконечным числом строк и столбцов.
Математик Ален Конн в 1976 году предположил, что квантовые системы с бесконечным числом измеримых переменных могут быть аппроксимированны более простыми системами с конечным числом измеримых переменных. Это предположение было следствием из так называемой гипотезы вложения Конна.
Эта проблема чисто математическая.
Однако спустя 10 лет физик Борис Цирельсон переложил эту проблему для физики.
Он предположил, что тензорное произведение и коммутирующие операторные модели запутывания примерно эквивалентны. Основанием такого предположения был здравый смысл. Ведь теоретически это два разных способа описания одного и того же физического явления.
Последующая работа подтвердила, что математически, гипотеза о вложении Конна и проблема Цирельсона про одно и то же - может ли нечто действительно бесконечное быть представлено его конечным приближением.
Из этого следовало: докажете гипотезу Конна - решите проблему Цирельсона.
Решали долго. Но так и не пришли к итоговому решению.
А потом появилась работа «MIP * = RE», оказалось, что неправы и физик, и математик.
• Ответ на проблему Цирельсона - нет - то есть две модели запутанности не эквивалентны.
• Ответ на гипотезу Конна - нет - то есть гипотеза неверна.
Если в результате рецензирования этой работы, ее результаты будут подтверждены, можно будет зафиксировать следующее:
• Преодолён горизонт проверяемых знаний (т.е. знаний, в которых мы абсолютно уверены). Значительно увеличилось число проблем, которые подпадают под категорию «трудно решить, но легко проверить». Насколько увеличилось это число, и где теперь пролегает новая линия горизонта, - пока неизвестно. Но уже ясно, - потенциал возможностей квантовых интерактивных мультипруверов колоссален.
• Замена матмоделей бесконечных систем их конечными приближениями, как многие годы предполагали физики, больше не работает.
• Будут стараться физически реализовать урезанную версию компьютерной системы с квантово-запутанными Решателями. Полная реализация таких систем, вроде как, невозможна, но это еще надо проверять. А первые попытки реализации (на базе транзисторов с квантовой спиновой связью HEMT) уже начались.
/Источник №1//Источник №2//Источник №3/