- Суперполиномиальное квантовое преимущество для задач комбинаторной оптимизации(arXiv)
Автор: Никлас Пирней, Винсент Улич, Фредерик Уайльд, Йенс Эйзерт, Жан-Пьер Зайферт
Аннотация. Комбинаторная оптимизация — область исследований, направленная на решение проблем, которые сильно характерны для множества практических и промышленных контекстов, — была определена как одна из основных потенциальных областей применения квантовых компьютеров в ближайшей перспективе. Однако до сих пор неясно, в какой степени вариационные квантовые алгоритмы действительно могут превзойти классические алгоритмы для задач такого типа. В данной работе, прибегая к вычислительной теории обучения и криптографическим понятиям, мы доказываем, что отказоустойчивые квантовые компьютеры обладают суперполиномиальным преимуществом перед классическими компьютерами в аппроксимации решений задач комбинаторной оптимизации. В частности, основываясь на фундаментальной работе Кернса и Вэлианта, мы конструируем специальные экземпляры задачи целочисленного программирования (которая в своей наиболее общей форме является NP-полной), которую, как мы доказали, трудно аппроксимировать классически, но мы даем эффективный квантовый алгоритм для ее решения. аппроксимировать оптимальное решение этих случаев, тем самым показывая суперполиномиальное квантовое преимущество. Этот результат показывает, что квантовые устройства способны аппроксимировать решения комбинаторной оптимизации за пределами досягаемости классических эффективных алгоритмов.
2. Постановка задач комбинаторной оптимизации для решения задач управления и планирования облачного производства(arXiv)
Автор:М. В. Сарамуд, Э. А. Спирин, Е. П. Талай, И. И. Пикалов
Аннотация: Рассмотрено применение задач комбинаторной оптимизации к решению задач планирования процессов для производств на основе фонда реконфигурируемых производственных ресурсов. Представлены результаты их решения методами смешанного целочисленного программирования.
3.Независимое от предметной области динамическое программирование: универсальный поиск в пространстве состояний для комбинаторной оптимизации(arXiv)
Автор: Рё Куроива, Дж. Кристофер Бек
Аннотация. Для задач комбинаторной оптимизации подходы на основе моделей, такие как смешанно-целочисленное программирование (MIP) и программирование с ограничениями (CP), направлены на разделение моделирования и решения проблемы: «Святой Грааль» декларативной задачи. решение. Мы предлагаем доменно-независимое динамическое программирование (DIDP), новую модельно-ориентированную парадигму, основанную на динамическом программировании (DP). Хотя DP не является новым, обычно он реализуется как метод для решения конкретных задач. Мы предлагаем язык описания динамического программирования (DyPDL), формализм для определения моделей DP, и разрабатываем стоимостно-алгебраический решатель A* для DyPDL (CAASDy), универсальный решатель для DyPDL, использующий поиск в пространстве состояний. Мы формализуем существующие специализированные методы DP и поиска в пространстве состояний для задач комбинаторной оптимизации в виде моделей DP в DyPDL. Используя CAASDy и коммерческие решатели MIP и CP, мы экспериментально сравниваем модели DP с существующими моделями MIP и CP, показывая, что, несмотря на свою зарождающуюся природу, CAASDy превосходит MIP и CP по ряду общих классов задач.
