Неасимптотический анализ времени выполнения квантовых выпуклых алгоритмов оптимизации — Дэвид Гросс

Доклад, записанный на семинаре EQUIPTNT 6/7 октября 2025 г. в Мюнхене

▶ Тема: «Это звучало как хорошая идея» — Неасимптотический анализ времени выполнения квантовых алгоритмов выпуклой оптимизации
▶ Докладчик: Дэвид Гросс (Кёльнский университет)
▶ Аннотация:
Для каких практических задач был бы полезен масштабируемый квантовый компьютер? Это сложный вопрос, поскольку оборудование, способное выполнять реальные бенчмарки, отсутствует, а теоретические работы обычно содержат только асимптотические утверждения. В этом докладе я расскажу о неасимптотическом анализе квантовых алгоритмов выпуклой оптимизации. Основное внимание будет уделено предложению Брандао, Франсы и Куэнга по релаксации SDP для задач QUBO. Оно показалось особенно привлекательным: SDP кажутся естественным дополнением к квантовым методам; Алгоритм, ориентированный на комбинаторные задачи, включает этап округления, который компенсирует невыгодную точность квантовых решателей SDP; и предложение сопровождалось строгой асимптотической оценкой времени выполнения. После оптимизации их предложения по производительности на реалистичных примерах мы приступили к оценке наименьшего размера задачи, для которого проявляется доказанное асимптотическое преимущество. Чтобы узнать результаты, приходите на доклад! (Или загляните на arXiv:2502.15426).

▶ О семинаре EQUIPTNT
Тема семинара — последние разработки на стыке квантовых вычислений, теории сложности и обработки информации. ▶ Сайт семинара: https://www.math.cit.tum.de/math/pers...

MCQST
▶ Сайт: https://www.mcqst.de
▶ LinkedIn:   / mcqst