[GQSP] Optimally scaling polynomial approximations

[anurudhp]

Context: P is a QSP polynomial if $|P(e^{i\theta})| \le 1$ for every $\theta \in [0, 2\pi)$.

When computing polynomial approximations for functions (that have infinite series), the polynomials may end up having max abs. value on the complex unit circle larger than 1, even if the actual function's absolute value is always at most 1 on the unit circle.

Current fix (#851) evaluate polynomial on (2**17 ~= 1.3e5) uniformly spaced points on the complex unit circle to compute the maximum absolute value, and scale down P by that.

Issues:

• Improve efficiency (if possible) - current method uses FFT, so is O(N log N) to evaluate N points.
• Correctness - value returned by current method can be smaller than the true maximum.

If anyone has ideas for correct and more efficient ways to compute the optimal scaling, please do share!

cc @tanujkhattar @skushnir123 @NoureldinYosri @ncrubin

[NoureldinYosri]

how large is the degree of the polynomial?

[anurudhp]

The current simulation tests use up to ~ 300. We would ideally want to test it on degrees upto 1e7.