Washed aShor

Inspiration

RSA encryption, which secures much of the internet today, relies on the fact that factoring large semiprimes is classically intractable.

Shor’s Algorithm flipped that paradigm, proving that factoring could be exponentially faster with quantum computers. But, most Shor's implementations only work for fixed, small N. Washed aShor is inspired by the dream of a truly universal, scalable, and executable design of Shor’s Algorithm, which could factor arbitrary N on real or simulated quantum hardware like Quantum Rings (Qrings). We built this to expand the possibility of the thrilling quantum future.

What it does

We implement a customizable version of Shor’s Algorithm using Qiskit, capable of factoring any semiprime ( N ). It works both locally using AerSimulator from Qiskit and on Quantum Rings’ Qrings, a cloud-based quantum simulator optimized for high-shot, large-qubit circuits.

Features:

Constructs modular exponentiation circuits using ripple-carry adders
Performs quantum phase estimation with inverse QFT
Post-processes measurement results to extract the order ( r ) and factors of ( N )
Randomly samples coprime bases ( a ) and repeats until success
Fully modular, scalable, and built to handle inputs beyond toy examples

How we built it

We started by implementing Shor’s algorithm for N = 15, gradually generalizing it for larger numbers. Inspired by the paper “Shor’s Factoring Algorithm and Modular Exponentiation Operators”, we designed the modular exponentiation component.

The QFT was implemented using Qiskit’s library for simplicity. We tested the circuits with AerSimulator, and used Quantum Rings’ QrBackendV2 for more realistic quantum runs.

Challenges we ran into

One of the biggest challenges is the design of the modular exponentiation function, a key component of the phase estimation

Accomplishments that we're proud of

One of the biggest challenges was designing the modular exponentiation component to be both scalable and depth-efficient. As the input size increases, the circuit depth and run-time grow significantly — theoretically up to ( O(n^3) ).

Even with just a few bits, the algorithm took a long time to run:

Quantum Rings was precise but time-consuming for large circuits.
Even Qiskit's AerSimulator struggled with simulation time at scale.

Additionally, integrating the circuit into Quantum Rings required strict qubit layout and gate precision, making debugging and development more complex.

Although Shor’s algorithm promises exponential speedup in theory, capturing that quantum advantage in practice was a non-trivial task.

What we learned

Through this project, we gained a solid understanding of Shor's Algorithm, the foundations of quantum gates, and the vast potential of quantum computing. As newcomers to the field, this hands-on experience was not only educational but also inspiring, giving us a meaningful introduction to the world of quantum technology. We pushed ourselves to confront unfamiliar concepts, which sparked curiosity and intellectual growth. By the end of the hackathon, every team member had made significant progress. We're now more motivated than ever to deepen our knowledge and explore how quantum computing can improve the world around us.

What's next for Washed aShor

As underclassmen just beginning our journey, we know there’s still a long road ahead.
But through this project, we've gained hands-on experience with quantum computing that has sparked a deeper intellectual curiosity and excitement for this rapidly growing field.
We're committed to pushing the boundaries of technology and using quantum computers to make a real impact.

We're thrilled to keep building the future, and we're excited to stay connected and collaborate with any of you from this amazing hackathon!