Skip main navigation

Putting It All Together -Big factors that impact the performance

Watch Rodney Van Meter explain the factors that drive the performance of Shor's algorithm.
3.8
Finally, I want to talk to you a little bit about the performance of Shor’s algorithm. I have a plot here showing the performance of the algorithm compared to the number we want to factor. So the X axis, this is the length of the number we want to factor in bits, so 100 bits, 1000 bits, 10,000, 100,000, it’s a logarithm scale. The vertical axis is the amount of time it takes us to factor and that’s also a logarithmic scale, so here in the middle we have 1 year, down here at the bottom we have 1 second, up at the top is about the age of the universe.
34.9
Right now, there is one line on this, this black line, that’s the number field sieve we’ve been talking about, the classical algorithm that does the factor and you can see that it goes up very steeply. There is one blue point on it, is the current record for how large a number we can factor using the classical algorithm. It’s 768 bits and you can see that from there getting to maybe a 1000 bits might be okay, but going from 1000 bits to 2000 bits means going from maybe a year’s worth of execution time to up to the lifetime of the universe, it’s a big deal.
71.3
Well, we talked earlier about Moore’s law and the advance of classical technology as well, so would that give us a big advantage? Let’s say we used a thousand times as much computing power, how would that look? Well, it would look something like this, curve is the same shape and it doesn’t move very far to the right, so it’s still a big problem even the apparently exponential gain of Moore’s law doesn’t get us a big improvement in the overall performance of the classical factoring algorithm. So, what about Shor’s algorithm? Let’s put Shor’s algorithm on here and compare it. Shor’s algorithm, instead, would look something like this. On this log-log plot, it’s a straight line, it’s a polynomial number.
114.7
Now, you noticed though that I took away the time on the vertical axis, how long does it actually take? That actually depends on a number of factors. You may have heard that a quantum computer can factor a number in seconds, that’s not actually true; the performance actually depends on several factors. The first, of course, is actually the clock speed of the quantum computer itself. How fast can we execute each individual operation? So let’s put in several curves here. Let’s say, you can execute only one operation per second. Up here, factoring a large number can still take thousands of years, thousand times faster than that, it still might take a year.
163.4
At a million times faster than that, 1 million gates per second, now we are down into the seconds and we are down into some really good performance here and the gigahertz might be even faster, so the clock performance actually has a bigger impact on the performance. What about the architecture? The architecture of the computer actually also has a big impact. You can see here three different lines and those represent differences in the internal structure of the quantum computer itself as well as how well we match to the modular exponentiation algorithm to the system itself.
202.3
And so you can see, we go from a line like this to a line like that, to a line like that, so you can see that ultimately we have these three big factors that impact the performance, we have the clock speed of the system itself, our ability to make good algorithm that executes the modular exponentiation part and finally the architecture of the quantum computer itself. So when somebody tells you that a quantum computer can factor a number in seconds, ask them those three questions; how fast is your computer, what’s the architecture of it and what algorithm are you using to actually execute the arithmetic.
Today’s best classical computers and algorithm would require the lifetime of the universe to factor a number that is 2000 bits long. Even the apparently exponential gain of Moore’s law does not get us a big improvement in the overall performance.
Can a quantum computer factor a large number in seconds? Ultimately we have these three big factors that impact the performance, we have the clock speed of the system itself, our ability to make good algorithm that executes the modular exponentiation part and finally the architecture of the quantum computer itself.

まとめ – パフォーマンスに影響を与える大きな要因

今存在している最高の古典コンピュータとアルゴリズムを持ってしても、2000ビット長の数字を因数分解をするためには、宇宙の年齢に相当する時間が必要になります。 ムーアの法則に則って、指数関数的にコンピュータの性能が向上しても、問題の根本的な解決策にはなりえません。
では、量子コンピューターは因数分解を瞬時に解くことができるのでしょうか? システムのパフォーマンスに影響を与える主な要因は、システム自体のクロック速度、冪剰余を実行する優れたアルゴリズムと量子コンピュータのアーキテクチャの3点が主に挙げられます。
This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education