Implementation of Shor’s Algorithm

Inspiration

Our inspiration came from one of the biggest breakthroughs in quantum computing: Shor’s Algorithm. Since its introduction in 1994, it has stood as the clearest demonstration of true quantum advantage. We wanted to understand not just the theory, but what it actually looks like to implement even a small version of it on modern quantum tools.

What it does

Shor’s Algorithm factors large integers by transforming the problem into one of period‑finding, something quantum computers excel at. It uses superposition and entanglement to explore many possibilities at once, and the Quantum Fourier Transform to extract hidden periodicity. In practice, this means a quantum computer can solve a problem that classical computers struggle with, especially as numbers grow large.

How we built it

We built a small working demo using Qiskit, IBM’s open‑source quantum computing framework. Our implementation focuses on the core quantum subroutine: preparing superposition states, performing modular exponentiation, and applying the Quantum Fourier Transform. Since today’s quantum hardware is still limited, we tested our circuits on Qiskit’s simulators and used built‑in tools to visualize the quantum states and measurement outcomes.

Challenges we ran into

One of the biggest challenges was the circuit depth. Even small instances of Shor’s Algorithm require many gates, and that quickly becomes too large for real hardware. Another challenge was implementing modular exponentiation efficiently, it’s the most resource‑intensive part of the algorithm.

Accomplishments that we're proud of

We’re proud that we were able to build a fully functioning demo that actually recovers the correct period and factors small integers. Seeing the algorithm work end‑to‑end, even on a small scale.

What we learned

We learned how powerful the combination of mathematics and quantum mechanics can be. We also gained hands‑on experience with Qiskit, quantum circuits, and debugging quantum algorithms something that feels very different from classical programming.

What's next for Implementation of Shor’s Algorithm

Next, we want to push our implementation further. That means experimenting with real quantum hardware, exploring error‑mitigation techniques, and testing more efficient versions of the Quantum Fourier Transform.

.

Built With

• github
• streamlit