«Теоретически, а не практически»: IBM доказала преимущество квантовых схем над LLM на двух задачах

Зачем сравнивать квантовое с языковыми моделями

Исходный вопрос IBM сформулировала так: для каких вычислительных задач квантовые подходы обойдут классические и насколько именно. Доказать теоретические пределы классических моделей трудно, потому что многие идеализированные классические модели при достаточных ресурсах симулируют произвольную машину Тьюринга; поэтому в работе квантовые вычисления сопоставляются не с ними, а с более ограниченными моделями — конкретными урезанными версиями больших языковых моделей (LLM).

Линия исследований, к которой относится работа, — квантовые схемы малой глубины: глубина схемы остаётся постоянной при росте числа кубитов. Опорная точка — результат Сергея Бравого (Sergey Bravyi), Дэвида Госсета (David Gosset) и Роберта Кёнига (Robert König), опубликованный в Science в 2018 году: некая модель схем постоянной глубины решает поисковые задачи, недоступные сопоставимым классическим схемам постоянной глубины. Препринт этой работы вышел на arXiv ещё в апреле 2017 года, где доказано, что схемы постоянной глубины мощнее классических аналогов, и построен конкретный пример — задача 2D Hidden Linear Function.

С тех пор, по описанию IBM, классический соперник в этих сравнениях становился всё сильнее, а квантовая сторона оставалась «заметно мелкой».

Функциональная сепарация: задача итерированного индекса

Функциональные задачи — те, где на вход нужно вернуть правильный выход, например достать конкретную информацию по промпту. Площадкой для первой сепарации взята задача итерированного индекса: представьте указатель в конце книги, который ведёт не на страницу этой книги, а на запись в указателе второй книги, та — в третьей, и так далее; вопрос — куда вы попадёте, пройдя всю цепочку ссылок.

Классическую половину сепарации дала адаптация прежнего результата о вычислительной сложности трансформеров: нижняя оценка показывает, что трансформеру для решения этой задачи нужно достаточно много ресурсов. Квантовую половину авторы доказали сами: задача решается квантовой схемой почти постоянной глубины с одним классическим гейтом AND, и эту глубину нельзя осмысленно улучшить — сделать её действительно постоянной не получится.

В препринте формулировка строже: существует функция, вычислимая схемой с глубиной O(log log n) и одним классическим гейтом AND, для которой любой декодерный трансформер постоянной глубины обязан быть большим — с шириной n в степени Ω(1). Практическая деталь: речь именно о декодерных трансформерах, то есть о той архитектуре, на которой построены известные модели вроде GPT, Claude и Llama.

Сэмплирующая сепарация: parity-sampling против diffusion-моделей

Второй класс задач — сэмплирующие: нужно не единственно верное значение, а выход, распределённый по заданному вероятностному распределению; типичный пример — генерация изображений диффузионными моделями. Здесь IBM работает с diffusion language models (DLM): они обучаются восстанавливать текст, «испорченный» случайным шумом, шаг за шагом разворачивая процесс порчи, а на инференсе начинают со случайного шума и постепенно его убирают.

Задача parity-sampling устроена просто: по строке из нулей и единиц нужно понять её чётность — чётное или нечётное число единиц — и сэмплировать строки с заданной чётностью. Квантовый подход использует запутанность и интерференцию, чтобы предсказать чётность за постоянную глубину схемы.

Раньше для DLM уже были доказаны ограничения на версию этой задачи, но они не покрывали модель с chain-of-thought — способностью «показывать работу», генерируя и потребляя промежуточные токены, что обычно значительно усиливает модель. Новизна работы в том, что нижняя оценка распространена на этот, более сильный случай: даже с доступом к некоторому объёму chain-of-thought diffusion-модель не может эффективно воспроизвести распределение, которое порождает мелкая квантовая схема.

В препринте это сказано ещё жёстче: никакая DLM с постоянным числом раундов и мелким расписанием шума не сэмплирует такое распределение с точностью до константы, даже если ей разрешить сублинейный chain-of-thought и пересмотр или перемаскирование выходных токенов — то есть именно те возможности, на которые современные DLM и опираются.

Чего в работе нет

Прежде чем переносить выводы на реальные продукты, стоит зафиксировать рамки. Препринт — это 60 страниц и 6 рисунков математики; его авторы — Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi и Rik Sengupta, а разбор в блоге IBM подписан теми же четырьмя исследователями и редактором Райаном Мандельбаумом.

Работа объявлена как «строго теоретическая и состоящая из математических доказательств». В ней нет ни экспериментов, ни прогонов на железе, ни бенчмарков: авторы прямо пишут, что сегодняшние квантовые компьютеры ограничены по возможностям, подвержены шуму и ошибкам, тогда как классические LLM работают на вычислительном железе беспрецедентного масштаба.

Самый практичный пункт — то, чего в статье не измерили: точный масштаб, при котором квантовые системы обойдут эти LLM на изученных задачах, не определён. Доказано только асимптотическое преимущество при прямом сравнении.

Что из этого следует

IBM формулирует вывод осторожно: работа должна подпитывать усилия по созданию квантовых компьютеров и открывать дорогу к конкретным бенчмаркам, которые сравнивают квантовые системы и LLM на таких задачах. Более широкая цель линии исследований — карта всех безусловных сепараций между общими квантовыми и классическими вычислениями, но до неё, по собственному признанию авторов, далеко.

Есть и неожиданный поворот: вместо конкуренции IBM предлагает рассматривать квантовые вычисления как возможное дополнение классических ИИ-систем — тогда часть задач, требующих существенно больших ресурсов, удалось бы решать иначе. Для читателя, который следит за новостями об «ИИ против квантовых компьютеров», практический смысл статьи в том, что речь идёт об асимптотических утверждениях для ограниченных классов моделей, а не о сравнении продуктов, которое можно проверить сегодня.