Квантовые схемы научились вычислять функции Parity и Majority. Для этого им нужно много копий входных данных. Такой результат получили Дэниел Грайер и его коллеги.
Грайер был аспирантом Скотта Ааронсона. Сейчас он профессор в UCSD. Работа заняла четверть века.
Проблема Parity не входила в класс QAC0. Это был центральный открытый вопрос. Теперь мы понимаем, почему его так трудно решить.
Результат опубликовали на arXiv. Это большой шаг в квантовой теории сложности. Он меняет понимание возможностей квантовых схем.
