10
$\begingroup$

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.

$\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
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The second paper is not a quantum algorithm. $\endgroup$ – smapers May 6 '20 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.