Приближенное вычисление весовой функции линейного двоичного кода

Рассматривается задача приближенного вычисления весовой функции двоичного линейного кода в точках единичной окружности с аддитивной погрешностью $\varepsilon$. Приближения весовых функций линейных двоичных кодов с аддитивной погрешностью возникают при анализе квантовых алгоритмов. Задача точного вычисления значения весовой функции вычислительно трудна. В работе показано, что приближенного вычисления весовой функции с аддитивной погрешностью $2^{n-n^c}$, где $c<1$ – положительная константа, достаточно для точного определения коэффициентов весовой функции. Аналогичные, но более слабые, результаты получены также для задачи приближенного вычисления весовой функции в единственной точке (основной пример – в точке $\omega=e^{i\pi/4}$).