Строгая квантовая основа для бинарной оптимизации с ограничениями-неравенствами и многокритериальной оптимизацией

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

• ID статьи: 2510.13983
• Название: A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization
• Авторы: Sebastian Egginger, Kristina Kirova, Sonja Bruckner, Stefan Hillmich, Richard Kueng
• Классификация: quant-ph (квантовая физика)
• Дата публикации: октябрь 2025
• Ссылка на статью: https://arxiv.org/abs/2510.13983

Аннотация

Кодирование задач комбинаторной оптимизации в физически значимые гамильтонианы с управляемым энергетическим ландшафтом составляет основу квантовой оптимизации. Многочисленные исследования изучали эффективное кодирование класса задач квадратичной безусловной бинарной оптимизации (QUBO). Однако многие реальные задачи содержат ограничения, и обработка ограничений-равенств, особенно ограничений-неравенств, на квантовых компьютерах остаётся серьёзной проблемой. В данной статье доказано, что включение ограничений-неравенств эквивалентно решению задачи многокритериальной оптимизации. Это понимание вдохновило разработку основы многокритериальной квантовой аппроксимации (MOQA), которая аппроксимирует максимум через p-норму меньшей степени и обеспечивает строгие гарантии производительности. MOQA работает непосредственно на уровне гамильтониана, совместима, но не ограничена решателями основного состояния, такими как квантовый адиабатический отжиг, квантовый приближённый алгоритм оптимизации (QAOA) или эволюция в мнимом времени. Кроме того, она не ограничена квадратичными функциями.

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

Определение проблемы

Основная проблема, которую решает данная статья, заключается в эффективной обработке бинарных задач оптимизации с ограничениями-неравенствами на квантовых компьютерах. Традиционные методы квантовой оптимизации в основном ориентированы на безусловные задачи QUBO, однако реальные задачи оптимизации часто содержат сложные ограничения.

Важность проблемы

1. Потребности практического применения: Многие важные задачи в финансах, логистике, управлении энергией могут быть переформулированы как задачи бинарной оптимизации, но обычно содержат ограничения-равенства f(b)=0 или ограничения-неравенства g(b)≥0
2. Потенциал квантового преимущества: Бинарная оптимизация считается одной из наиболее перспективных областей, где квантовые алгоритмы могут оказать значительное практическое влияние

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

1. Обработка ограничений-равенств: Может быть обработана методами регуляризации, то есть h(b) → h(b) + γ(f(b))², но требует надлежащего выбора параметра регуляризации γ
2. Сложность ограничений-неравенств: Традиционные стратегии регуляризации неприменимы к ограничениям-неравенствам g(b)≥0
3. Недостатки существующих решений:
   • Требуют дополнительных переменных релаксации и вспомогательных кубитов
   • Отсутствуют строгие теоретические гарантии
   • Применимы только к конкретным постановкам задач
   • Требуют дополнительных классических/квантовых подпрограмм

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

В данной статье предложена первая строгая основа для обработки ограничений-неравенств без использования вспомогательных систем, дополнительных переменных оптимизации, не ограниченная конкретными задачами или решателями, с обеспечением гарантий сходимости.

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

1. Теоретический прорыв: Доказано, что включение ограничений-неравенств эквивалентно решению задачи многокритериальной оптимизации
2. Основа MOQA: Предложена основа многокритериальной квантовой аппроксимации, реализующая обработку ограничений через аппроксимацию p-нормой
3. Строгие теоретические гарантии: Предоставлены строгие математические доказательства Предложения 1 и Теоремы 1
4. Универсальная совместимость: Основа совместима с различными квантовыми решателями, включая QAOA, адиабатический отжиг и другие
5. Экспериментальная верификация: Метод проверен на 10000 случайных примерах

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

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

Рассмотрим задачу многокритериальной бинарной оптимизации:

минимизировать h_max(b) = max{h₁(b), ..., h_M(b)}
b∈{0,1}ⁿ

где каждая h_m(b) представляет целевую функцию, которая может быть переформулирована как k-локальный гамильтониан Ĥ_m на n кубитах.

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

Для ограничения-неравенства g(b)≥0 преобразование выполняется следующим образом:

1. Неаналитическая регуляризация: h(b) → h(b) + γmax{0, -g(b)}
2. Переформулировка многокритериальности: Переформулировка в максимум двух благоприятных функций стоимости
   • h₁(b) = h(b)
   • h₂(b) = h(b) - γg(b)

Архитектура основы MOQA

Основная аппроксимация: Аппроксимация максимума средним значением p-й степени

h_max(b)ᵖ = max{h₁ᵖ(b), ..., h_Mᵖ(b)} ≈ Σᴹₘ₌₁ h_mᵖ(b)

На уровне гамильтониана:

Ĥ^(p) = (1/M) Σᴹₘ₌₁ Ĥ_m^p

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

1. Теоретическая основа ℓp-нормы

Предложение 1: Для каждого p∈ℕ₊ следующие неравенства сжатия справедливы для всех бинарных векторов b∈{0,1}ⁿ:

M^(-1/p)(h^(p)(b))^(1/p) ≤ h_max(b) ≤ (h^(p)(b))^(1/p)

2. Теория спектрального зазора

Теорема 1: Пусть Ĥ_max — гамильтониан, соответствующий максимуму M целевых функций, пространство основного состояния невырождено, r(Ĥ_max) — его отношение спектрального зазора. Выбор уровня аппроксимации:

p > log(M)/log(r(Ĥ_max) + 1)

гарантирует, что Ĥ^(p) имеет точно такое же пространство основного состояния, что и Ĥ_max, и больший коэффициент спектрального зазора.

3. Анализ локальности и количества членов

• Исходный гамильтониан: k-локальный, не более T≤nᵏ членов
• Приближённый гамильтониан: pk-локальный, не более n^(kp) членов
• Случай QUBO: Рост с 2-локального на 2p-локальный

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

Набор данных

• Размер задачи: Задачи QUBO с n=4 до n=20 переменных
• Тип ограничений: Одно линейное ограничение-неравенство aᵀb≥0
• Количество примеров: 10000 случайных примеров
• Способ генерации: Элементы векторов и матриц независимо выбраны из стандартного нормального распределения

Метрики оценки

1. Ошибка абсолютного различия (ε):

ε = (1/Ns) Σᵢ₌₁ᴺˢ {1 если h_max^(i)(b*_(p)^(i)) ≠ h_max^(i)(b*_max^(i)), 0 иначе}

2. Ошибка относительного различия (δ):

δ = (1/Ns) Σᵢ₌₁ᴺˢ [h_max(b*_(p)^(i)) - h_max(b*_max^(i))]/h_max(b*_max^(i))

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

• Уровень аппроксимации: Тестирование p∈{5,10,20}
• Параметр регуляризации: γ∈{6,120}
• Анализ спектрального зазора: Примеры сгруппированы по отношению спектрального зазора для анализа

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

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

1. Качество аппроксимации растёт с p: На Рисунке 1 показано, что с увеличением p качество аппроксимации глобально улучшается по всему энергетическому ландшафту оптимизации
2. Производительность относительной ошибки: Для малых значений p относительное различие δ<1%, что указывает на то, что минимум, найденный MOQA, также является хорошим решением для Ĥ_max
3. Удовлетворение ограничений: Во всех 10000 примерах решения для всех значений p не нарушали ограничения

Анализ спектрального зазора

На Рисунке 2 показана связь между ошибкой аппроксимации и отношением спектрального зазора:

• Пороговый эффект: Когда отношение спектрального зазора достигает теоретического порога, абсолютное различие ε становится равным 0
• Ранняя сходимость: На практике ошибка становится равной 0 до теоретического порога
• Влияние параметров: Малые p, малые n, большие M уменьшают расстояние между эмпирической и теоретической нулевой точкой

Анализ эффектов масштаба

• Влияние размера задачи: С увеличением n вероятность нахождения глобального оптимума для малых значений p снижается
• Стабильность относительной производительности: Различия между разными масштабами уменьшаются, что указывает на возможность расширения метода на n>20
• Практическая верификация: Даже ниже теоретического порога MOQA производит надёжные результаты

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

Основы квантовой оптимизации

1. Адиабатическая квантовая оптимизация: Подготовка основного состояния гамильтониана задачи путём медленного изменения гамильтониана из простого начального состояния
2. Алгоритм QAOA: Версия Троттеризации адиабатического преобразования, подходящая для устройств NISQ
3. Задачи QUBO: Особенно квантовая обработка задачи MAX-CUT

Методы обработки ограничений

1. Ограничения-равенства: Метод регуляризации h(b) → h(b) + γ(f(b))²
2. Существующие методы для ограничений-неравенств:
   • Метод переменных релаксации (требует вспомогательных кубитов)
   • Метод расширенного лагранжиана
   • Несбалансированная штрафизация
   • Пользовательские функции штрафа
   • Метод квантовой проекции

Преимущества данной работы

По сравнению с существующими методами MOQA обеспечивает:

• Строгую основу без вспомогательных систем
• Теоретические гарантии сходимости
• Совместимость с различными решателями
• Неограниченность конкретными типами задач

Заключение и обсуждение

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

1. Теоретический вклад: Установлена эквивалентность между ограничениями-неравенствами и многокритериальной оптимизацией
2. Практическая основа: MOQA обеспечивает универсальный метод обработки оптимизации с ограничениями
3. Гарантии производительности: Теоретически гарантирует точное восстановление основного состояния при надлежащих условиях
4. Экспериментальная верификация: Численные эксперименты подтверждают теоретические предсказания и практическую эффективность

Ограничения

1. Вырожденные случаи: Для вырожденных оптимальных решений вторая часть теоретических гарантий может быть неприменима
2. Выбор параметров: Требуется предварительное знание отношения спектрального зазора для определения подходящего значения p
3. Ограничения масштаба: Текущие эксперименты проверены только на задачах размером до n=20
4. Сложность гамильтониана: С ростом p локальность и количество членов увеличиваются, что может повлиять на практическую реализацию

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

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

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

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

1. Теоретическая строгость: Предоставлены полные математические доказательства и строгие гарантии производительности
2. Универсальность метода: Не ограничена конкретными решателями или типами задач, имеет широкую применимость
3. Инновационный подход: Идея преобразования задач с ограничениями в многокритериальную оптимизацию новаторская и эффективная
4. Достаточность экспериментов: Практическая эффективность метода проверена на большом количестве случайных примеров

Недостатки

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

Влияние

1. Академическая ценность: Предоставляет новую теоретическую основу и методы для квантовой оптимизации с ограничениями
2. Практический потенциал: Может быть непосредственно применена к различным квантовым алгоритмам оптимизации и реальным задачам
3. Продвижение области: Заполняет важный пробел в обработке ограничений в квантовой оптимизации
4. Воспроизводимость: Предоставлены полный код и детали экспериментов

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

1. Финансовая оптимизация: Оптимизация портфеля и другие задачи финансовой оптимизации с ограничениями
2. Планирование логистики: Оптимизация маршрутов, распределение ресурсов и другие задачи оптимизации с ограничениями
3. Управление энергией: Оптимизация электросетей, задачи планирования
4. Комбинаторная оптимизация: Задача о рюкзаке, покрытие вершин, задача коммивояжёра и другие

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

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

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