Most of the digital security we rely on today is based on a simple but powerful mathematical idea: while it is easy to multiply two very large prime numbers together, it is practically impossible for a classical computer to reverse the process and find those original prime factors.
This is the foundation of RSA encryption, which protects everything from your bank account to your private conversations. However, in 1994, Peter Shor published an algorithm that, when run on a large-scale quantum computer, can perform this factorization efficiently. Shor’s algorithm doesn’t just offer a speedup; it offers a way to break the core of modern encryption, making it one of the most famous and consequential quantum algorithms ever conceived.
🧩 The Hybrid Quantum-Classical Sandwich
Shor’s algorithm is a powerful example of a hybrid algorithm, a ‘sandwich’ of classical and quantum computing. The process begins on a classical computer, where we set up the problem. The most difficult and time-consuming part of the process—period finding—is then handed off to a quantum computer.
The final step is to take the output from the quantum machine and use a classical algorithm to quickly and efficiently solve for the prime factors. While today’s quantum computers aren’t yet large or reliable enough to crack internet-level encryption, the existence of Shor’s algorithm means that such encryption is only secure for a limited time.
🔭 Period Finding: The Quantum Core
The quantum part of Shor’s algorithm solves a problem called period finding. Imagine a sequence of numbers that repeats over and over again. The period of the sequence is the number of elements before it repeats.
For example, the sequence 3, 7, 2, 4, 3, 7, 2, 4 has a period of 4. Shor’s algorithm uses quantum parallelism to find this period in a very clever way. It creates a superposition of all possible inputs and queries a special oracle to find the period. It then uses the quantum Fourier transform to make a single, precise measurement that reveals the period. Once the period is found, the information is sent back to the classical computer to quickly determine the prime factors and break the encryption.
🎲 Grover’s Algorithm: Searching Unstructured Data
Another powerful and practical algorithm is Grover’s algorithm. Imagine you have an unstructured database, like a giant box of unorganized documents, and you’re looking for one specific item. A classical computer would have to check each item one by one, a process that can take a very long time. Grover’s algorithm provides a quadratic speedup for this problem. It uses a series of quantum operations, or ‘Grover iterations,’ to amplify the amplitude of the item you’re looking for, making it far more likely to be measured than any other item. This algorithm is useful for any problem where checking a solution is easy, but finding it is hard.
—
Glassner, Andrew. Quantum Computing: From Concepts to Code. No Starch Press, 2025.
More Topics
- The Deutsch-Jozsa Algorithm: An Exponential Leap in Quantum Problem Solving
- The Bernstein-Vazirani Algorithm: Unmasking a Secret With a Single Query
- Simon’s Algorithm: The First Quantum Speedup That Left Classical Computers in the Dust
- Cracking the Code: How Quantum Parallelism Solves Deutsch’s Problem in One Step
- Your First Quantum Program: The ‘Hello, World!’ of a Qubit
- Scaling Up: How Quantum Computers Handle Multiple Qubits
- The ‘Spooky Action’: What Happens When Qubits Entangle?
