Математики вышли на новые рубежи в деле проверки решений задач вычислительными методами. При этом они, как бы побочно, но, что интересно, всё же нашли ответы на открытые вопросы чистой математики, самое главное квантовой механики. Авторы математического исследования MIP* = RE поставили перед собой цель определить границы подхода по проверке решений вычислительных задач, привязав к этому и имеющиеся математические представления о квантовой запутанности. Границы они нашли, при этом показав ложность некоторых математических теорем, до этого как бы принятых за аксиомы многими математиками.
Некие границы для применения математических формул определил когда-то Алан Тьюринг, ещё до появления компьютеров, когда он сформулировал первую общую теорию вычислений. Он доказывал, что существуют задачи, которые никогда не смогут быть решены. Многие математики не могли принять это без сопротивления, а выражали своё сопротивление в виде выдумки разных формул. Когда появились компьютеры, математики решили, что эти приборы опровергнут доказательства Тьюринга, но, конечно, компьютеры не всегда справились с множеством таких формул, ибо они ограничены в возможностях оперирования единицами и нолями. После некоторого периода уныния математики стали возлагать свои надежды на теоретически предсказанные ими же квантовые компьютеры, которые как бы должны производить любые вычисления, оперируя запутанными квантовыми битами (кубитами).
Тьюринг, доказывая ограниченность возможностей математики, показал, что существует определённая задача, которую компьютеры решить не могут. Это – так называемая проблема останова.
Обычно компьютерные программы получают что-то на вход и генерируют выходные данные. Но иногда они застревают в бесконечных циклах, а значит – никогда не останавливаются. Когда такое происходит, есть лишь один выход из сложившейся ситуации. По словам Генри Юэня, нужно вручную остановить программу. Нужно просто поставить точку в её работе.
Тьюринг доказал, что не существует универсального алгоритма, способного выяснить, будет ли программа когда-нибудь остановлена. Для того чтобы это узнать, надо запустить эту программу.
Авторы описываемого математического исследования приводят примеры программ, используя по обычаю как бы учёных ролевые игры в допрос свидетелей. Но можно привести более простой пример программы, о которой неизвестно остановится ли она когда-нибудь.
Это программа вычисления числа π.
Тьюринг, с технической точки зрения, доказал, что задача останова неразрешима. Даже самый мощный компьютер, который можно себе представить, не способен с ней справиться.
И вот очередное исследование молодых математиков не только в очередной раз подтвердило идеи Тьюринга и перечеркнуло веру в безграничные возможности математики, но и как бы попутно отвергло теории квантовой запутанности.
Речь идёт о гипотезе Цирельсона, касающейся математического моделирования квантовой запутанности, и как бы связанной с этой фантазией задачи в чистой математике, так называемой проблемы Конна в теории алгебр фон Неймана (проблемы вложения Конна), а так же статистических математических работ Джона Белла о квантовой запутанности.
Известный математик Ален Конн предположил в 1976 году, что квантовые системы с бесконечным числом измеримых переменных могут быть аппроксимированы более простыми системами с конечным числом измеримых переменных. Это предположение было следствием из так называемой гипотезы вложения Конна.
В следующем десятилетии физик-теоретик Борис Цирельсон сформулировал версию гипотезы вложения Конна, применив её к современной как бы физике, а именно к измышлениям о запутанных частицах. Цирельсон предположил, что модели тензорного произведения и коммутирующего оператора примерно эквивалентны друг другу. Это утверждение как бы имеет математический смысл. Последователи нашли, что задачи Конна и Цирельсона косвенно связаны: если решить одну, то будет решена и другая.
Полсотни лет назад теоретик от физики Джон Белл придумал как бы тест для определения того, является ли квантовая запутанность реальным физическим явлением, а не теоретическим понятием. В тесте, по обычаю как бы учёных для иллюстрации этих теорий использовали нечто вроде игры, результаты которой якобы позволяли узнать о том, действуют ли в ходе игры некие механизмы, не относящиеся к обычной физике.
Позже специалисты по информатике применили тест, касающийся квантовой запутанности, как инструмент для как бы верификации решений других своих задач. И получили разочарование. В 2016 году Уильям Слофстра доказал, что не существует общего алгоритма для вычисления точной максимальной вероятности выигрыша для всех нелокальных игр.
Математики задались вопросом: может можно хотя бы приблизительно подсчитать максимальный процент выигрышей?
Попытались использовать две модели квантовой запутанности. Алгоритм, который использует модель тензорного произведения, задаёт минимальное значение при приближённом вычислении максимальной вероятности выигрыша для всех нелокальных игр. Другой алгоритм, в котором используется модель коммутирующего оператора, задаёт максимальное значение. Ответ этих алгоритмов, якобы тем точнее, чем дольше выполняется программа. По Цирельсону в эти две модели эквивалентны и нижняя и верхняя оценки должны приближаться к друг другу, превращаясь в единственное значение, представляющее приблизительную максимальную вероятность выигрыша.
Но если гипотеза Цирельсона не верна, и две модели не эквивалентны, то, по словам Генри Юэня, верхняя и нижняя оценка всегда будут разделены. И не будет способа рассчитать даже приблизительный процент выигрышей для нелокальных игр.
Математики в описываемой работе воспользовались рассуждениями о том, сходятся ли верхняя и нижняя оценки, и о том, истинна или ложна гипотеза Цирельсона.
Оказалось, что гипотеза Цирельсона ложна
Это значит, что определить приблизительную максимальную вероятность выигрыша для конкретной нелокальной игры, то вам сначала придётся решить задачу останова. Но решить эту задачу невозможно. Это означает, что нахождение приблизительного максимального уровня вероятности выигрыша для нелокальных игр так же, как и для задачи останова, невозможно.
А это, в свою очередь, значит, что две модели квантовой запутанности не эквивалентны. Если бы они были эквивалентны, то можно было бы свести нижнюю и верхнюю оценку к одному и тому же значению и вычислить приблизительную максимальную вероятность выигрыша.
Описываемая работа доказывает то, что класс задач, решения которых можно верифицировать с помощью запутанных квантовых доказывателей, класс, называемый MIP(Многофункциональные интерактивные доказательства), в точности равен классу задач, которые не сложнее задачи останова – классу RE. В заголовке работы имеется сжатое указание на это: “MIP = RE”.
В ходе вывода доказательства того, что два класса сложности равны, учёные доказали ложность гипотезы Цирельсона, гипотезы Конна, и математических работ Белла о запутанных фотонах.