Shor’s Algorithm

Much of the buzz around quantum computing comes from one simple fact: a quantum computer with several thousand qubits can solve a certain strategic problem that classical computers have no hope of solving.

In 1994 [1], Peter Shor unveiled an algorithm to crack today’s widely used encryption schemes. Decrypting a message might take trillions of years on a classical computer. But Shor’s algorithm, running on a sufficiently large quantum computer, can decrypt a message in less than a minute. It would be nice if most people welcomed a solution to this decryption problem. But, unfortunately, most people who want to break encryption schemes are malicious hackers.

Businesses and governments are taking this problem seriously. At this very moment (no matter when you’re reading this), people around the world are developing post-quantum cryptography schemes. These newly formulated schemes must be resistant to vulnerabilities arising from quantum...

Technical requirements

You can find the code used in this chapter on GitHub:

https://github.com/PacktPublishing/Quantum-Computing-Algorithms

A popular encryption scheme

In August 1977, three researchers wrote an article for a mathematical curiosities column in the Scientific American magazine [2]. The article described what has come to be known as RSA encryption, so named after its originators—Rivest, Shamir, and Adelman. The idea behind RSA is that multiplying numbers is easy, but factoring numbers is difficult. In Figure 9.1, we get a 100-digit number by multiplying two 50-digit numbers:

Figure 9.1 – The RSA-100 number

When I presented this multiplication problem to my laptop computer, I got the answer almost instantly. Multiplying two numbers, however large they may be, isn’t challenging for today’s hardware.

But what if we try to solve the problem in reverse? What if we start with the 100-digit number at the bottom of Figure 9.1, and ask a computer to find the two 50-digit numbers at the top of the figure? When I handed this task to a respected mathematics...

How Shor’s algorithm works

If you remember only one thing about the strategy behind Shor’s algorithm, it should be this: the algorithm examines the repetition within a particular sequence of numbers and uses that repetition to factor the public key.

Let’s take a look at some sequences of numbers. (Once again, the numbers in our examples are laughingly small to ensure that the arithmetic is manageable.) On a rainy day in August, Alice initiates a sensitive conversation with Bob. While Eve does her snooping, she notices Alice sending the public key 15 to Bob. Eve’s goal is to factor 15 into its component parts.

With the help of her computer, Eve chooses a number that’s smaller than 15. As we did in the previous section, we’ll call this smaller number a coprime. As with the previous section’s coprime, this smaller number must have no divisors (other than 1) in common with the public key 15.

In this example, let’s have Eve...

Complex numbers

Much of the work in Shor’s algorithm depends on a matrix known as the QFT. Using the QFT, Eve can find the period of a sequence and use that period to decrypt Bob’s message. The QFT uses complex numbers to perform its magic, so this section covers some facts about complex numbers.

Complex number basics

Imaginary numbers were first described by Girolamo Cardano in 1545. The best-known imaginary number is , also known as i, and sometimes in Python code, j. The worst part of imaginary numbers is their name. If we called them “super numbers” instead of “imaginary numbers,” people wouldn’t be so suspicious of them. It’s true that imaginary numbers don’t arise naturally in day-to-day situations. So, for most people, imaginary numbers don’t exist. But scientists rely on imaginary numbers all the time. Imaginary numbers are very useful.

A complex number is a number with two parts. One of those parts...

Finding a sequence’s period

In the section entitled How Shor’s algorithm works, we saw how knowing the period of a certain repeating sequence of numbers helps an eavesdropper factor a large public key and decrypt a message. How can quantum computing help the eavesdropper discover a sequence’s period?

Consider the following sequence of numbers:

1, 2, 7, 10, 15, 3, 1, 2, 7, 10, 15, 3, 1, 2, 7, 10, 15, 3, 1, 2, 7, 10, 15, 3

For want of a better name, we’ll call this my sequence. In my sequence, the pattern 1, 2, 7, 10, 15, 3 occurs four times:

• Since the pattern contains six numbers, we say that my sequence’s period is 6
• Since the pattern occurs four times in my sequence, we say that the pattern’s frequency is 4

My sequence contains 24 numbers. So, the period and frequency in my sequence are related by the following formula:

Mathematicians refer to my sequence’s period and its frequency as dual variables...

Shoring up your knowledge

Understanding Shor’s algorithm can be difficult because examples with manageable-size numbers are hard to find. For instance, a minimal circuit that factors 15 with 11 as its coprime may involve five qubits. Wielding five qubits at once means multiplying 32 × 32 matrices by one another. Each matrix contains 1024 complex numbers. That’s too many numbers for one example in a book.

You can overcome the conceptual difficulties using summations and linear algebra, and I encourage you to study more about these approaches. In the meantime, this section describes some aspects of Shor’s algorithm that previous sections glossed over.

At some future date, when we have quantum computers that can crack real RSA encryption problems, those computers will probably have thousands of qubits. Alice will start with a public key, n, that has 2048 bits. To attack that key with Shor’s algorithm, Eve’s circuit will implement an N ×...

Illustrating Shor’s algorithm with Qiskit code

In this section, we present two Qiskit programs. One program illustrates, in a straightforward manner, the application of Qiskit’s QFT function. The other uses special tricks to construct a circuit that scales for large numbers. Neither program implements Shor’s algorithm in complete detail.

Testing the QFT

We begin this example with the required import statements:

from qiskit import QuantumCircuit, Aer, executefrom qiskit.circuit.library import QFT
from qiskit.tools.visualization import plot_histogram
import numpy as np

With public key 15 and coprime 7, we create a vector containing eight values of 7n % 15:

public_key = 15coprime = 7
#coprime = 11
vector = []
for i in range(8):
    vector.append(coprime**i % public_key)
norm = np.linalg.norm(vector)
statevector = vector / norm
print('vector:')
print(vector)
print()
print('statevector:')
print(statevector)

The...

Summary

Shor’s algorithm is the crowning glory in the theory of gate-based quantum computing. Using Shor’s algorithm, a quantum computer can do what no classical computer could ever have time to do. The algorithm quickly finds the period of a coprime powers sequence and uses information about that period to factor unimaginably large numbers. That’s the good news.

The bad news is that the most obvious use of Shor’s algorithm is for unsavory purposes. Many applications in use today include some form of RSA encryption. And with Shor’s algorithm, a hacker can easily break the RSA encryption scheme. For this reason, the National Institute of Standards and Technology (NIST) in the United States has been running an initiative to develop quantum-proof post-quantum cryptography schemes [4]. Someday, in the not-too-distant future, the battle over your security and privacy will be fought with quantum computers and even more robust cryptographic algorithms...

Further reading

[1] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124-134, doi: 10.1109/SFCS.1994.365700.

[2] Rivest, R. L., Shamir, A., and Adleman, L. M. (1977, August). A method for obtaining digital signatures and public-key cryptosystems: https://web.williams.edu/Mathematics/lg5/302/RSA.pdf

[3] QPE: https://github.com/qiskit-community/qiskit-textbook/blob/main/content/ch-algorithms/quantum-phase-estimation.ipynb

[4] Post-Quantum Cryptography | Round 4 Submissions: https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions

Questions

1. Using a pencil and paper or a hand calculator, find the factors of 14 using 3 as a coprime. (Use only the technique shown in the section entitled The role of a period in factoring a number. Don’t try applying the QFT.)
2. Using a pencil and paper or a hand calculator, find the factors of 35 using 2 as a coprime. (Again, use only the technique shown in the section entitled The role of a period in factoring a number.)
3. Write the value of using a + bi notation.
4. Write down the entries of a 4 × 4 QFT matrix. Use the notation for complex numbers that’s shown in Figure 9.8. Then, use the 4 × 4 QFT matrix to find the entries in the QFT† matrix.
5. Write down the entries of a 2 × 2 QFT matrix. Does this matrix look familiar?
6. Fill in the missing values in Figure 9.20.
7. Why isn’t 3 useful as a coprime when you try to factor 22?
8. Starting with the powers of 7 shown in the How Shor’s algorithm works section, use...