I would like to know if exist a quantum algorithm tailored to compute the QR decomposition and SVD of a matrix? Pointers to relevant papers will be very appreciated.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Does this help: Quantum circuits synthesis using Householdertransformations...? $\endgroup$ – draks ... Apr 27 '20 at 9:36
-
$\begingroup$ I don't think so, I am afraid because their algorithm uses classical QR as the first step, but they aren't proposing a quantum algorithm to perform QR decomposition. $\endgroup$ – user3116936 May 1 '20 at 1:49
-
$\begingroup$ Hmm, ok right. How do you think to store the input $A$ and output $Q$ and $R$? BTW: Householder trafo is mentioned on the Grover' search Wikipage... $\endgroup$ – draks ... May 1 '20 at 22:09
Add a comment
|
$\begingroup$
$\endgroup$
1
I could find a few research papers with the potential application of quantum algorithms for Singular Value Decomposition and QR decomposition.
Singular Value Decomposition: Singular Value Decomposition (SVD) is one of the most useful techniques for analyzing data in linear algebra. SVD decomposes a rectangular real or complex matrix into two orthogonal matrices and one diagonal matrix. The following research paper proposes a Quantum-SVD algorithm that interpolates the non-uniform angles in the Fourier domain. This Quantum-SVD algorithm is a fundamentally novel approach for the computation of the Quantum Fourier Transformation (QFT) of non-uniform states.
We can also consider Schmidt decomposition approach for Singular Value Decomposition as per the researches in Quantum Information Theory. It is considered as a Schmidt decomposition has a lot of applications for bipartite state purification.
Quantum SVD based Approximation Algorithm
QR Factorisation
Following research paper proposes a rotation graph to devise elimination orderings in order to achieve QR factorisations. Properties of this graph characterise and identify sufficient sets of rotation planes. The unitary or real orthogonal matrix Q is usually computed in one of three ways: Givens rotations, Householder reflections, or Gram-Schmidt orthogonalization. A Givens-based decomposition is also an essential tool in quantum computing. It is important to determine whether a given set of rotation planes can be used to reduce a matrix to upper triangular form using a minimal number of rotations. One interesting rotation graph is the star graph. A second interesting rotation graph is the chain.
QR Factorisation using Rotation Graphs and Eliminated Orderings
