Квантовая оптимизация с практически постоянным числом запусков квантовой схемы

Учёными из Российского квантового центра предложена модификация алгоритма QAOA, в которой — как показали численные эксперименты — число запусков квантовой схемы, необходимое для получения качественного приближённого решения, не растёт с увеличением размера задачи. Результаты опубликованы в журнале Physical Review A.

📔 QAOA используют для приближённого решения сложных задач оптимизации. Обычно параметры квантовой схемы подбираются в гибридном квантово-классическом цикле, а для новых задач может потребоваться новая оптимизация. Это создаёт дополнительные вычислительные затраты и усложняет масштабирование алгоритма.

В качестве альтернативы этому подходу авторы обратились к парадигме fixed-point QAOA (fpQAOA). В ней параметры сначала обучаются на небольших задачах определённого класса, а затем переносятся на более крупные задачи того же класса — без повторной настройки параметров для каждого нового экземпляра.

Метод объединяет сразу три элемента:

🔹 поиск не обязательно точного, но достаточно качественного решения с заданным коэффициентом приближения;

🔹 увеличение числа слоёв QAOA вместе с размером задачи при сохранении всего двух обучаемых параметров, определяющих углы всех слоёв;

🔹 нормировку QUBO-гамильтонианов по норме Фробениуса.

Численное моделирование идеальных квантовых систем размером до 30 кубитов показало неожиданный эффект. Для достижения коэффициента приближения AR = 0,95 медианное число запусков квантовой схемы — shots — необходимых для получения решения заданного качества, не увеличивается с ростом размера задачи, а, напротив, постепенно уменьшается и приближается к практически постоянному значению порядка нескольких запусков.

Такое поведение согласуется с эффективно константной сложностью O(1) по числу запусков квантовой схемы в исследованном диапазоне размеров.

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

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

Пока результат получен для моделирования идеального квантового процессора без аппаратного шума и для систем размером до 30 кубитов, поэтому он не является строгим доказательством асимптотической сложности O(1). Один из следующих важных вопросов — сохранится ли такое поведение для существенно больших систем и на реальных квантовых устройствах.

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

Проще говоря: задача становится больше, квантовая схема — глубже, но число необходимых запусков практически не растёт.

Авторы работы:
🔹 Андрей Чернявский — старший научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Денис Куликов — младший научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Борис Бантыш — старший научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Юрий Богданов — главный научный сотрудник группы «Квантовые информационные технологии» РКЦ;
🔹 Алексей Федоров —руководитель научной группы «Квантовые информационные технологии» РКЦ;
🔹 Евгений Киктенко — младший руководитель группы «Квантовые информационные технологии» РКЦ.