6

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?

Pablo LiManni
  • 301
  • 1
  • 8
  • 1
    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. – Adrien Suau Jan 10 '19 at 07:57
  • 1
    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 '19 at 08: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 '19 at 08:28
  • 1
    @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 '19 at 08:29
  • @PabloLiManni I don't know how it is called, I don't even know if it has a specific name. Maybe an extension of the definition of eigenvalues, but I doubt it. – Adrien Suau Jan 10 '19 at 08:39
  • 4
    @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 '19 at 10:20
  • 1
    @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 – glS Jan 10 '19 at 10:22
  • @gIS: no it can have least-squares solutions. E is the energy of a molecule from the Schroedinger equation and M represents a basis set expansion in Gaussian orbitals. So we just want an approximation to E, not an exact E. – Pablo LiManni Jan 10 '19 at 10:26
  • @gIS: My matrix is NOT unitary, so I indeed would like the general case. – Pablo LiManni Jan 10 '19 at 12:23
  • @MarkS: since I have never defined "n", you can make N and n be related however you want. – Pablo LiManni Oct 06 '19 at 01:53
  • Hello: Since it's been almost a year, I thought I might see if anyone knows the answer? Now that it's been so many months being unanswered, I guess an answer would earn the author a badge :) – Pablo LiManni Oct 06 '19 at 01:54
  • @MarkS, for a 100x100 matrix, how many qubits and gates do you need to find the eigenvalues up to a precision of $\pm \epsilon$? – Pablo LiManni Oct 06 '19 at 02:24
  • @MarkS: The question asks about NxN, not 100x100. The 100x100 is just an example to try to illustrate, that we don't need to know how N relates to n. We can make N=10^9. Now the question is how many qubits do we need for a 10^9 x 10^9 matrix? The question has an answer, and it does not need any more information, as far as I can see. – Pablo LiManni Oct 06 '19 at 02:46
  • Just touch the question to move it to the front page. Just edit it to say this is what I think, this is the approach that I’m wondering might work. Say $N=4$ or $N=100$ as a toy example. Apart from @gIS answer it seems like you want to drive a sports car in the city. Otherwise in general the number of qubits is about the log of N. – Mark Spinelli Oct 06 '19 at 03:09

0 Answers0