Квантовая оптимизация с практически постоянным числом запусков квантовой схемыУчёными из Российского квантового центра
предложена модификация алгоритма QAOA, в которой — как показали численные эксперименты — число запусков квантовой схемы, необходимое для получения качественного приближённого решения, не растёт с увеличением размера задачи. Результаты опубликованы в журнале
Physical Review A.
📔
QAOA используют для приближённого решения сложных задач оптимизации. Обычно параметры квантовой схемы подбираются в гибридном квантово-классическом цикле, а для новых задач может потребоваться новая оптимизация. Это создаёт дополнительные вычислительные затраты и усложняет масштабирование алгоритма.
В качестве альтернативы этому подходу авторы обратились к парадигме fixed-point QAOA (fpQAOA). В ней параметры сначала обучаются на небольших задачах определённого класса, а затем переносятся на более крупные задачи того же класса — без повторной настройки параметров для каждого нового экземпляра.
Метод объединяет сразу три элемента:
🔹 поиск не обязательно точного, но достаточно качественного решения с заданным коэффициентом приближения;
🔹 увеличение числа слоёв QAOA вместе с размером задачи при сохранении всего
двух обучаемых параметров, определяющих углы всех слоёв;
🔹 нормировку QUBO-гамильтонианов по норме Фробениуса.
Численное моделирование идеальных квантовых систем размером до
30 кубитов показало неожиданный эффект. Для достижения коэффициента приближения
AR = 0,95 медианное число запусков квантовой схемы —
shots — необходимых для получения решения заданного качества,
не увеличивается с ростом размера задачи, а, напротив, постепенно уменьшается и приближается к практически постоянному значению порядка нескольких запусков.Такое поведение согласуется с
эффективно константной сложностью O(1) по числу запусков квантовой схемы в исследованном диапазоне размеров.
При этом сама квантовая схема становится глубже с ростом задачи: число слоёв QAOA увеличивается линейно с её размером. Поэтому речь не идёт о константной сложности всего вычисления. Однако один из важных ресурсов алгоритма — число повторных запусков квантовой схемы — практически перестаёт зависеть от размера задачи.
Особенно важно, что эффект возникает именно благодаря
совместной работе всех трёх элементов подхода. В численных тестах исключение любого из них приводило к тому, что необходимое число запусков снова начинало быстро расти.
Пока результат получен для моделирования идеального квантового процессора без аппаратного шума и для систем размером до 30 кубитов, поэтому он не является строгим доказательством асимптотической сложности O(1). Один из следующих важных вопросов — сохранится ли такое поведение для существенно больших систем и на реальных квантовых устройствах.
Тем не менее работа показывает перспективный путь к более масштабируемой квантовой оптимизации:
без необходимости заново настраивать параметры алгоритма для каждого нового экземпляра задачи и с практически не растущими затратами по числу квантовых запусков.Проще говоря:
задача становится больше, квантовая схема — глубже, но число необходимых запусков практически не растёт.Авторы работы:🔹 Андрей Чернявский — старший научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Денис Куликов — младший научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Борис Бантыш — старший научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Юрий Богданов — главный научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Алексей Федоров —руководитель научной группы «Квантовые информационные технологии» РКЦ;
🔹 Евгений Киктенко — младший руководитель группы «Квантовые информационные технологии» РКЦ.
