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?
$\begingroup$
$\endgroup$
14
-
1$\begingroup$ 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. $\endgroup$– Adrien SuauJan 10, 2019 at 7:57
-
1$\begingroup$ 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)? $\endgroup$– DaftWullieJan 10, 2019 at 8:07
-
1$\begingroup$ @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. $\endgroup$– Pablo LiManniJan 10, 2019 at 8:29
-
4$\begingroup$ @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$ $\endgroup$– glS ♦Jan 10, 2019 at 10:20
-
1$\begingroup$ @PabloLiManni regarding the question, I don't know about the general case, but if the matrix is unitary and implemented as a gate, then this is what the quantum phase estimation algorithm does $\endgroup$– glS ♦Jan 10, 2019 at 10:22
|
Show 9 more comments