FCS: Квантовые компьютеры ускоряют решение задач с матроидами
Квантовые компьютеры работают быстрее классических в некоторых задачах, например, при поиске в неупорядоченной базе данных и факторизации простых чисел. Поэтому важно найти другие задачи, которые можно решить с помощью квантовых вычислений.
Ранее не изучались сложность квантовых запросов и квантовые алгоритмы для задач матроида. Стоит исследовать структуры, в которых квантовые вычисления дают преимущество при решении задач матроидов.
Чтобы изучить возможности и ограничения ускорения квантовых вычислений в задачах матроида, исследовательская группа под руководством Лвжоу Ли (Lvzhou LI) опубликовала новое исследование в журнале Frontiers of Computer Science.
Команда изучает, насколько сложно решать некоторые базовые задач с матроидами с помощью квантовых алгоритмов. Они используют метод квантового противника, чтобы определить нижнюю границу сложности таких задач при решении квантовыми алгоритмами.
Для некоторых задач команда получила оптимальные алгоритмы на основе алгоритма Гровера. Это доказывает, что для этих фундаментальных задач с матроидами возможно ускорение с помощью квантовых вычислений.
В будущем ученые планируют исследовать структуру задач с большим ускорением и задачи для эпохи шумного квантования промежуточного масштаба (NISQ), чтобы показать преимущества квантовых компьютеров.
