## Want to keep learning?

This content is taken from the Keio University's online course, Understanding Quantum Computers. Join the course to learn more.
3.17

## Keio University

Skip to 0 minutes and 3 seconds 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.

Skip to 0 minutes and 36 seconds 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.

Skip to 1 minute and 3 seconds 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.

Skip to 1 minute and 42 seconds 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.

# 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.

# まとめ - アルゴリズムのまとめ

Shorのアルゴリズムは素晴らしい成果だとは思いませんか？ しかし、これは多くの新しい概念を含み、量子と古典の両方の性質が組み合わさった複雑なアルゴリズムでもあります。 より深く理解するため、全体の流れを振り返ってみましょう。 その後、アルゴリズムのパフォーマンスへの影響について説明します。