SHOR'S ALGORITHM AND QUANTUM FOURIER TRANSFORM (QFT)
THE IMPORTANCE OF FACTORIZATION
The integer factorization problem is about finding two factors N1 and N2 which when multiplied gives the number N (N, N1, N2 > 1) [1]. When N1 and N2 are primes, this becomes especially hard. The problem is useful in the scientific community. The public and private key of the RSA cryptosystem are modern implementations of integer factorization problem with primes [2]. There is no known classical polynomial-time algorithm currently for this problem [1]. Currently, integers with 1000 or more bits are impossible to factor using known algorithms and classical hardware. Quantum computing is believed to have the potential to change this. Meanwhile, Shor’s algorithm is a breakthrough for this problem, factoring small numbers at time O(n^3logn) [1].
A SIMPLE EXPLANATION
Shor’s algorithm uses using modular exponentiation. Consider an odd N = N1*N2, 1 < N1, N2 < N. If we pick k < N such that gcd(k, N) = 1, we can show that there is a p > 0 such that k^p ≡ 1 (mod N) [1]. Using modular arithmetic definition, x ≡ y (mod m) iff m divides x – y, we can say N divides k^p − 1 = (k^(p/2) − 1)(k^(p/2) + 1) if p is even. n1 = k^(p/2) + 1 and n2 = k^(p/2) – 1 are greater than zero and have no common factor greater than 2 because |n1-n2| = 2 [1]. Since N = N1N2 was assumed to be odd, then N1 is a factor of either n1 or n2. If N1 is a factor of n1 and N, then N1 divides both n1 and N and one can find N1 by computing gcd(n1, N) [1]. The same goes for N2.
Here is an example. Given N = 15 and k = 7, a modular exponentiation sequence [3] is 1, 7, 4, 13, 1, 7, 4, 13, 1, . . . with period 4. Since the period 4 is an even number, 74 mod 15 ≡ 1 ⇒ 74 − 1 mod 15 ≡ 0 ⇒ (72 − 1)(72 + 1) mod 15 ≡ 0 . This means 15 divides 48*50, which can be used to factorize 15 as gcd(48, 15) = 3 and gcd(50, 15) = 5.
QUANTUM FOURIER TRANFORM
Finding the period of a modular exponentiation sequence is not classically easy, but with quantum computing, the period can be found in polynomial time using the Quantum Fourier Transform (QFT).
The classical Fourier transform has the following equation:
Where
• yk and xj are complex numbers. • j and k are indices, ranging from 0 to N-1. • N is the length of the data set x.
The quantum Fourier transform has the same equation but with one difference. The data set is a vector, with each element in the vector representing the probability of the state being measured as that combination of 0 and 1 and is often called ψ instead of x [4].
|ψ> = α1 |00…0>⋯αn |11..11>
This can be represented as a matrix. Eg. For a 2-qubit state ψ,
The magnitude of the state vector ψ remains unchanged but is rotated using a series of operations of the form e^(iθ) [4].
Our matrix now looks like this.
Phase rotations can be implemented using the quantum R gate:
The factorization algorithm uses QFT because it can “compute” the period of a periodic input. One can find the period of the corresponding modular exponentiation sequence using QFT if one is able to encode its period in the amplitudes of a quantum state (the input to QFT) [1]
ILLUSTRATION OF A PERIOD FINDING CIRCUIT
The following is a high-level illustration of the circuit.
1. The first QFT on register A produces an equal superposition of the qubits from A. The current state is
2. The function f (i) = X_i (mod N) is used on the second register B. The current state is
3. In the last QFT transform, register A is a superposition with only equal non-zero amplitudes of |i⟩ for which f (i) = s. F(i) is in a periodic superposition with period r.
REFERENCES
[1] Coles, P. J., Eidenbenz, S., Pakin, S., Adedoyin, A., Ambrosiano, J., Anisimov, P., ... & Gunter, D. (2018). Quantum algorithm implementations for beginners. arXiv, arXiv-1804.
[2] Boneh, D. (1999). Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46(2), 203- 213.
[3] https://www2.math.upenn.edu/~mlazar/math170/notes06-3.pdf
[4] https://medium.com/@sashwat.anagolum/qftaddition-ce0a0b2bc4f4