Задачи комбинаторной оптимизации (COP) находят применение во многих различных областях, таких как логистика, управление цепочками поставок, машинное обучение, дизайн материалов и открытие лекарств, среди прочего, для поиска оптимального решения сложных проблем. Эти проблемы обычно требуют очень больших вычислительных ресурсов с использованием классических компьютеров, и поэтому решение COP с использованием квантовых компьютеров привлекло значительное внимание как со стороны научных кругов, так и со стороны промышленности.
Квантовые компьютеры используют преимущество квантового свойства суперпозиции, используя специализированные кубиты, которые могут существовать в бесконечном, но ограниченном количестве состояний 0 или 1 или любой их комбинации, для быстрого решения больших задач. Однако, когда COP накладывает ограничения, традиционные квантовые алгоритмы, такие как адиабатический квантовый отжиг, с трудом могут получить почти оптимальное решение за время работы квантовых компьютеров.
Недавние достижения в области квантовых технологий привели к созданию таких устройств, как квантовые отжигатели и квантовые устройства вентильного типа, которые обеспечивают подходящие платформы для решения задач COP. К сожалению, они чувствительны к шуму, что ограничивает их применимость для квантовых алгоритмов с низкими вычислительными затратами.
Чтобы решить эту проблему, доцент Тацухико Сираи и профессор Нозому Тогава с факультета компьютерных наук и коммуникационной инженерии Университета Васэда в Японии недавно разработали квантовый алгоритм постобработки с вариационным планированием (pVSQA). Их исследование было опубликовано в журнале IEEE Transactions on Quantum Engineering.
«Два основных метода решения COP с помощью квантовых устройств — это вариационное планирование и постобработка. Наш алгоритм сочетает в себе вариационное планирование с методом постобработки, который преобразует невозможные решения в возможные, что позволяет нам достигать почти оптимальных решений для ограниченных COP на как квантовые отжигатели, так и квантовые компьютеры на основе вентилей», — объясняет доктор Шираи.
Инновационный алгоритм pVSQA использует квантовое устройство для генерации вариационного квантового состояния посредством квантовых вычислений. Затем это используется для создания функции распределения вероятностей, которая состоит из всех возможных и невозможных решений, находящихся в пределах ограничений COP.
Затем метод постобработки преобразует невозможные решения в возможные, оставляя в распределении вероятностей только возможные решения. Затем классический компьютер используется для расчета энергетического ожидания функции стоимости с использованием этого нового распределения вероятностей. Повторение этого расчета приводит к почти оптимальному решению.
Исследователи проанализировали производительность этого алгоритма, используя как симулятор, так и реальные квантовые устройства, такие как квантовый отжиг и квантовое устройство вентильного типа. Эксперименты показали, что pVSQA достигает почти оптимальной производительности в течение заданного времени на симуляторе и превосходит традиционные квантовые алгоритмы без постобработки на реальных квантовых устройствах.
Д-р Шираи сказал: «Для решения различных социальных проблем срочно необходимы радикальные социальные преобразования. Примеры включают создание общества с нейтральным уровнем выбросов углерода для решения проблем изменения климата и реализацию целей устойчивого развития для решения таких проблем, как рост спроса на энергию и продукты питания. дефицит.
«Эффективное решение задач комбинаторной оптимизации лежит в основе достижения этих преобразований. Наш новый метод сыграет значительную роль в реализации этих долгосрочных социальных преобразований».
В заключение, это исследование знаменует собой значительный шаг вперед в использовании квантовых компьютеров для решения COP, что обещает решение сложных реальных проблем в различных областях.