Что собой представляет оптимизация?

Оптимизация — это процесс поиска наилучшего решения задачи среди множества возможных вариантов с учетом желаемого результата и ограничений.

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

Дополнительные сведения о задачах оптимизации и соответствующую терминологию см. в статье Основные понятия оптимизации.

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

Что такое квантовая оптимизация?

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

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

  1. Во-первых, вы подготовите систему и инициализируйте ее до самого низкого состояния энергии.

  2. Затем вы медленно преобразуете эту систему в более сложную систему, описывающую задачу, которую вы пытаетесь решить. Адиабатическая модель утверждает, что, если такое преобразование выполняется достаточно медленно, то у системы есть достаточное время для адаптации, и она останется в этой конфигурации с самой низкой энергией. После завершения преобразований можно решить задачу.

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

Где можно применять квантовую оптимизацию?

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

  • Найти решение, которое работает быстрее по сравнению с другими методами оптимизации, для конкретного варианта использования и фиксированного качества решения.
  • Найти решение более высокого качества по сравнению с другими методами оптимизации для конкретной задачи и фиксированного интервала времени.
  • Использовать более реалистичную модель по сравнению с другими методами оптимизации за счет расширения задачи для учета большего количества переменных.

Примечание

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

Ниже приведены условия, при выполнении которых квантовая оптимизация проявит высокую эффективность по сравнению с другими классическими алгоритмами оптимизации:

  • Ландшафт оптимизации должен быть неровным, но структурированным. Такие ландшафты часто встречаются в реальных задачах. Для получения дополнительных сведений см. статью Ландшафты оптимизации.
  • Если переменных немного (например, меньше 100), достаточно простейших алгоритмов. Для задач с сотнями переменных квантовая оптимизация позволяет улучшить результат на несколько порядков по сравнению с ранее использованными методами.
  • Параметры задачи, влияющие на выбранную метрику затрат, должны быть представлены с помощью переменных функции затрат. Экспресс-функция затрат как полиномиалы по двоичным переменным для получения проблемы PUBO.

Как алгоритмы квантовой оптимизации решают задачи?

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

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

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

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

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

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

Методы оптимизации Azure Quantum

После создания задачи оптимизации ее можно отправить в один из решателей оптимизации на основе квантовых вычислений в Azure Quantum. Узнайте , как отправлять задания оптимизации.

Azure Quantum предлагает широкий спектр квантовых методов для решения дискретных и комбинаторных задач оптимизации. Тем не менее, невозможно определить, какой решатель будет оптимален для новой задачи оптимизации. Вы можете изучить спецификации каждого целевого объекта для разработки стратегии, а в статье "Какой решатель оптимизации следует использовать?", вы найдете рекомендации по использованию тестовой производительности для поиска подходящего решателя.

Доступны следующие поставщики решений для оптимизации:

  • Microsoft QIO. Набор из нескольких целевых объектов, которые переопределяют задачу оптимизации на основе результатов квантовых исследований, проводившихся десятки лет.
  • 1QBit. Итеративные эвристические алгоритмы, использующие методику поиска для решения задач QUBO.
  • Toshiba SQBM+: компьютер имитируемой квантовой бифуркации Toshiba — это компьютер на модели Изинга на базе графического процессора, который с высокой скоростью решает крупномасштабные задачи комбинаторной оптимизации.

Целевые объекты Microsoft QIO

Поставщик Microsoft QIO включен в каждой рабочей области Azure Quantum. Microsoft QIO предлагает разнообразный набор целевых объектов для каждого типа сценария оптимизации.

  • Параллельная закалка. Связанный классический подход к оптимизации, где копии системы хранятся при разных температурах, автоматизируя повторяющийся нагрев и охлаждение в рамках закалки. Его можно использовать для ускорения классического и (имитированного) квантового отжига, а также для многих других эвристических методов.
  • Имитация отжига. Классический стохастический метод имитации, копирующий медленное охлаждение материала (отжиг) для устранения изъянов. Температура снижается по графику. Температурные переходы позволяют избежать локальных минимумов в области поиска.
  • Отжиг популяции. Так же, как и имитация отжига, имитирует обходчик, который в идеале всегда движется вниз. Отжиг популяции имитирует популяцию обходчиков Метрополиса с постоянным объединением усилий по поиску вокруг приемлемых состояний.
  • Квантовый метод Монте-Карло. Квантовая оптимизация, имитирующая метод квантового отжига с помощью симуляций квантовых методов Монте-Карло. Аналогично температуре в имитации отжига, сила квантового туннелирования со временем сокращается. Эффекты квантового туннелирования позволяют избежать локальных минимумов в области поиска.
  • Субстохастический алгоритм Монте-Карло — это диффузионный метод Монте-Карло на основе адиабатических квантовых вычислений. Он симулирует диффузию популяции блужданий в пространстве поиска с их удалением и дублированием в зависимости от их результатов с учетом функции затрат.
  • Поиск с запретами направлен на соседние конфигурации. Он может принимать перемещения, ведущие к ухудшению, если нет перемещений, ведущих к улучшению, и запрещать выполнять переход к ранее просмотренным решениям

Обратите внимание, что это лишь малая часть доступных методов, и Майкрософт продолжает разрабатывать и добавлять новые решатели в службу Azure Quantum. Дополнительные сведения см. в списке целевых объектов Microsoft QIO.