О сравнительной сложности квантовых и классических бинарных программ

В работе дается определение квантовой бинарной программы. Рассматривается известная булева функция $\operatorname{MOD}_p$. Доказывается, что любая детерминированная бинарная программа и вероятностная уровневая стабильная бинарная программа, $(1/2+\varepsilon)$-вычисляющая функцию $\operatorname{MOD}_p$, имеют ширину, не меньшую $p$. Строится стабильная квантовая бинарная программа ширины $O(\log p)$, которая вычисляет функцию $\operatorname{MOD}_p$ с односторонней ошибкой $\varepsilon>0$.