So I am asked to solve this question which says the following...

If I have a quantum computer which can make $1000^{10}$ numeric operations (addition and multiplication) per second, I am asked to estimate the time it takes a quantum computer to evaluate the determinant of a matrix of size $(50,50)$ by iterated cofactor expansion.

Some estimation steps I am apparently supposed to aim for here is, the number of operations is greater than $50!$, and $50!>10^{50}$ where $10^{50}=\sqrt{Googol}$.

I am also told that

$1$ $ns$= $1$ $nanosecond$ = $10^{-9}$

$1$ $\mu s$= $1$ $microsecond$ = $10^{-6}$

$1$ $ms$= $1$ $millisecond$ = $10^{-3}$

$1$ $Day$ $< 10^5$ $seconds$

$1$ $Year$ $< 10^8$ $seconds$

$Age$ $of$ $the$ $universe$: $<15 \cdot 10^9 < 10^{11}$ $years$

My approach was that I am already given the rate of calculations. It's $1000^{10}$ calculations per second. So I just need the number of calculations required. Then I can just multiply the two numbers to get the amount of time required.

The problem is though I can't figure out the number of calculations required. My assumption was to just use $50!$ which is close to $10^{50}$ or $\sqrt{Googol}$ but I don't think that's right since I have to account for all the multiplication of the cofactors of each minor and then all the additions.

How would I go about finding the number of calculations required for a $50$ X $50$ matrix?


In fact you are right. To calculate the determinant of a $50\times 50$ matrix directly, would require more than $50!$ operations, and $50! \approx 3\times 10^{64}$. Thus, using the computer that performs $1000^{10} = 10^{30}$ operations per second, it would take approximately $3\times 10^{34}$ seconds $\approx 10^{27}$ years.

Thus, it would require more than $10^{17}$ times the age of the universe! For more, see page 269, Algebra: A Modern Introduction by David Poole. Hope it helps.

  • $\begingroup$ That's absolutely mind boggling. Thanks a lot! $\endgroup$ – Future Math person Feb 17 '17 at 10:19
  • $\begingroup$ @SubhashisChakraborty (+1) to you! $\endgroup$ – user371838 Feb 17 '17 at 10:22

So to calculate the determinant of an $n \times n$ matrix using cofactor expansion you expand along a row or column, lets say a row. So for each n terms you multiply by the determinant of a $(n-1)\times (n-1)$ matrix. Then you add or subtract all these terms. So an $n\times n$ matrix requires a number of calculations equal to $n\times f(n-1)+n+(n-1)$ where $f(n)$ is the number of calculations required for an $n\times n$ matrix. The $n\times f(n-1)+n$ comes from multiplying n terms by the determinant of a $(n-1)\times (n-1)$ matrix, then n-1 comes from the adding or subtracting of their terms. So $f(n)= n\cdot f(n-1)+ 2n -1$ now we have the number of calculations in terms of a recursive function, but this can be simplified further with the upper incomplete gamma function and be written as $f(n) = e\Gamma(n+1,1)-2$. This works out to be approximately $8\times 10^{64}$ calculations which would take $2.5\cdot10^{27}$ years. This in fact is longer then the current age of the universe.


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.