# Singular vector transformation

In this example, We introduce the implementation of singular vector transformation.

### What is singular vector transformation

Singular vector transformation implements a matrix that transforms the right singular vector to the corresponding left singular vector. Suppose that we have access to a unitary $$U$$, its inverse $$U^\dagger$$ and the controlled reflection operators $$(2\Pi-I)$$, $$(2\tilde{\Pi}-I)$$. $$A:=\tilde{\Pi} U\Pi$$ is of our interest and has a singular value decomposition $$A=\sum\_k \sigma\_k |\phi\_k \rangle \langle \psi\_k|$$. Singular vector transformation algorithm performs the transformation

$$
\sum\_k \alpha\_k|\psi\_k\rangle  \mapsto \sum\_k \alpha\_k|\phi\_k\rangle.
$$

This algorithm can be used for devising a new method for singular value estimation. It also has many applications, for example, efficient ground state preparation of certain local Hamiltonians.

### The equivalent problem in function approximation

As shown in the proof of Theorem 1 in [\[GSLW\]](#reference), this algorithm aims at achieving the singular value transformation of $$A$$ for sign function $$f$$, that is $$f^{(SV)}=\sum\_k |\phi\_k\rangle\langle \psi\_k|.$$

In practice, we find an odd polynomial approximation to $$f$$, denoted as $$f\_{poly}$$, on the interval $$D\_{\kappa}=\[-1, -\delta]\cup \[\delta,1]$$. By applying the singular value transformation for $$f\_{poly}$$ instead, this algorithm maps the a right singular vector having singular value at least $$\delta$$ to the corresponding left singular vector.

For numerical demonstration, we scale the target function by a factor of 0.8, to improve the numerical stability.

We call a subroutine to find the best odd polynomial approximating $$f(x)$$ on the interval $$D\_{\kappa}$$, where we solves the problem by convex optimization. Here are the parameters set for the subroutine.

```matlab
opts.intervals=[delta,1];
opts.objnorm = Inf;
opts.epsil = 0.1;
opts.npts = 500;
opts.isplot= true;
opts.fscale = 1; % disable further rescaling of f(x)

delta = 0.1;
targ = @(x) 0.8*sign(x);
parity = 1;
% agrees with parity
deg = 251;
coef_full=cvx_poly_coef(targ, deg, opts);
% The solver outputs all Chebyshev coefficients while we have to post-select 
% those of odd order due to the parity constraint.
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%2FtHD5WBFfKcm04h0lIfOO%2Fsingular_vector_transformation_polynomial.png?alt=media&#x26;token=79c3e81a-caab-429e-b86e-eff0d8319bed" alt=""><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%2FqgGrOmOUDHiADB8aGBYC%2Fsingular_vector_transformation_polynomial_error.png?alt=media&#x26;token=4ce5f32e-5c69-46b9-b633-16ccba9533c1" alt=""><figcaption><p>Polynomial approximation error</p></figcaption></figure>

### Set up parameters

```matlab
opts.maxiter = 100;
opts.criteria = 1e-12;
opts.useReal = false;
opts.targetPre = true;
opts.method = 'Newton';
```

### Solving phase factors by running the solver

```matlab
[phi_proc,out] = QSP_solver(coef,parity,opts);
```

### Verifying the solution

```matlab
xlist1 = linspace(-1,-delta,500)';
xlist2 = linspace(delta,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,'singular_vector_transformation_error.png','-dpng','-r500');
```

<figure><img src="https://40428858-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FznDlSgNqsJLx79OHu47P%2Fuploads%2FGz9MbmuCHVTb6gNjFJQH%2Fsingular_vector_transformation_error.png?alt=media&#x26;token=77d47457-73b2-46a4-96a6-8c65e9a336ec" 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 = 6.67183e-08
max of solution = 0.8
iter          err
   1  +4.0710e-01 
   2  +5.8374e-02 
   3  +1.8592e-03 
   4  +1.8744e-06 
   5  +1.7525e-12 
Stop criteria satisfied.
The residual error is
   2.8070e-13
```

</details>