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