Quantum Computing Algorithms
A sequence that leads from the quantum Fourier transform, through phase estimation, to Shor's algorithm for factoring integers, and then to building that algorithm as a circuit.
Quantum Computation (QT-05), AICTE Quantum Technology Programme, MNIT Jaipur, 2025 ยท Full playlist on YouTube
- 01
Quantum Fourier Transform
The quantum Fourier transform is the quantum counterpart of the discrete Fourier transform. It acts on the amplitudes of a quantum state rather than on a list of numbers stored in memory. It is built from Hadamard gates and controlled phase rotations, followed by swaps that reverse the order of the qubits. The number of gates grows only with the square of the number of qubits. It is the key subroutine in phase estimation and Shor's algorithm.
- Discrete Fourier transform
- Quantum Fourier transform
- Hadamard gate
- Controlled phase rotations
- Qubit reversal with swap gates
- Gate count
- 02
Quantum Phase Estimation
Phase estimation finds the eigenvalue of a unitary operator, which is fixed by a phase, when one of its eigenvectors is available as a quantum state. A register of extra qubits controls repeated applications of the unitary. This writes the phase into that register through phase kickback, and an inverse quantum Fourier transform turns it into a binary number that can be measured. More qubits in the register give more digits of precision.
- Eigenvalues of unitary operators
- Eigenphase
- Controlled unitary operations
- Phase kickback
- Inverse quantum Fourier transform
- Precision
- 03
Shor's Factoring Algorithm
Shor's algorithm factors an integer by turning factoring into the problem of finding the period of a modular exponentiation function. The quantum computer finds this period efficiently with phase estimation and the quantum Fourier transform. The other steps are classical: picking a random number, recovering the period with continued fractions and computing greatest common divisors. The RSA cryptosystem relies on factoring being hard, so the algorithm has direct consequences for cryptography.
- Integer factorisation
- Order finding
- Period finding
- Modular exponentiation
- Continued fractions
- Greatest common divisor
- RSA cryptography
- 04
Shor's Algorithm: Implementation
This session turns Shor's algorithm into a quantum circuit. It covers the registers the circuit needs and the modular exponentiation step, built from controlled modular multiplications. The inverse quantum Fourier transform comes before measurement. Classical post-processing of the measured results then recovers the period and the factors.
- Quantum circuits
- Quantum registers
- Controlled modular multiplication
- Modular exponentiation circuit
- Inverse quantum Fourier transform
- Classical post-processing