# Negative power function

### What is negative power function

As a generalization of the quantum linear system problem (QLSP), we consider the following problem: given the access to an invertible matrix $$A$$ and a normalized quantum state $$|b\rangle$$, we want to construct a quantum state

$$
|x\rangle:=\frac{A^{-c}|b\rangle}{|A^{-c}|b\rangle|\_2},
$$

where $$c$$ is a integer larger than 1. 

### The equivalent problem in function approximation

Similarly, the implement boils down to a scalar function $$f(x)=x^{-c}$$. Without loss of generality, we assume the matrix is normalized. We have to find a polynomial with parity approximating $$f(x)$$ over the interval $$D\_{\kappa}:=\[-1,-\kappa]\cup\[-\kappa,1].$$

### Setup parameters

For numerical demonstration, we set $$\kappa = 10$$, $$c=2$$ and scale down the target function by a factor of $$1/(2\kappa^c)$$ so that 

$$
f(x) = \frac{1}{2(\kappa x)^c}, \quad\max\_{x \in D\_\kappa} |f(x)| = \frac{1}{2}.
$$

This improves the numerical stability.

```matlab
kappa = 10;
targ = @(x) 1./x.^2;
% approximate f(x) by a polynomial of degree deg
deg = 150;
parity = 0;
opts.fscale = 1/(2*kappa^2);
```

### Polynomial approximation using convex-optimization-based method

We want to find the best approximation polynomial with degree up to $$d$$ in terms of $$L^{1}$$ norm. To achieve it, we call `cvx_poly_coef`, which solves the optimization problem and outputs the Chebyshev coefficients of the best approximation polynomial.

```matlab
opts.intervals=[1/kappa,1];
opts.objnorm = Inf;
opts.epsil = 0.2;
opts.npts = 400;
opts.isplot = true;

```

Then, simply calling the subroutine yields the coefficients of the approximation polynomial in the Chebyshev basis. As a remark, the solver outputs all coefficients while we have to post-select those of odd order due to the parity constraint.

```matlab
coef_full=cvx_poly_coef(targ, deg, opts);
coef = coef_full(1+parity:2:end);
```

<figure><img src="https://40428858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FznDlSgNqsJLx79OHu47P%2Fuploads%2FFgMxRtoDsewqETVUjWWV%2Fnegative_power_function_polynomial.png?alt=media&#x26;token=61d630aa-424c-470d-bbd8-a2375283b5cd" alt="" width="563"><figcaption><p>Polynomial approximation of the target function</p></figcaption></figure>

<figure><img src="https://40428858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FznDlSgNqsJLx79OHu47P%2Fuploads%2F4mzpyQ2aKWBd9CDxQQWh%2Fnegative_power_function_polynomial_error.png?alt=media&#x26;token=76d68329-871b-45e5-bcb2-f42ef45e43b8" alt="" width="563"><figcaption><p>Polynomial approximation error</p></figcaption></figure>

### Solving the phase factors for QLSP

We use Newton's method for solving phase factors. The parameters of the solver is initiated as follows.

```matlab
% set the parameters of the solver
opts.maxiter = 100;
opts.criteria = 1e-14;
opts.useReal = false;
opts.targetPre = true;
opts.method = 'Newton';
% solve phase factors
[phi_proc,out] = QSP_solver(coef,parity,opts);
```

### Verifying the solution

We verify the solved phase factors by computing the residual error in terms of the $$\ell^\infty$$ norm

$$
\mathrm{residual\_error} = \max\_{k = 1, \cdots, K} |g(x\_k,\Phi^\*) - f\_\mathrm{poly}(x\_k)|.
$$

Using $$500$$ equally spaced points, the residual error is $$6.2172 \times 10^{-15}$$ which attains almost machine precision. We also plot the point-wise error.

```matlab
xlist1 = linspace(-1,-1/kappa,500)';
xlist2 = linspace(1/kappa,1,500)';
xlist = cat(1, xlist1,xlist2);
func = @(x) ChebyCoef2Func(x, coef, parity, true);
targ_value = targ(xlist);
func_value = func(xlist);
QSP_value = QSPGetEntry(xlist, phi_proc, out);
err= norm(QSP_value-func_value,2);
disp('The residual error is');
disp(err);

figure()
plot(xlist,QSP_value-func_value)
xlabel('$$x$$', 'Interpreter', 'latex')
ylabel('$$g(x,\Phi^*)-f_\mathrm{poly}(x)$$', 'Interpreter', 'latex')
print(gcf,'negative_power_function_error.png','-dpng','-r500');
```

<figure><img src="https://40428858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FznDlSgNqsJLx79OHu47P%2Fuploads%2FzUXHGMEmdyeyK6M3mSBG%2Fnegative_power_function_error.png?alt=media&#x26;token=06da7132-bcc4-41dc-b3fe-8e97acd8b187" alt="" width="563"><figcaption><p>The point-wise error of the solved phase factors.</p></figcaption></figure>

### Reference

1. Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019, June). Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In *Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing* (pp. 193-204).
2. Dong, Y., Meng, X., Whaley, K. B., & Lin, L. (2021). Efficient phase-factor evaluation in quantum signal processing. *Physical Review A*, *103*(4), 042419.

<details>

<summary>Output of the code</summary>

```
norm error = 3.55695e-05
max of solution = 0.801961
iter          err
   1  +1.4303e-01 
   2  +1.0329e-02 
   3  +8.1428e-05 
   4  +5.3832e-09 
Stop criteria satisfied.
The residual error is
   3.3761e-14
```

</details>