Shor’s algorithm
Hybrid algorithm to factor numbers
Quantum component finds period r of sequence a1, a2, . . . ai, . . . , given an oracle function that maps i to ai
Skeleton of the algorithm:
- create a superposition of all oracle inputs and call the oracle
- apply a quantum Fourier transform to the input qubits
- read the input qubits to obtain a random multiple of 1/r
- repeat a small number of times to infer r