Skip main navigation

Putting It All Together -Summarizing the Algorithm/まとめ – アルゴリズムのまとめ

Putting It All Together -Summarizing the Algorithm/まとめ - アルゴリズムのまとめ
Shor’s algorithm is an amazing accomplishment, isn’t it? But it’s a complex algorithm involving a number of concepts that are probably new to you and it’s a combination of both quantum and classical subroutines. So, let’s take a look back at the overall structure, then we’ll talk about the performance implications of the algorithm. First, we start with the number N that you’d like to factor. Next, pick a random number a less than N. Before going any farther, it’s worth checking the greatest common denominator of a and N. Almost certainly, the gcd will be 1.
If you get very lucky and it’s greater than 1, you have found the factor of N and you are already done, so there is no need to actually use the quantum computer. Most likely though, we move onto the next step, which is to use the quantum computer to find the period of the function, f (x) = a^x mod N. We are going to need high accuracy. But quantum systems are very fragile and noisy, which means using a lot of extra qubits to correct the errors.
This doesn’t sound like a big deal in a world where we buy gigabit memories and terabyte discs for our laptops, but in fact, building even a few qubits is very hard, so it’s actually a serious concern. We will discuss error correction and hardware later in the course. First, we need to optimize the program for the quantum computer to suit our particular numbers a and N, which means recompiling the program. Then, we would use the broad superposition state for the variable x so that we calculate the modular exponentiation in superposition. Applying the quantum Fourier transform to that state should give us the period when we measure the result.
Finally, we take that period r that we found and calculate the gcds – gcd of a^r/2 +1 and N and gcd of a^r/2 - 1 and N. That should give us two prime number factors of our number N. Sometimes, the algorithm fails and we have to re-run it, but we shouldn’t have to do that very many times. So that’s the algorithm.
Shorのアルゴリズムは素晴らしい成果だとは思いませんか? しかし、これは多くの新しい概念を含み、量子と古典の両方の性質が組み合わさった複雑なアルゴリズムでもあります。 より深く理解するため、全体の流れを振り返ってみましょう。 その後、アルゴリズムのパフォーマンスへの影響について説明します。
This article is from the free online


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