Skip to main content
Glossary

Quantum glossary

Shor's algorithm

A quantum algorithm that factors integers and computes discrete logarithms in polynomial time.

It reduces factoring to finding the period of modular exponentiation, and finds the period with a QFT. It breaks RSA and elliptic-curve cryptography — but only on a large fault-tolerant machine that does not yet exist.

See it for yourself

Related terms

  • Quantum Fourier transform — The quantum version of the discrete Fourier transform, acting on amplitudes with only O(n²) gates for n qubits.
  • Quantum phase estimation — An algorithm that reads out the eigenvalue phase of a unitary into a register of qubits.
  • Post-quantum cryptography — Classical cryptography designed to resist attack by quantum computers, running on ordinary hardware.