The Setting
A polynomial filter for an integer count must distinguish zero from a prescribed range of positive values, while controlling the cost of its coefficients. For quantum circuit bounds, let denote the total number of qubits, including ancillas.
For a real polynomial and a real weight , the weighted coefficient cost is the real number given by (1), with the sum taken over the nonzero coefficients: (1)✦ For a real number , the natural ceiling is the least nonnegative integer at least .
The Finite Construction
The integer root polynomial , for a nonnegative integer , is the product in (2): (2)✦ The affine polynomial in (3) defines the interval rescaling polynomial for real parameters and . (3)✦
Write for the Chebyshev polynomial of the first kind of degree , where is a nonnegative integer. The Chebyshev approximant for nonnegative integers is the real polynomial defined from (2) and (3) by (4). (4)✦
The Claim
Theorem 1 (Uniform polynomial approximation). Let be real numbers with and . For all sufficiently large natural , there is a real polynomial satisfying (5): (5)✦
Theorem 2 (Approximating polynomial bounds). Let be nonnegative integers and let be real. Suppose , , and . Then the Chebyshev approximant satisfies (6): (6)✦
What Is Checked
The asymptotic assertion concerns real polynomials with the cost (1), real exponents and natural qubit counts; the finite assertion concerns the Chebyshev approximants (4), with natural parameters and nonnegative real weight.
The integer root polynomial equals one at zero and vanishes at the first positive integers.