Комбинаторная оптимизация пронизывает науку и инженерию: от планирования маршрутов до распределения ресурсов. Многие такие задачи эквивалентны поиску основного состояния модели Изинга, что относится к классу NP-трудных проблем. Классические эвристики, такие как имитационный отжиг, часто застревают в локальных минимумах из-за изрезанного энергетического ландшафта. Квантовые подходы, в частности QAOA, обещают ускорение, но страдают от проблем обучаемости и ограниченной глубины схем на современном оборудовании. Данная работа стоит в ряду недавних попыток использовать шумные промежуточные квантовые процессоры (NISQ) для практических задач: соседние исследования изучают квантовые алгоритмы, коррекцию ошибок и квантовую информацию. Отличие данной работы — в конкретной гибридной схеме, где квантовая часть лишь предлагает «прыжки» между бассейнами, а вся тонкая оптимизация остаётся классической.
Алгоритм Qjump работает итеративно. Имея текущее решение (битовую строку), квантовая схема генерирует множество кандидатов, «перепрыгивая» в соседние энергетические бассейны. Схема состоит из слоя кодирования, L слоёв операторов стоимости и смешивания (вдохновлённых QAOA) и измерений. Параметры схемы не оптимизируются вариационно, а берутся из предварительно рассчитанных значений для глубокого QAOA, что исключает проблему бесплодных плато. После квантового сэмплирования классический компьютер выполняет локальный поиск (жадный спуск) для каждого кандидата и выбирает лучшее решение. Эксперименты проводились на 104-кубитном сверхпроводящем процессоре с медианной точностью двухкубитных гейтов 99,5%. Для сравнения использовался высокооптимизированный классический имитационный отжиг (SA) на одноядерном CPU.
На 20 специально отобранных сложных экземплярах задачи Изинга со 104 кубитами Qjump в среднем находил глобальный минимум в 2,23 раза чаще, чем SA, за фиксированное время. При этом квантовый сэмплер демонстрировал более высокую вероятность попадания в область глобального минимума по сравнению с классическим случайным сэмплированием с той же долей перевёрнутых битов. На основе предположений о будущем квантовом оборудовании (частота сэмплирования 0,4 МГц, быстрое управление через FPGA) было оценено время до решения (TTS): Qjump превзошёл SA на одноядерном CPU в 2,34 раза. Для меньших систем (60 и 84 кубита) преимущество было меньше (0,98 и 1,56 раза соответственно), что указывает на улучшение с ростом размера задачи. QAOA с локальным поиском оказался почти неэффективным для этих задач.
Работа показывает, что гибридные схемы, где квантовый процессор используется только для «прыжков» по ландшафту, а классический — для точной оптимизации, могут быть практичным путём к квантовому преимуществу на NISQ-устройствах. В отличие от соседних работ, фокусирующихся на чисто квантовых алгоритмах или коррекции ошибок, здесь предложен конкретный механизм разделения труда, снижающий требования к глубине схем и качеству кубитов. Это расширяет применимость существующих квантовых процессоров для задач оптимизации уже сегодня.
Естественный следующий шаг — масштабирование на тысячи кубитов и улучшение метрик кубитов. Также интересно исследовать оптимальные параметры сэмплера и структуру схемы, а также влияние шума гейтов и измерений. Потенциально Qjump можно комбинировать с другими классическими эвристиками (табу-поиск, метод ветвей и границ) или использовать как модуль в ансамбле алгоритмов.
Результаты могут повлиять на области, где требуется решение NP-трудных задач: логистика, финансы, материаловедение, машинное обучение. Гибридный подход может быть адаптирован для других квантовых платформ.
Провести эксперименты на системах с тысячами кубитов и улучшенными показателями точности гейтов. Исследовать масштабирование временной сложности Qjump с ростом размера задачи.
В области квантовых вычислений остаётся открытым вопрос, могут ли шумные промежуточные квантовые устройства обеспечить практическое преимущество над классическими алгоритмами для задач оптимизации. Данная работа вносит вклад, демонстрируя конкретный гибридный алгоритм и экспериментальное свидетельство преимущества на 104 кубитах, но строгое доказательство квантового ускорения требует дальнейших исследований.
Этот раздел адресован автору работы и его коллегам. Соседние работы нашёл смысловой поиск по нашему архиву — не по совпадению слов, а по смыслу. Мы не рецензируем: мы показываем поле вокруг.
Что сделано в работе
В работе предложен гибридный квантово-классический алгоритм Qjump, который использует квантовый сэмплер для генерации кандидатов в разных энергетических бассейнах, а классический локальный поиск для спуска. На 104-кубитном процессоре алгоритм чаще находил глобальный минимум, чем классический имитационный отжиг, и показал экстраполированное ускорение в 2.34 раза по времени до решения.
В чём сила
Сильная сторона — конкретная гибридная схема, где квантовая часть отвечает только за «прыжки» между бассейнами, а тонкая оптимизация остаётся классической, что позволяет избежать проблем вариационной оптимизации и использовать фиксированные параметры схемы.
Куда можно двигаться
Что можно попробовать
Работы рядом в нашем архиве
Вокруг этой работы в архиве пусто: ближайший разбор всего на 0.58, при обычных 0.64. Похоже, рядом почти не бурили.
Для отбора сложных экземпляров задачи учёные сгенерировали 4000 случайных конфигураций связей и полей, а затем оставили только 20, на которых классический имитационный отжиг работал хуже всего. Это гарантирует, что сравнение было честным: квантовый алгоритм испытывался на самых трудных случаях.