Shor’s Algorithm

A guided research project in Quantum Computing.

← Quantum Computing projects

Experience Research Quantum Computing

Question

How can quantum period finding be used to factor a composite integer?

The quantum circuit exposes a hidden period that ordinary arithmetic turns into factors.
The quantum circuit exposes a hidden period that ordinary arithmetic turns into factors.

Goals

  • Derive the reduction from factoring to order finding.
  • Implement or simulate the quantum and classical stages on small cases.

Method

Find the period of modular powers and convert it into candidate factors.

  • Choose a base coprime to \(N\) and construct modular exponentiation.
  • Apply phase estimation or the quantum Fourier transform to estimate its order.
  • Use continued fractions and greatest common divisors to recover and verify factors.