# Understanding amplitude amplification in quantum computing

In short, what is the essence of amplitude amplification type of techniques that appear in quantum computing?

More precisely, my main questions are, relating them more to Grover's search which employs amplitude amplification: ($\mathcal{H}$ being the Hilbert space of the system)

• We start with some eigenstate $|0\rangle$, run the system through a Hadamard gate $H$, thus changing the state to a coherent superposition $|\psi\rangle$ of possible eigenstates $|x_i\rangle$ (with $i=1,\cdots \text{dim} \mathcal{H}$), then having a target eigenstate $|x_t\rangle$ in mind (whose amplitude we want to amplify in the superposition), an iterative process of rotations of the state around different axes starts (one of them being the target state), but what is really going on? How is it that we can reach $|x_t\rangle$ by rotating $|\psi\rangle$ around a set of well-defined axes, but we could not have set up our system in the $|x_t\rangle$ to begin with?

• At first glance it looks a bit paradoxical, because my understanding of rotation operators is that they are represented by unitary operators, i.e. operators that preserve inner products. But surely if we are changing the amplitudes of different states in the superposition, we are in turn not preserving inner products. So does this mean that the overall transformation is non-unitary? If yes, how is it possible to transform the system in a non-unitary way whilst preserving coherence (i.e. not collapsing the system to one of its eigenstates in the process)?

• It would be incredible if someone could give a dumbed-down account of the main ideas that make amplitude amplification possible. (to see what is really going on...).

The aim of Grover search is to find some "marked" items ($|x_t\rangle$) in an unstructured database. The "marking" is done by a function called the oracle. The problem you are trying to solve is - 'Given an oracle can you find the items it marks in a database?'. The ability to implement the oracle doesn't imply that we can construct $|x_t\rangle$. And at times you will not even have the freedom to construct an initial state. For example when you use Grover search as an intermediate step in some other algorithm
It is not paradoxical. If you look at the intermediate steps closely all operations involved are unitary. So the entire algorithm is also unitary. The source of your confusion may be this: Initially $\langle \psi | x_t\rangle$ was small but the algorithm amplifies this value. It is not a contradiction because unitary transformations preserve inner products if you apply them to both the vectors (i.e. rotation of the whole space). But here we change $| \psi \rangle$ and not $|x_t\rangle$. The amplification here happens the same way how the x-component of a 2D vector can change when you rotate it keeping the axes fixed.
• Thanks a lot, you clarified all my confusions! I guess the dim of the Hilbert space should be as large as the size of the database (at least if we want fully disinguishable states), then are we always able to build a Hadamard gate regardless of what dim H is? In order to transform our state into a uniform superposition of all eigenstates, so that the overkap with $|x_t\rangle$ is non-zero. – user929304 Feb 15 '16 at 15:15
• Yes, Dimension of H is the size of the data base. For dimensions which are powers of 2 we can build the Hadamard gate using single qubit Hadamard gates. For other cases you may have to do something else. Like a Fourier transform on $|0 \rangle$ perhaps. More efficient ways may exist. – biryani Feb 15 '16 at 15:46