# How many qubits and how many gates, are required for finding the eigenvalues of a matrix?

Say I have an $$N \times N$$ matrix and I want to know the eigenvalues to a precision of $$\pm \epsilon$$. How many qubits and how many gates do I need?

• Hi Pablo! I guess you wanted to write "singular values" and not "eigenvalues" as eigenvalues are only defined for square matrices. I will not edit your question by myself, I think it is better that you edit it in order to add precisions. – Nelimee Jan 10 at 7:57
• How is the matrix specified (e.g. are you given the matrix elements, or perhaps some oracle that implements some extension of the matrix)? Do you know any properties (e.g. is it sparse)? – DaftWullie Jan 10 at 8:07
• @Nelimee: what is E called in the equation Mv = Ev, where v is a vector and M is a matrix but M is not square? – Pablo LiManni Jan 10 at 8:28
• @DaftWullie: let's say the elements of the matrix are known on a classical computer. Let's say it is a completely dense matrix. Let's say we do not know any other properties. – Pablo LiManni Jan 10 at 8:29
• @PabloLiManni if $E$ is a scalar, that equation cannot be satisfied unless $M$ is square. You can see it easily because if $M$ is $n\times m$, then $v$ must have length $m$ for the LHS to make sense, but then $Mv$ has length $n$, which is in contradiction with the $v$ on the right still having length $m$ – glS Jan 10 at 10:20