Shor’s Algorithm is one of the most famous Quantum Algorithms today. It remains renowned because of its implications for the world of cryptography and, in fact, almost every facet of our lives, from communications to finance. If Quantum Computers can effectively run Peter Shor’s Algorithm, they can break into the fabric of our modern life, and one can argue that little is safe. Here, we conduct an overview of the algorithm, why it’s one of the oldest quantum algorithms dating back to 1994, and how it has created an impetus for those to harness it and for some to combat it.
Peter Shor: The Man Behind Shor’s Algorithm
Peter Shor (born August 14, 1959) is an American professor of applied mathematics at the Massachusetts Institute of Technology (MIT). He is widely known for his pioneering work in the field of quantum computing, particularly for devising Shor’s algorithm, which is a quantum algorithm that has the potential to factorize exponentially faster than the best classical algorithms currently known. Shor’s algorithm has significant implications for cryptography, and its discovery made Peter Shor famous in the scientific community worldwide.
In addition to his contributions to quantum computing, Peter Shor has performed pioneering work in combinatorial analysis. He received a Bachelor of Science in Mathematics from Caltech and a Ph.D. in applied mathematics from MIT. He has also held tenured appointments in the MIT Mathematics department and has been a member of the Theory of Computer Science group at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL).
Shor has been recognized for his contributions to quantum computing and mathematics. He has received numerous awards and honours, including the Turing Award (in 2021), the Dirac Medal (in 2008), and the National Security Agency’s Mathematics in Cryptology Award (in 1995). Shor’s work on quantum computing continues to be an active area of research, and his contributions have significantly advanced the field.
In summary, Peter Shor is a highly respected mathematician and computer scientist known for his contributions to the field of quantum computing and his discovery of Shor’s algorithm, which has significant implications for cryptography.
Shor’s Algorithm, The Quantum Algo from 1994
Shor’s algorithm is a quantum computer algorithm for factoring integers into their prime factors, and it was developed in 1994 by Peter Shor. The algorithm is important because it can factor large numbers exponentially faster than the best-known classical algorithms.
The algorithm consists of two main parts: classical pre-processing and quantum parts. The classical part reduces the factorization problem to finding the period of a specific function. This can be done classically using a regular (classical) computer. The quantum part uses a quantum computer to efficiently find the function’s period (so-called period finding), which is used to factor the number.
The outline of Shor’s algorithm can be summarized as follows:
- Choose N to be factorized, where
Nis a large composite number with two prime factors,pandq. - Choose a random number ‘a’ that is less than N and is relatively prime to N.
- Apply the Quantum Fourier Transform (QFT) to a set of n qubits in a superposition of all possible states. This step generates an equal superposition of all possible values of the periodic function, f(x) = a^x mod N, where x is an integer between 0 and N-1.
- Measure the output of the QFT, which results in a random value of the periodic function, say s. This measurement collapses the superposition of states to a single state.
- Calculate the greatest common divisor (GCD) of N and (a^s/2) + 1 or (a^s/2) – 1. If the GCD is not equal to 1 or N, then we have found a non-trivial factor of N. Otherwise, repeat steps 2-5 until a non-trivial factor is found.
It is important to note that the quantum part of Shor’s algorithm requires a large, fault-tolerant quantum computer, which is not yet available. Nevertheless, the algorithm has significant implications for data security since it could break the RSA encryption algorithm based on the assumption that factoring large numbers is a complex problem.
Quantum Algorithm Zoo
One meaning of the term is a comprehensive catalog of quantum algorithms maintained by Stephen Jordan at Microsoft Research. This catalog contains descriptions and explanations of various quantum algorithms used in quantum computing, such as algebraic and number theoretic algorithms used for factoring.
