Том 11, серия 1, номер 4, 2004 г., Стр. 3-19

УДК 519.681.4
М. Н. Вялый
Приближенное вычисление весовой функции линейного двоичного кода

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

Вялый М. Н. ¹
1. ВЦ им. А. А. Дородницына РАН,
Вавилова, 40, 119991 Москва, Россия
е-mail: vyalyi@mccme.ru

Статья поступила 29 июня 2004 г.