1767069696
2025-12-29 20:37:00
Задачи комбинаторной оптимизации, которые включают поиск лучшего решения из огромного числа возможностей, представляют собой серьезную проблему как для классических, так и для новых квантовых компьютеров. Гильермо Прейссер, Конор Мак Кивер и Майкл Любаш, все из Quantinuum, теперь демонстрируют новый подход с использованием вариационных методов, основанных на состояниях продукта и матричного продукта. В их работе представлены алгоритмы, основанные на методе итерированного локального поиска, эффективно использующие случайность для повышения производительности при решении сложных задач, и сравниваются эти методы с задачами максимального сокращения, включающими до 50 000 переменных. Результаты показывают, что эти новые алгоритмы превосходят существующие классические и вариационные методы, что представляет собой существенный прогресс в решении сложных вычислительных задач оптимизации.
Исследование впервые разработало метод, который сочетает в себе вариационную минимизацию энергии по отношению к гамильтониану квантового отжига и внедряет этот подход в структуру итерированного локального поиска. В результате были созданы квантовые алгоритмы ILS, которые исследователи протестировали на задачах максимального сечения, включающих до 50 000 переменных, продемонстрировав превосходную производительность по сравнению с традиционными методами, классическими ILS и другими вариационными квантовыми решателями. Команда разработала параллельную альтернативу QiILS, названную квантовым итеративным глобальным поиском, которая использует обновления глобального градиента для обеспечения эффективного распараллеливания. Эксперименты с использованием параллельных вычислений на базе графического процессора показали, что этот подход обеспечивает время выполнения, практически не зависящее от размера задачи, обеспечивая значительное ускорение для больших экземпляров. Производительность оценивалась с использованием коэффициента аппроксимации, меры качества решения.
QiILS превосходит алгоритмы при решении задач MaxCut
Ученые добились значительных успехов в решении сложных задач комбинаторной оптимизации, используя новые вариационные методы, основанные на анзацах состояния продукта и матричных состояниях продукта. Исследовательская группа разработала алгоритмы, основанные на метаэвристике итерированного локального поиска, демонстрирующие улучшенную производительность при решении задач максимального разреза с числом до 50 000 переменных. Эксперименты показывают, что эти новые подходы превосходят традиционные методы, классический итерационный локальный поиск и другие вариационные решатели. Сравнение производительности на эталонном графике показало, что разработанный алгоритм стабильно достигает превосходных результатов. Команда измеряла производительность с помощью коэффициента аппроксимации — показателя оценки качества решения.
Вариационные алгоритмы превосходно справляются с задачами максимального разреза
В этом исследовании представлены новые вариационные методы для решения сложных задач комбинаторной оптимизации, в частности, использование методов состояния продукта и матричного состояния продукта в рамках итерируемой локальной структуры поиска. Объединив эти подходы, ученые разработали алгоритмы, которые явно превосходят традиционные методы и классический локальный поиск при тестировании на задачах максимального разреза, включающих до 50 000 переменных. Команда исследовала влияние ключевых параметров на производительность алгоритма и обнаружила, что тщательный выбор этих параметров может максимизировать скорость улучшения. Исследование подчеркивает потенциал сочетания ограниченной квантовой запутанности со случайностью для эффективного перемещения в пространстве решений сложных задач оптимизации.
#Вариационные #состояния #продукта #обеспечивают #превосходную #оптимизацию #задачах #переменными
Читайте также
