2025-11-23T13:22:17.314370

Recent quantum runtime (dis)advantages

Tuziemski, Pawłowski, Tarasiuk et al.
We (re)evaluate recent claims of quantum advantage in annealing- and gate-based algorithms, testing whether reported speedups survive rigorous end-to-end runtime definitions and comparison against strong classical baselines. Conventional analyses often omit substantial overhead (readout, transpilation, thermalization, etc.) yielding biased assessments. While excluding seemingly not important parts of the simulation may seem reasonable, on most current quantum hardware a clean separation between "pure compute" and "overhead" cannot be experimentally justified. This may distort "supremacy" results. In contrast, for most classical hardware total time $\approx$ compute $+$ a weakly varying constant leading to robust claims. We scrutinize two important milestones: (1) quantum annealing for approximate QUBO PRL 134, 160601 (2025) [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.134.160601], which uses a sensible time-to-$ε$ metric but proxies runtime by the annealing time (non-measurable); (2) a restricted Simon's problem PRX 15, 021082 (2025) [https://journals.aps.org/prx/abstract/10.1103/PhysRevX.15.021082] , whose advantageous scaling in oracle calls is undisputed; yet, as we demonstrate, estimated runtime of the quantum experiment is $\sim 100 \times$ slower than a tuned classical baseline. Finally, we show that recently claimed "runtime advantage" of the BF-DCQO hybrid algorithm (arXiv:2505.08663) does not withstand rigorous benchmarking. Therefore, we conclude that runtime-based supremacy remains elusive on NISQ hardware, and credible claims require a careful time accounting with a proper reference selections, and an adequate metric.
academic

Недавние (не)преимущества квантового времени выполнения

Основная информация

  • ID статьи: 2510.06337
  • Название: Recent quantum runtime (dis)advantages
  • Авторы: J. Tuziemski, J. Pawłowski, P. Tarasiuk, Ł. Pawela, B. Gardas
  • Классификация: quant-ph
  • Дата публикации: 16 октября 2025 г. (arXiv v2)
  • Ссылка на статью: https://arxiv.org/abs/2510.06337

Аннотация

В данной работе переоценены недавние утверждения о квантовом преимуществе, в частности в квантовом отжиге и алгоритмах на основе вентилей, путём проверки того, сохраняются ли заявленные ускорения при строгом определении сквозного времени выполнения и справедливом сравнении с мощными классическими эталонами. Традиционный анализ часто игнорирует значительные накладные расходы (чтение, трансляция, термализация и т.д.), что приводит к смещению оценок. Авторы рассматривают три важных вехи: (1) квантовый отжиг для приближённого QUBO; (2) ограниченная задача Саймона; (3) гибридный алгоритм BF-DCQO. Результаты показывают, что квантовое преимущество на основе времени выполнения на оборудовании NISQ остаётся труднодостижимым.

Исследовательский контекст и мотивация

Исследовательский вопрос

Центральный вопрос, который решает данная работа: Остаются ли действительными текущие утверждения о квантовом преимуществе при строгом определении времени выполнения и справедливом сравнении классических эталонов?

Значимость проблемы

  1. Практические соображения: Конечная цель квантовых вычислений — превзойти классические вычисления в практических приложениях, а производительность по времени выполнения является ключевым показателем практической ценности
  2. Проблема смещения оценок: Существующие исследования часто игнорируют значительные накладные расходы квантового оборудования, что приводит к чрезмерно оптимистичной оценке квантового преимущества
  3. Научная строгость: Необходимо установить справедливые и строгие методы тестирования для оценки реальной производительности квантовых алгоритмов

Ограничения существующих методов

  1. Неправильное определение времени выполнения: Многие исследования рассматривают только «чистое время вычисления», игнорируя накладные расходы на чтение, термализацию, трансляцию и т.д.
  2. Смещение в выборе эталонов: Неправильный выбор классических алгоритмов сравнения, отсутствие использования передовых методов параллелизации
  3. Недостаточный статистический анализ: Отсутствие адекватного статистического анализа, проблема cherry-picking

Исследовательская мотивация

Авторы считают, что по мере развития квантовых технологий необходимы более строгие критерии оценки для проверки подлинности квантового преимущества и предотвращения преувеличенных заявлений, влияющих на научное суждение.

Основные вклады

  1. Установление строгой структуры определения времени выполнения: Предложено полное определение времени выполнения, включающее все необходимые компоненты (программирование, выполнение, чтение, термализация)
  2. Переоценка трёх важных утверждений о квантовом преимуществе:
    • Преимущество квантового отжига при приближённом решении задач QUBO
    • Преимущество в сложности запросов для ограниченной задачи Саймона
    • Преимущество времени выполнения гибридного алгоритма BF-DCQO
  3. Выявление коренных причин смещения оценок: Анализ причин, по которым квантовому оборудованию сложно достичь чёткого разделения между «чистыми вычислениями» и «накладными расходами»
  4. Предоставление руководства по справедливому тестированию: Установление стандартов и методологии оценки для будущих утверждений о квантовом преимуществе

Подробное описание методов

Определение задач

В данной работе переоценивается производительность квантовых алгоритмов на следующих трёх конкретных задачах:

  • Входные данные: Экземпляры задач оптимизации, запросы Oracle, задачи HUBO
  • Выходные данные: Решение задачи или результаты запросов
  • Ограничения: Реальная производительность по времени выполнения в условиях ограничений современного оборудования NISQ

Структура определения времени выполнения

Время выполнения устройства квантового отжига

Полное время выполнения квантового отжига должно включать:

Общее время выполнения = Время программирования + Время отжига + Время чтения + Время термализации

Ключевые выводы:

  • Время чтения ~200 мкс, в то время как время отжига составляет только 0,5–27 мкс
  • Время чтения на два порядка величины больше времени отжига
  • Это приводит к серьёзному искажению оценки производительности на основе времени отжига

Время выполнения цифрового квантового устройства

Полное время выполнения цифровых квантовых вычислений включает:

Общее время выполнения = Время предварительной обработки + Время трансляции + Время выполнения + Время чтения + Время термализации

Метрика Time-to-ε (TTε)

TTε=tf⋅log⁡(1−0.99)log⁡(1−pE≤E0+ε∣E0)TTε = t_f \cdot \frac{\log(1-0.99)}{\log(1-p_{E≤E_0+ε|E_0})}

Где:

  • tft_f: время генерации решения
  • pE≤E0+ε∣E0p_{E≤E_0+ε|E_0}: вероятность нахождения решения в пределах ε-оптимальности

Технические инновации

  1. Комплексное измерение времени выполнения: Первая систематическая попытка включить временные затраты всех этапов квантовых вычислений
  2. Мощные классические эталоны: Использование оптимизированных на GPU параллельных алгоритмов (например, SBM) в качестве эталонов
  3. Статистическая строгость: Избежание cherry-picking, использование достаточного количества экземпляров для статистического анализа

Экспериментальная установка

Оцениваемые случаи

Случай 1: Квантовый отжиг для приближённого QUBO

  • Набор данных: Экземпляры Sidon-28, размер N∈142, 1322
  • Квантовое устройство: Квантовый отжиг D-Wave
  • Классический эталон: Симулированная машина ветвления (SBM)
  • Метрика: Медиана TTε

Случай 2: Ограниченная задача Саймона

  • Размер задачи: 29-битный вход, вес Хэмминга w∈2,7
  • Квантовое устройство: IBM Brisbane
  • Классическая реализация: Алгоритм перебора на GPU
  • Метрика: Количество вызовов Oracle и реальное время выполнения

Случай 3: Гибридный алгоритм BF-DCQO

  • Тип задачи: Неограниченная бинарная оптимизация высокого порядка (HUBO)
  • Размер экземпляров: N∈80, 100, 130, 156
  • Методы сравнения: CPLEX, имитация отжига, SBM

Детали реализации

  • Аппаратная среда: Двойной процессор Intel Xeon Platinum 8462Y+, 4×NVIDIA H100 GPU, 1 ТБ ОЗУ
  • Статистический метод: 50 случайных экземпляров, несколько независимых прогонов
  • Оптимизация параметров: Все алгоритмы подвергались оптимизации гиперпараметров

Результаты экспериментов

Основные результаты

Результаты квантового отжига

При использовании полного определения времени выполнения:

  • TTεMed почти постоянна: Неопределённость подобранного показателя экспоненты α слишком велика для получения ненулевого вывода
  • Время чтения доминирует: Составляет основную часть общего времени выполнения
  • SBM показывает лучшие результаты: Демонстрирует лучшую масштабируемость на аналогичных задачах

Результаты ограниченной задачи Саймона

  • Преимущество в сложности запросов действительно существует: Квантовый алгоритм теоретически требует меньше вызовов Oracle
  • Значительное практическое неудобство по времени выполнения:
    • При N=29, w=7: классический алгоритм ~0,035 с, квантовый алгоритм ~2 с
    • Квантовый алгоритм медленнее примерно в 100 раз
    • Предполагаемая точка пересечения при N≈60, но шум ограничивает практическую достижимость

Результаты гибридного алгоритма BF-DCQO

  • Методологические проблемы: Неточные оценки времени выполнения, игнорирование важных накладных расходов
  • Статистические проблемы: Cherry-picking на основе небольшого количества экземпляров (5 шт.)
  • Явное преимущество SBM: Лучшая производительность на аналогичных задачах

Абляционные эксперименты

Анализ чувствительности определения времени выполнения

Сравнение влияния различных определений времени выполнения:

Определение времени выполненияПоказатель экспоненты α квантового отжигаПоказатель экспоненты α SBM
Только время отжига2,23±0,25-
Общее время QPU0,61±1,20-
Полное время выполнения0,93±1,241,83±0,11

Результаты показывают, что квантовый алгоритм чрезвычайно чувствителен к определению времени выполнения, в то время как классический алгоритм относительно устойчив.

Анализ конкретных случаев

Сложность экземпляров HUBO

Генерируемые экземпляры HUBO демонстрируют различную сложность для разных алгоритмов:

  • SBM: Более низкий процент успеха на экземплярах распределения Коши, но явное преимущество по времени выполнения
  • SA(QUBO): Лучшее качество решения, но более длительное время выполнения
  • SA(HUBO): Отличная производительность на экземплярах распределения Парето

Это указывает на то, что характеристики экземпляров оказывают значительное влияние на производительность алгоритма, требуя достаточного статистического анализа.

Связанные работы

Теоретические основы квантового преимущества

  • Алгоритм Саймона: Экспоненциальное разделение сложности запросов
  • Алгоритм Шора: На основе предположения о сложности факторизации
  • Выборка случайных схем: Первое экспериментальное утверждение о квантовом преимуществе

Эвристические квантовые алгоритмы

  • Квантовый отжиг: Поиск преимущества на конкретных экземплярах задач NP-hard
  • Вариационные квантовые алгоритмы: Основное направление эпохи NISQ
  • Гибридные квантово-классические алгоритмы: Объединение преимуществ обеих парадигм вычислений

Методология тестирования

  • Метрика TTε: Стандартный метод оценки приближённой оптимизации
  • Структура сложности запросов: Важный инструмент теоретического анализа
  • Выбор классических эталонов: Ключевой фактор, влияющий на достоверность утверждений о квантовом преимуществе

Выводы и обсуждение

Основные выводы

  1. Квантовое преимущество по времени выполнения на оборудовании NISQ остаётся труднодостижимым: При строгом определении времени выполнения и справедливом сравнении эталонов все проверенные утверждения о квантовом преимуществе не подтверждаются
  2. Определение времени выполнения имеет критическое значение: Высокие накладные расходы квантового оборудования делают сложным разделение между «чистыми вычислениями» и «накладными расходами», что требует использования полного времени выполнения
  3. Важность выбора классических эталонов: Использование передовых параллелизованных классических алгоритмов в качестве эталонов является предпосылкой справедливой оценки
  4. Статистическая строгость необходима: Достаточное количество экземпляров и статистический анализ критичны для достоверных утверждений о квантовом преимуществе

Ограничения

  1. Ограничения оборудования: Оценка ограничена текущими устройствами NISQ; будущие отказоустойчивые квантовые компьютеры могут изменить выводы
  2. Размер задач: Ограничено масштабом текущего квантового оборудования, невозможно оценить асимптотическое поведение на крупномасштабных задачах
  3. Охват алгоритмов: Оценены только конкретные квантовые алгоритмы, не могут представлять все возможные квантовые методы

Направления будущих исследований

  1. Улучшенные методы измерения времени выполнения: Разработка более точных инструментов для измерения времени выполнения квантовых алгоритмов
  2. Более мощные классические эталоны: Постоянное отслеживание последних достижений в классических алгоритмах
  3. Оценка отказоустойчивых квантовых вычислений: Установление структуры оценки для будущих отказоустойчивых квантовых устройств
  4. Новые метрики оценки: Рассмотрение других практических показателей помимо времени выполнения, таких как энергопотребление и стоимость

Глубокая оценка

Преимущества

  1. Методологическая строгость: Установлена полная и справедливая структура оценки квантовых алгоритмов
  2. Достаточные эксперименты: Охватывают три важных утверждения о квантовом преимуществе, разумный дизайн экспериментов
  3. Надёжная статистика: Использование достаточного объёма выборки, избежание смещения cherry-picking
  4. Высокая практическая ценность: Предоставляет важное методологическое руководство для сообщества квантовых вычислений
  5. Ясное изложение: Логическая структура, точное описание технических деталей

Недостатки

  1. Ограниченный охват: Оценены только три конкретных случая, может быть недостаточно полной
  2. Зависимость от оборудования: Выводы могут измениться с развитием технологии квантового оборудования
  3. Смещение в сторону классических алгоритмов: Возможно наличие предпочтения в оптимизации классических методов
  4. Недостаточный теоретический анализ: Больше внимания экспериментальным результатам, относительно меньше теоретического анализа

Влияние

  1. Академическое влияние: Установление новых стандартов оценки квантового преимущества, возможное влияние на будущие направления исследований
  2. Практическая ценность: Помощь исследователям и инвесторам в более объективной оценке текущего состояния квантовых вычислений
  3. Политическое значение: Предоставление научной основы для инвестиций в квантовые вычисления и разработки политики
  4. Сильная воспроизводимость: Предоставление полного кода и данных, облегчающих проверку и расширение

Применимые сценарии

  1. Оценка квантовых алгоритмов: Предоставление методологии для оценки производительности новых квантовых алгоритмов
  2. Инвестиционные решения: Предоставление объективной технической оценки для инвестиций в квантовые вычисления
  3. Руководство по направлениям исследований: Помощь исследователям в выявлении действительно перспективных квантовых приложений
  4. Образование и обучение: Важный справочный материал для курсов по квантовым вычислениям

Библиография

В данной работе цитируются важные работы в области квантовых вычислений, включая:

  1. Feynman, R.P. - Основополагающие работы по квантовым вычислениям
  2. Shor, P. - Квантовый алгоритм факторизации
  3. Simon, D.R. - Оригинальная статья алгоритма Саймона
  4. Arute, F. et al. - Утверждение Google о квантовом преимуществе
  5. Munoz-Bauza, H. & Lidar, D. - Утверждения о преимуществе квантового отжига

Общая оценка: Это статья с важной академической и практической ценностью, которая посредством строгих экспериментов и анализа предоставляет важные выводы для сообщества квантовых вычислений относительно оценки квантового преимущества. Хотя выводы могут разочаровать некоторых сторонников квантовых вычислений, её научная строгость и методологический вклад имеют позитивное значение для развития этой области.