В поисках квантового преимущества: что открывает алгебра, профессор Аркадев Чаттопадхьяй

Квантовые компьютеры обещают обрабатывать информацию способами, недоступными классическим компьютерам. Но где именно следует искать это преимущество и как определить, когда оно невозможно? Мы опишем математический поиск «убежищ» квантового преимущества. Мы начнем с простых моделей, в которых были открыты некоторые из первых квантовых алгоритмов, а затем перейдем к более богатому миру коммуникации, где разделенные наблюдатели должны объединять частичную информацию о системе. Попутно алгебраические меры будут играть, что несколько неожиданно, роль детектора: иногда показывая, что квантовое ускорение не может быть слишком большим, а иногда указывая на места, где может находиться квантовое преимущество. Доклад предназначен для широкой научной аудитории и не предполагает каких-либо специальных знаний. Акцент будет сделан на основных идеях, а не на технических деталях.