Задача QMA считается квантовым аналогом NP. «Доказывающий» Мерлин отправляет квантовое свидетельство — особое квантовое состояние — «проверяющему» Артуру, который запускает квантовый алгоритм для проверки, является ли ответ на задачу «да». Если доказательство верно, Артур принимает его, если ложно, то отвергает. Решающее значение для обеих систем имеют два числа: полнота, или вероятность того, что Артур примет верное доказательство, и непротиворечивость, или вероятность того, что он ошибочно примет ложное. Обычные пороговые значения — 2/3 и 1/3. Но эти числа можно увеличить с помощью амплификации, когда проверяющий повторяет проверку и объединяет результаты.
Авторы исследования, Скотт Ааронсон из Техасского университета в Остине (США) и Фрик Виттевен из CWI Amsterdam (Нидерланды) решили ответить на вопрос, который оставался открытым в течение многих лет: насколько методы черного ящика могут повысить надежность систем доказательств QMA?
Методы амплификация позволяют снизить вероятность ошибок. Ученые продемонстрировали, что полнота может стремиться к единице с двойной экспоненциальной скоростью. Оставался открытым вопрос, может ли она превзойти это значение, пишет Quantum Insider.
Когда первые попытки решения зашли в тупик, Ааронсон решил обратиться к GPT-5. Сначала версии, предложенные моделью, были ошибочными. Однако после нескольких раундов обсуждений GPT-5 предложила переформулировать задачу, используя простое математическое выражение, которое отражало бы, насколько вероятность принятия доказательства проверяющей системой может приблизиться к уверенности.
Эта идея оказалась решающей. Проанализировав выражение с помощью инструментов аппроксимационной теории, исследователи смогли, наконец, подтвердить строгие ограничения на компенсацию погрешностей QMA. Полнота не может превысить уровень двойной экспоненциальной близости к единице, а достоверность не может опуститься ниже экспоненциально малой величины.
«Я пробовал решать похожие задачи год назад, используя новые для того времени модели рассуждений GPT, но мои результаты были далеко не такими хорошими, — пишет Ааронсон в своем блоге. — Сейчас, в сентябре 2025 года, я готов сообщить, что ИИ наконец-то приступил к выполнению того, что, по моему опыту, является самой типично человеческой из всех видов интеллектуальной деятельности: а именно, к доказательству разделения оракулов между классами квантовой сложности».
Результат подтверждает, что для определения равенства между QMA и QMA1 потребуются нерелятивизирующие методы, которые будут анализировать структуры схем, а не рассматривать их как черные ящики. Очевидна также асимметрия: полнота зависит от одного надежного свидетельства, в то время как непротиворечивость должна быть подтверждена всеми возможными свидетельствами.
Исследование оставляет открытыми важные вопросы, в том числе вопрос о том, равно ли QMA QMA1. Но оно знаменует собой поворотный момент: ИИ больше не ограничивается только составлением документов или написанием кода.
Новая технология на основе искусственного интеллекта, разработанная в США, впервые позволила обнаружить жизнеспособные сперматозоиды у мужчины с диагнозом азооспермия — отсутствием сперматозоидов в эякуляте. Используя алгоритмы, изначально созданные для поиска далеких звезд, система помогла паре зачать ребенка.
