numerical_utils

numerical_utils ¶

cheb_t ¶

cheb_t(L, x)

Generalized Chebyshev polynomial definition.

Chebyshev polynomials are defined as

\[T_L(\theta) = \cos(L\theta)\]

where \(L\) is an integer defining the Chebyshev polynomial (we say "the \(L\) th Chebyshev polynomial). If we replace \(x\) with \(\cos(\theta)\), we get

\[T_L(x) = \cos(L\arccos(x))\]

We can generalize this expression in two different ways: first, we can allow for values of \(x\) that lie outside of \([-1, 1]\) by making use of hyperbolic trig functions; and second, we can allow for non-integer values of \(L\), simply by plugging them in.

See the Wikipedia page for Chebyshev polynomials ⧉ for a derivation of the trig expressions and "Fixed-point quantum search with an optimal number of queries" (arXiv:1409.3305 ⧉) for an example of where these generalized Chebyshev functions can be used.

This function implements the most general form of Chebyshev polynomial as described above.

Parameters:

Name	Type	Description	Default
`L`	`float`	Multiplier inside the trig functions. For a standard Chebyshev polynomial, this is an integer corresponding to the degree of the polynomial, but for this function `L` can be any real number.	required
`x`	`float`	Point at which to evaluate the Chebyshev function. For a standard Chebyshev polynomial, this should satisfy `abs(x) <= 1`, but for this function `x` can be any real number.	required

Returns:

Type	Description
`float`	The output of the generalized Chebyshev polynomial.

closest_octant ¶

closest_octant(phase)

Finds the closest octant.

Given a phase on the unit circle, returns the nearest value on that circle in the set {0/8, 1/8, 2/8, 3/8, 4/8, 5/8, 6/8, 7/8}.

Parameters:

Name	Type	Description	Default
`phase`	`float`	A phase in the interval [0, 1].	required

Returns:

Type	Description
`int`	The closest octant on the unit circle.

Example

If phase = 0.49, the closest octant is 4/8 and the functions returns 4.

discretized_prob_distribution ¶

discretized_prob_distribution(input_list, bit_precision)

Discretized a probability distrubution.

Given a list of n probabilities, return a list of integers corresponding to the number of "boxes" of weights value_per_block.

Parameters:

Name	Type	Description	Default
`input_list`	`List[float]`	Probability distribution.	required
`bit_precision`	`int`	Number of bits used to represent items in probability distribution.	required

Returns:

Type	Description
`List(int)`	Discretized probability distribution.

Note

Might have smarter way of doing this. The idea is to ensure that the final discretized probability distribution is still normalized by adjusting the total number of boxes. This adjustment is done by adding or removing one box to the histogram where the rounding error was the worst. This means that the adjustment is going to increase the error on that specific probability. The error from rounding is usually \(\pm\frac{2^{-b}}{n}\) (where \(b\) is the number of bits of precision and \(n\) is the number of boxes), but on that probability it's going to be:

Rounding error for all but one probability: \(-\frac{2^{-b}}{2n}\) < (val - rounded) < \(\frac{2^{-b}}{2n}\)

Rounding error for the adjusted one: \(-\frac{2^{-b}}{n}\) < (val - rounded) < \(-\frac{2^{-b}}{2n}\) OR \(\frac{2^{-b}}{2n}\) < (val - rounded) < \(\frac{2^{-b}}{n}\)