Grover's Algorithm/Superposition?

[Bonham]

Hello everyone. I'm only just starting to look into degree programs for physics, so this question may not be worded well, or make much sense. Hopefully it does.

According to a couple of books I've read, you could theoretically search a large database for specific entries in a quantum computer using Grover's Algorithm. This involves using laser pulses to find the correct entry, inverting it's wavelets, and then inverting the system about the average until the correct entry's amplitude is high enough for the system to collapse from superposition into it with high accuracy.

It's my understanding that if an atom in superposition is measured or observed in any way, the superposition will collapse immediately. My question is, how is it possible to search for the correct entry using laser pulses without causing to superposition to collapse?

 

[Zarqon]

Yo uare right in that the superposition will collapse upon measurement, but bear in mind that you need many qubits to perform the search. As a very simplified example, let's say that you want to search a database with 1 million posts in it. Then you need 20 qubits just to be able to represent a million different states (classical states, as 2^20 > 10^6). During the quantum information processing, all the 20 qubits will be in a large superposition, where all are entangled with each other. After the processing is complete, you do your read out, and the state with the highest probability amplitude should be your desired state.

Though note that the quantum computer is probabilistic and that you in general do not have a 100% chance of finding the right state, but rather that as you measure and collapse the superposition, the right state has the highest probability of being measured after the collapse. One would then have to redo the computation several times in order to gain statistics of which state has the highest probability.

Also note that this picture is greatly simplified, for example to actually do the computation you would need a lot more than 20 qubits, because you also need temporary qubits during the computation, but that's another story.

Hope that helped.