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 UU, its inverse UU^\dagger and the controlled reflection operators (2ΠI)(2\Pi-I), (2Π~I)(2\tilde{\Pi}-I). A:=Π~UΠA:=\tilde{\Pi} U\Pi is of our interest and has a singular value decomposition A=kσkϕkψkA=\sum_k \sigma_k |\phi_k \rangle \langle \psi_k|. Singular vector transformation algorithm performs the transformation

kαkψkkαkϕk.\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], this algorithm aims at achieving the singular value transformation of AA for sign function ff, that is f(SV)=kϕkψk.f^{(SV)}=\sum_k |\phi_k\rangle\langle \psi_k|.

In practice, we find an odd polynomial approximation to ff, denoted as fpolyf_{poly}, on the interval Dκ=[1,δ][δ,1]D_{\kappa}=[-1, -\delta]\cup [\delta,1]. By applying the singular value transformation for fpolyf_{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)f(x) on the interval DκD_{\kappa}, where we solves the problem by convex optimization. Here are the parameters set for the subroutine.

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);
Polynomial approximation of the target function
Polynomial approximation error

Set up parameters

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

Solving phase factors by running the solver

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

Verifying the solution

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');
The point-wise error of the solved phase factors.

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.

Output of the code
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

Last updated