3
$\begingroup$

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...).

$\endgroup$
3
$\begingroup$

I won't explain the complete algorithm here. You can find a good explanation in Wikipedia or Nielsen and Chuang

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.

Check out Nielsen and Chuang for a really simple explanation. They effectively explain the whole thing in terms of two dimensional vectors.

An alternative way to think about it is using the Schrodinger equation. The Schrodinger Hamiltonian has two terms, the kinetic energy term and the potential energy term. If there is no potential then the tendency of the K.E term is to spread out the wave function. What Grover search does is this: A potential is applied to the "marked" states and the system is allowed to evolve according to the Schrodinger Hamiltonian. The potential concentrates the amplitude at the marked states so that when you do a measurement there is a high chance that you will get these states. Grover figured out his algorithm by thinking about it in this way and then discretizing Schrodinger equation. You can find his own explanation along these lines here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user929304 Feb 15 '16 at 15:15
  • $\begingroup$ 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. $\endgroup$ – biryani Feb 15 '16 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.