See, I've heard this before. But it really doesn't mean anything to most people. The only concrete example I can think of is cracking modern encryption.
Does anybody have any ideas that would be useful to everyday life? I'm 100% sure that there are a ton.
Well unless users work for NSA, are somehow aware of encryption algorithms, are concerned about protecting their data, or are interested in factoring large numbers, this would not interest them much.
Grover's search algorithm however, will speedup searching. It would be possible to search very large databases in a much shorter time : O(sqrt(n)) instead of O(n). Of course, many problems are based on searching so it is hard to enumerate all the possible end-user visible effects of this.
Idealy only an index would be searched. For example when a sorting algorithm is presented, typically we assume that items are just integers.
So if the database itself is huge, one would take a column and feed that into the quantum computer along with a matching function and a search item and the output would be the position of the item in the column.
In general it is assumed that 'items' are integers. That is general enough. But since no practical implementations exist, still we still don't know how it would work in the real world with a real database.
Here is a more in depth (and somewhat dramatic) explanation:
For N, items to be search, it would take log2(N) qubits (that's enough to represent all N states). The matching function would have to be a quantum gate/operator. In other words, matching is performed in the quantum world.
The idea behind quantum algorithms is to encode the input in a set of qubits, then make them interact in a way that creates a superposition of states. A superposition of states can be thought of as sending the input into a 'magic' quantum world, where N qubits simoultaneously represent all 2^N binary states. Then a set of quantum operators (gates) are applied to the state vector, while it is still in this magic quantum world.
All is fine and dandy (provided that we can mentain the whole quantum world in a stable/isolated state). Then the 'sad' part is that once we measure the result and bring it into the 'real' world, the whole 'magic' quantum world collapses on itself, and only one particular state out of 2^N emerges.
The trick is then to apply the quantum operators such that the probability of the quantum world collapsing to one particular 2^N state is increased. In case of Grover's algorithm that is what happens. The quantum operators increase the probability of the quantum state collapsing to the matched index. It is a probabilistic algorithm in the sense that it might have to be run a couple of times.
You can use polynomial time factoring to prove P = NP. Which means you have simultaneously solved a ton of outstanding optimization problems in science and engineering, and would allow for the creation of AI, clean renewable energy and practical space travel. Obviously those innovations would lead to the biggest change in the history of human civilization, and probably would cause lasting world peace.
All from something as "useless" as factoring integers.
True story.
