9.6 Amplitude amplification

Suppose we have three qubits and the standard basis kets for them each correspond to a possible solution to some problem. We want to devise an algorithm that chooses the best solution among them. I’m purposely not telling you what the problem is or how the kets map to the data and solution. Just assume we want to identify one of them that the algorithm can determine as best.

The first question is how to see that this best ket stands out from another. The general form for a 3-qubit register state is

with

If we initialize each qubit to |0⟩ and then apply H^⊗3, we get a balanced superposition via a change of basis

All the coefficients are equal and the square of each absolute value is 1/8. If we measure the qubits now, we have an equal chance of getting any one of the eight basis kets. At the qubit level, we have done a change of basis from the computational basis {|0⟩, |1...