Один квантовый запрос против миллиона классических. Физики доказали математически, что квантовый компьютер умеет то, что классическому недоступно в принципе

Квантовые компьютеры давно обещают превзойти классические машины, но доказать преимущество на строгом математическом уровне удается редко. Команда исследователей из Quantinuum и QuSoft представила алгоритм, который решает узкую, но принципиально важную задачу заметно эффективнее любых классических методов. Работа опубликована в журнале Physical Review Letters и демонстрирует доказуемое квантовое преимущество по числу необходимых выборок.

Речь идет о задаче complement sampling. Представим множество из N элементов и неизвестное подмножество S размером K. Алгоритм получает случайные элементы из S и должен выдать элемент, который в S не входит. На первый взгляд задача выглядит простой, но в классической модели быстро упирается в потолок.

Если размер подмножества равен половине исходного множества, классическому алгоритму приходится собрать почти полную информацию о составе S. Чтобы с вероятностью хотя бы немного выше случайной угадать элемент вне S, требуется порядка N различных выборок. Без знания внутренней структуры подмножества классическая схема фактически вынуждена перебирать почти все варианты.

Квантовый алгоритм действует иначе. Вместо набора отдельных элементов машина получает одно квантовое состояние, которое представляет равномерную суперпозицию всех элементов S. Такая суперпозиция кодирует подмножество целиком и когерентно. Исследователи показали, что при K = N/2 достаточно одной такой квантовой выборки. Алгоритм преобразует состояние в суперпозицию элементов дополнения, после чего измерение выдает случайный элемент вне S с гарантированным успехом.

Авторы подчеркивают, что речь не о выигрыше по времени работы. Преимущество проявляется в sample complexity, то есть в числе необходимых выборок. Квантовой машине хватает одного состояния, тогда как классическому алгоритму требуется число выборок, пропорциональное размеру всего множества. Источник выигрыша лежит в способе хранения и обработки квантовой информации, а не в «более быстром» счете.

Интересно, что ключевое наблюдение исследователи сделали случайно, работая над другой задачей. Два квантовых состояния, сформированные из двух половин одного и того же набора, трудно различить напрямую. Зато простая операция позволяет легко превратить одно состояние в другое. Из этой идеи и выросла строгая формализация complement sampling.

Авторы считают, что подход открывает новый способ демонстрировать квантовое преимущество, который проще проверить экспериментально и реализовать на существующем оборудовании. Команда уже провела тысячи запусков алгоритма на ионных квантовых компьютерах Quantinuum System Model H2 и опубликовала предварительные результаты на arXiv. Эксперименты показали хорошее совпадение с теоретическими предсказаниями.

Дополнительно исследователи отмечают возможные применения в криптографии. Задачу complement sampling можно встроить в псевдослучайные конструкции, где классическая сложность опирается на стандартные криптографические допущения. Квантовый алгоритм в такой схеме способен усилить отдельные протоколы и изменить баланс между классическими и квантовыми атаками.

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