Крупный прорыв в квантовых вычислениях потряс физику и математику
Анатолий Шуклецов - 15.08.20 (обновлено 15.08.20) MIP * = RE не является опечаткой. Это революционное открытие и броское название недавней статьи в области квантовой теории сложности. Теория сложности – это зоопарк «классов сложности» – совокупностей вычислительных задач, из которых MIP * и RE – всего два.
В 165-страничном документе показано, что эти два класса одинаковы. Это может показаться незначительной деталью абстрактной теории без какого-либо реального применения. Но физики и математики стекаются в зоопарк, хотя, вероятно, они всего этого не понимают. Потому что оказывается, что это открытие имеет поразительные последствия для их собственных дисциплин.
Фото: https://www.qvcon2020.com/
В 1936 году Алан Тьюринг показал, что проблема остановки – алгоритмическое решение, когда останавливается компьютерная программа или зацикливается навсегда – не может быть решена. Так родилась современная информатика. Его успех произвел впечатление, что вскоре все практические задачи уступят место огромной мощности компьютера.
Но вскоре стало очевидно, что, хотя некоторые проблемы могут быть решены алгоритмически, фактические вычисления будут длиться еще долго после того, как наше Солнце поглотит компьютер, выполняющий вычисления. Недостаточно было понять, как решить проблему алгоритмически. Было жизненно важно классифицировать решения по эффективности. Теория сложности классифицирует проблемы в зависимости от того, насколько сложно их решить. Сложность проблемы измеряется тем, как долго длится вычисление.
RE означает проблемы, которые можно решить с помощью компьютера. Это зоопарк. Давайте посмотрим на некоторые подклассы.
Класс P состоит из задач, которые известный алгоритм может решить быстро (технически за полиномиальное время). Например, умножение двух чисел относится к P, так как длинное умножение является эффективным алгоритмом решения проблемы. Неизвестно, что проблема нахождения простых делителей числа находится в P; проблема, безусловно, может быть решена компьютером, но ни один известный алгоритм не может сделать это эффективно. Родственная проблема, решение, если данное число является простым, не была в подобном подвешенном состоянии до 2004 года, когда эффективный алгоритм показал, что эта проблема в P.
Другой класс сложности – NP. Представьте себе лабиринт. «Есть ли выход из этого лабиринта?» это вопрос да / нет. Если да, то есть простой способ убедить нас: просто дайте нам указания, мы будем следовать им и найдем выход. Однако если ответ отрицательный, нам придется пройти через весь лабиринт, так и не найдя выхода, чтобы убедиться.
Такие задачи типа да / нет, для которых, если ответ положительный, мы можем эффективно продемонстрировать это, принадлежат NP. Любое решение проблемы убеждает нас в ответе, и поэтому P содержится в NP. Удивительно, но вопрос на миллион долларов заключается в том, действительно ли P = NP. Никто не знает.
Фото: https://excelerator.solutions/
Доверие машинам
Описанные до сих пор классы представляют проблемы, с которыми сталкивается обычный компьютер. Но компьютеры кардинально меняются – разрабатываются квантовые компьютеры. Но если появляется новый тип компьютера, который утверждает, что решает одну из наших проблем, как мы можем верить, что он правильный?
Представьте себе взаимодействие между двумя сущностями, следователем и доказывающим. На допросе в полиции доказывающим может быть подозреваемый, пытающийся доказать свою невиновность. Следователь должен решить, достаточно ли убедителен доказывающий. Есть дисбаланс; с точки зрения знаний следователь находится в более низком положении.
В теории сложности допрашивающий – это человек с ограниченными вычислительными возможностями, пытающийся решить проблему. Доказательством является новый компьютер, который, как предполагается, обладает огромной вычислительной мощностью. Интерактивная система доказательств представляет собой протокол, следователь может использовать для того, чтобы определить, по крайней мере, с большой долей вероятности, следует ли верить этому. По аналогии, это преступления, которые полиция может не раскрыть, но, по крайней мере, невиновные могут убедить полицию в своей невиновности. Это класс IP.
Если можно допросить нескольких испытуемых, а доказывающим не разрешено координировать свои ответы (как это обычно бывает, когда полиция допрашивает нескольких подозреваемых), то мы попадаем в класс MIP. Такие допросы посредством перекрестного изучения ответов проверяющих наделяют запросчика большей мощностью, поэтому протокол MIP содержит IP.
Квантовая коммуникация – это новая форма коммуникации, осуществляемая с помощью кубитов. Запутанность – квантовая особенность, в которой кубиты пугающе запутаны, даже если они разделены – делает квантовую коммуникацию принципиально отличной от обычной коммуникации. Разрешение испытателям MIP совместно использовать запутанный кубит приводит к классу MIP *.
Фото: https://vk.com/
Кажется очевидным, что общение между доказывающими может служить только для того, чтобы помочь доказывающим координировать ложь, а не помогать допрашивающему в обнаружении истины. По этой причине никто не ожидал, что расширение обмена данными сделает вычислительные задачи более надежными и разрешимыми. Удивительно, но теперь мы знаем, что MIP * = RE. Это означает, что квантовая коммуникация ведет себя совершенно иначе, чем обычная коммуникация.
Далеко идущие последствия
В 1970-х годах Ален Конн сформулировал так называемую проблему вложения Конна. Существенно упрощенный, это вопрос, можно ли аппроксимировать бесконечные матрицы конечными матрицами. Эта новая статья доказала, что это невозможно – важный вывод для чистых математиков.
Тем временем в 1993 году Борис Цирельсон обозначил проблему в физике, которая теперь известна как проблема Цирельсона. Речь шла о двух различных математических формализмах одной ситуации в квантовой механике – на сегодняшний день невероятно успешной теории, объясняющей субатомный мир. Поскольку это два разных описания одного и того же явления, следовало ожидать, что эти два формализма математически эквивалентны.
Но новая статья теперь показывает, что это не так. Неизвестно, как именно они оба могут по-прежнему давать одинаковые результаты и описывать одну и ту же физическую реальность, но именно поэтому физики внезапно проявляют интерес. Время покажет, какие еще оставшиеся без ответа научные вопросы уступят место изучению сложности. Несомненно, MIP * = RE – большой шаг вперед.
Комментарии