Shor's Algorithm

A full-stack quantum implementation of Shor’s Algorithm using Toffoli-based modular arithmetic to efficiently factor semiprimes through modular exponentiation and quantum phase estimation.

Comment

Inspiration

🔍 Inspiration

Our project was inspired by the elegance and power of Shor’s Algorithm, a quantum algorithm capable of factoring large semiprime numbers exponentially faster than any known classical method. We were particularly intrigued by a recent paper on Toffoli-based modular multiplication which demonstrated a more hardware-efficient approach to building the algorithm. This blend of quantum theory, reversible logic, and computational number theory sparked our desire to implement the full algorithm from scratch.

🧠 What We Learned

Throughout the project, we deepened our understanding of:

  • Quantum modular arithmetic, especially how to perform addition and multiplication using reversible gates.
  • Quantum Phase Estimation (QPE) and its central role in extracting periodicity.
  • The design of Toffoli-based circuits for arithmetic and how to optimize them.
  • The full pipeline of quantum algorithm implementation, from idea to execution on quantum simulators.

🛠️ How We Built It

We built the project using QuantumRings, constructing each component in modular layers:

  1. Reversible Adders & Modular Multipliers using Toffoli and ancilla-efficient techniques.
  2. A custom modular exponentiation circuit parameterized by input values.
  3. A full QPE implementation that extracts the order of a mod N.
  4. Classical post-processing to recover the prime factors from measured outcomes.

⚠️ Challenges

Building a full Shor’s pipeline came with several challenges:

  • Designing reversible circuits that worked with limited gate sets and without unnecessary ancilla.
  • Debugging quantum arithmetic gates, where even a single miswired control led to incorrect results.
  • Integrating quantum and classical components seamlessly.
  • Keeping the project scalable while ensuring correctness on test cases like N = 15, 21, and 35.

✅ The Result

A working quantum implementation of Shor’s Algorithm that efficiently factors small semiprimes with a clean, modular circuit design—bringing us one step closer to practical quantum advantage.

Built With

Share this project:

Updates