3.2 Shor's factoring algorithm

Shor's algorithm is a quantum computing breakthrough that can factor large numbers exponentially faster than classical computers. This has huge implications for cryptography, as it could potentially break widely-used encryption methods like RSA that rely on the difficulty of factoring large numbers.

Understanding Shor's algorithm is crucial for businesses to assess quantum computing's impact on cybersecurity. Companies need to start preparing for quantum-safe cryptography alternatives to protect sensitive data and communications in a post-quantum world.

Overview of Shor's algorithm

• Shor's algorithm is a quantum algorithm for integer factorization that runs in polynomial time, exponentially faster than the best known classical algorithms
• It leverages the power of quantum computing to solve a problem that is believed to be intractable for classical computers, with significant implications for cryptography and cybersecurity
• Understanding Shor's algorithm is crucial for businesses to assess the potential impact of quantum computing on their security practices and to plan for the adoption of quantum-safe alternatives

Number theory foundations

Fundamental theorem of arithmetic

Top images from around the web for Fundamental theorem of arithmetic

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

1 of 3

Top images from around the web for Fundamental theorem of arithmetic

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

• 

  Shor's Quantum Factoring Algorithm View original

  Is this image relevant?

1 of 3

• States that every positive integer greater than 1 can be uniquely expressed as a product of prime numbers (2, 3, 5, 7, 11...)
• Provides the basis for the integer factorization problem, which is central to the security of many cryptographic systems (RSA)
• Shor's algorithm exploits the properties of prime factorization to efficiently factor large numbers on a quantum computer

Modular arithmetic

• Arithmetic operations performed on integers within a fixed range, where numbers "wrap around" after reaching a certain value (modulus)
• Plays a crucial role in number theory and cryptography, including the RSA algorithm and Shor's algorithm
• Used in Shor's algorithm to transform the factoring problem into a period-finding problem

Euler's totient function

• Counts the number of positive integers up to a given integer n that are relatively prime to n (have no common factors other than 1)
• Denoted as φ(n) and used in various number-theoretic calculations and cryptographic algorithms
• In Shor's algorithm, Euler's totient function is used to determine the order of an element in a multiplicative group modulo n

Continued fractions

• Represent real numbers as fractions with integer numerators and denominators, where the denominators are recursively defined
• Used in number theory for approximating irrational numbers and solving Diophantine equations
• In Shor's algorithm, continued fractions are employed to extract the period from the output of the quantum phase estimation procedure

Classical factoring algorithms

Trial division

• Simplest factoring algorithm that divides the number n by all integers from 2 up to the square root of n
• Has a time complexity of O(√n), making it inefficient for large numbers
• Serves as a baseline for comparing the efficiency of more advanced factoring algorithms

Pollard's rho algorithm

• Probabilistic algorithm that uses a sequence of numbers generated by a polynomial modulo n to find a factor of n
• Has an expected running time of O(√p), where p is the smallest prime factor of n
• More efficient than trial division but still exponential in the size of the input

Quadratic sieve

• Fastest known classical factoring algorithm for numbers up to around 100 digits
• Works by searching for smooth numbers (numbers with only small prime factors) and using them to construct a congruence of squares modulo n
• Has a subexponential running time of $e^{O(\sqrt{\log n \log \log n})}$

General number field sieve

• Most efficient classical factoring algorithm for numbers larger than 100 digits
• Extends the ideas of the quadratic sieve to algebraic number fields, using sophisticated mathematical techniques
• Has a subexponential running time of $e^{O((\log n)^{1/3} (\log \log n)^{2/3})}$, making it the best known classical factoring algorithm

Quantum Fourier transform

Discrete Fourier transform

• Transforms a sequence of complex numbers into another sequence that represents the frequency components of the original sequence
• Widely used in signal processing, data compression, and other applications
• The quantum Fourier transform is a quantum analog of the discrete Fourier transform, operating on quantum states

Quantum circuit for QFT

• Consists of a series of Hadamard gates and controlled phase rotation gates applied to the qubits in a quantum register
• Performs the quantum Fourier transform on the amplitudes of the quantum state, enabling interference and superposition effects
• The QFT circuit is a key component of Shor's algorithm and many other quantum algorithms

QFT vs classical FFT

• The classical Fast Fourier Transform (FFT) is an efficient algorithm for computing the discrete Fourier transform, with a time complexity of O(n log n)
• The quantum Fourier transform achieves an exponential speedup over the classical FFT, requiring only O(log n) gates for n qubits
• This speedup is a fundamental advantage of quantum computing and is exploited in Shor's algorithm for period finding

Complexity of QFT

• The QFT can be performed using O(log n) quantum gates for n qubits, making it exponentially faster than the classical FFT
• However, the output of the QFT is a quantum state, which cannot be directly accessed or measured without collapsing the superposition
• To extract useful information from the QFT, additional quantum operations (phase estimation) and classical post-processing are required

Period finding

Quantum phase estimation

• Quantum algorithm that estimates the eigenvalue of a unitary operator corresponding to a given eigenvector
• Uses the quantum Fourier transform to extract the phase information from the eigenvector, which encodes the eigenvalue
• In Shor's algorithm, phase estimation is used to find the period of a periodic function, which is related to the factors of the input number

Eigenvalues and eigenvectors

• An eigenvector of a linear operator is a non-zero vector that, when the operator is applied to it, yields a scalar multiple of itself (the eigenvalue)
• Eigenvalues and eigenvectors play a fundamental role in quantum mechanics, describing the possible measurement outcomes and the corresponding quantum states
• In Shor's algorithm, the period of a function is encoded as the eigenvalue of a unitary operator, which can be estimated using phase estimation

Unitary operators

• Linear operators that preserve the inner product between vectors, meaning they maintain the geometry of the vector space
• In quantum mechanics, the evolution of a quantum system is described by a unitary operator, which ensures the conservation of probability
• In Shor's algorithm, the periodic function is implemented as a unitary operator, allowing the period to be extracted using quantum phase estimation

Estimating the period

• The goal of the period-finding step in Shor's algorithm is to estimate the period of a periodic function $f(x) = a^x \bmod N$, where $a$ is a randomly chosen integer coprime to $N$
• By applying phase estimation to the unitary operator that encodes the periodic function, the period can be obtained with high probability
• The estimated period is then used in the classical post-processing step to determine the factors of the input number $N$

Shor's factoring algorithm

Reduction to period finding

• Shor's algorithm reduces the problem of factoring an integer $N$ to the problem of finding the period of the function $f(x) = a^x \bmod N$, where $a$ is a randomly chosen integer coprime to $N$
• If the period $r$ of $f(x)$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} \pm 1, N)$ is a non-trivial factor of $N$
• This reduction allows the factoring problem to be solved efficiently on a quantum computer using the period-finding subroutine

Classical part of Shor's algorithm

• Shor's algorithm begins with a classical preprocessing step, which selects a random integer $a$ coprime to the input number $N$
• After the quantum period-finding subroutine, the algorithm performs classical post-processing to extract the factors from the estimated period
• This involves computing the greatest common divisor (GCD) of $a^{r/2} \pm 1$ and $N$, which can be done efficiently using the Euclidean algorithm

Quantum part of Shor's algorithm

• The quantum part of Shor's algorithm consists of the period-finding subroutine, which uses the quantum Fourier transform and phase estimation
• It starts by preparing a superposition of all possible input values for the periodic function $f(x) = a^x \bmod N$
• The quantum circuit then applies the unitary operator that encodes the periodic function, followed by the quantum Fourier transform to extract the period
• The output of the quantum circuit is measured, yielding an estimate of the period with high probability

Probability of success

• The success probability of Shor's algorithm depends on the probability of measuring a value that allows the period to be determined accurately
• The algorithm succeeds with a probability of at least $1 - 1/2^k$, where $k$ is the number of qubits used in the quantum circuit
• In practice, the algorithm may need to be repeated a few times with different random values of $a$ to ensure a high probability of success
• The overall success probability can be boosted to near-certainty by performing multiple runs of the algorithm and combining the results

Complexity analysis

Quantum vs classical complexity

• Shor's algorithm demonstrates the potential of quantum computers to solve certain problems much faster than classical computers
• The quantum part of Shor's algorithm runs in polynomial time, $O((\log N)^3)$, while the best known classical factoring algorithms have subexponential running times
• This exponential speedup is a key motivation for the development of large-scale quantum computers and the study of quantum algorithms

Polynomial vs exponential time

• Polynomial-time algorithms have running times that scale as a polynomial function of the input size, $O(n^k)$ for some constant $k$
• Exponential-time algorithms have running times that scale as an exponential function of the input size, $O(2^{n^k})$ for some constant $k$
• Polynomial-time algorithms are generally considered efficient, while exponential-time algorithms become intractable for large input sizes
• Shor's algorithm achieves a polynomial-time solution for factoring, which is believed to require exponential time on classical computers

Impact on RSA cryptography

• The security of the widely-used RSA cryptosystem relies on the difficulty of factoring large integers, typically 1024 bits or more
• Shor's algorithm, if implemented on a large-scale quantum computer, would render RSA vulnerable to attacks, jeopardizing the security of many digital communications and transactions
• This has prompted the search for quantum-safe alternative cryptographic schemes that can withstand attacks by both classical and quantum computers

Limitations and assumptions

• Shor's algorithm assumes the availability of a large-scale, fault-tolerant quantum computer with thousands of qubits and low error rates
• Current quantum hardware is still far from achieving the scale and reliability required to run Shor's algorithm for practically relevant input sizes
• The algorithm also relies on the ability to implement the quantum Fourier transform and phase estimation with high precision, which may be challenging in practice
• Despite these limitations, Shor's algorithm remains a key motivation for the development of quantum computing and a benchmark for the power of quantum algorithms

Implementations and experiments

Experimental demonstrations

• Shor's algorithm has been experimentally demonstrated on small-scale quantum computers, factoring small numbers such as 15 and 21
• These demonstrations serve as proof-of-concept implementations and help validate the principles behind the algorithm
• However, scaling up these experiments to factor larger numbers remains a significant challenge due to the limitations of current quantum hardware

Quantum hardware requirements

• To factor a 1024-bit number using Shor's algorithm, a quantum computer with several thousand logical qubits and low error rates would be required
• This scale is beyond the capabilities of current quantum devices, which have at most a few hundred noisy qubits
• Advances in quantum hardware, such as improved qubit coherence times, gate fidelities, and error correction schemes, are needed to enable practical implementations of Shor's algorithm

Error correction and fault tolerance

• Quantum error correction is essential for mitigating the effects of noise and errors in quantum computations, which are inevitable in real-world quantum devices
• Fault-tolerant quantum computing schemes, such as surface codes and color codes, aim to achieve reliable computation with unreliable components
• Implementing Shor's algorithm on a fault-tolerant quantum computer would require encoding the quantum state using an error-correcting code and performing the computation using fault-tolerant logical gates

Prospects for scalability

• Scaling up quantum computers to the size required for practical applications of Shor's algorithm is a major challenge and an active area of research
• Various approaches, such as superconducting qubits, trapped ions, and photonic qubits, are being explored as potential platforms for large-scale quantum computing
• Modular architectures, which combine smaller quantum processors into a larger system, may provide a path towards scalability
• While significant progress has been made in recent years, it remains uncertain when and if a quantum computer capable of running Shor's algorithm for large numbers will be realized

Business implications

Impact on cryptography in industry

• The potential of Shor's algorithm to break RSA and other widely-used public-key cryptosystems has significant implications for businesses that rely on secure digital communications and transactions
• Industries such as finance, healthcare, and government, which handle sensitive data and require strong encryption, are particularly vulnerable to the threat of quantum computing
• Businesses need to assess their exposure to quantum risk and develop strategies for transitioning to quantum-safe cryptography

Post-quantum cryptography

• Post-quantum cryptography refers to cryptographic algorithms that are designed to be secure against attacks by both classical and quantum computers
• These algorithms rely on mathematical problems that are believed to be hard for both classical and quantum computers, such as lattice-based cryptography, code-based cryptography, and multivariate cryptography
• Standardization efforts, such as the NIST Post-Quantum Cryptography Standardization Process, aim to select and standardize quantum-safe cryptographic algorithms for widespread adoption

Quantum-safe alternatives to RSA

• Lattice-based cryptosystems, such as the Learning with Errors (LWE) and Ring Learning with Errors (RLWE) problems, are promising candidates for replacing RSA and other vulnerable public-key cryptosystems
• Hash-based signature schemes, such as the Leighton-Micali Signature (LMS) scheme and the eXtended Merkle Signature Scheme (XMSS), provide quantum-safe alternatives for digital signatures
• Symmetric-key algorithms, such as the Advanced Encryption Standard (AES) with larger key sizes, are believed to be secure against quantum attacks and can be used for encryption and key exchange

Preparing for quantum disruption

• Businesses should start preparing for the potential impact of quantum computing on their cybersecurity practices, even though the timeline for practical quantum computers remains uncertain
• This involves assessing the quantum risk to their current cryptographic infrastructure, identifying critical assets and data that need long-term protection, and developing a roadmap for transitioning to quantum-safe cryptography
• Engaging with quantum experts, participating in standardization efforts, and monitoring the progress of quantum computing and post-quantum cryptography are important steps in staying ahead of the quantum threat
• By proactively addressing the challenges posed by Shor's algorithm and quantum computing, businesses can ensure the long-term security of their digital assets and maintain the trust of their customers and stakeholders.