This is the workhorse subroutine of quantum computing — the engine inside Shor, inside quantum chemistry, inside linear-systems solvers. Its whole job: a gate U hides a phase φ in its eigenvalue, and phase estimation reads that number out in binary. It is simply kickback and the inverse QFT, bolted together.
A unitary spins its eigenstate by some angle and otherwise leaves it alone. That angle is the gate’s hidden number. Phase estimation gathers many copies of that spin into a counting register — doubling the dose for each qubit — so the register ends up winding at rate φ. Then the inverse QFT collapses that winding into a sharp peak at the bin closest to φ. Measure, divide, and you’ve read the number.
You can’t read a clock’s rate from a single glance, but watch the second hand for a while and you can time it precisely. Phase estimation does the same: it lets the gate “tick” 1, 2, 4, 8… times into different qubits, so the slow-moving high bits and fast-moving low bits together pin down the rate. The inverse QFT is the read-off: it converts the accumulated ticking into a number on a dial.
Set the gate’s true phase φ and the number of counting qubits n. The bars show the probability of each possible readout. When 2ⁿφ is a whole number you get one perfect spike; otherwise the peak sits at the nearest bin, with a little spread. Add qubits to sharpen it.
Put the n counting qubits in |+⟩ and the target in the eigenstate |u⟩. Each controlled-U2ᵃ kicks back the phase of that many U’s. After all of them the counting register holds exactly the QFT of the number 2ⁿφ:
That winding state is precisely what the QFT was designed to read. So phase estimation = kickback writes the rate in, inverse QFT reads the number out. Each extra counting qubit doubles the bins, adding one more bit of φ.
“You must already have the eigenstate.” Helpful, but not required. Feed any state — it’s a blend of eigenstates — and the algorithm returns one of their phases at random, weighted by how much of that eigenstate was present. Shor exploits exactly this.
“More counting qubits always means more accuracy for free.” They add resolution, but each also demands applying U up to 2ⁿ times — the cost grows too. And on noisy hardware those long controlled-U powers are the hard part.
“If 2ⁿφ isn’t a whole number the algorithm fails.” It still works — you just get a peaked distribution around the true value, and the most likely outcome is the closest bin. A few repeats nail it down.