Skip main navigation

Putting It All Together -Summarizing the Algorithm

Let’s take a look back at the overall structure of Shor's algorithm.
3.3
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.
36.2
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.
62.8
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.
101.5
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’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のアルゴリズムは素晴らしい成果だとは思いませんか? しかし、これは多くの新しい概念を含み、量子と古典の両方の性質が組み合わさった複雑なアルゴリズムでもあります。 より深く理解するため、全体の流れを振り返ってみましょう。 その後、アルゴリズムのパフォーマンスへの影響について説明します。

This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now