Quantum Computing and Communications: An Engineering Approach

7

Searching in an Unsorted Database

In order to survive from day to day in a very hostile and dangerous environment prehistoric men spent most of their time seeking for such resources as food, fresh water, suitable stones for tools, etc. The world around us was nothing more than a large unsorted database. Efficiency of the two basic methods, namely random and exhaustive search, proved to be rather poor. The only way to achieve some improvement was the involvement of more people (parallel processing). The first breakthrough in this field can be connected to the first settlements and the appearance of agriculture which brought along the intention to make and keep order in the world.¹ A field of wheat or a vegetable garden compared to a meadow embodied the order which increased the probability of successful searching almost up to 1. Therefore our ancestors were balancing during the last 10 thousand years between the resource requirement of making order and seeking for a requested thing. However, at the dawn of the third millennium our dreams seem to become true due to quantum computing. Grover's database search algorithm enables a dramatic reduction in the computational complexity of seeking in an unsorted database. The change is tremendous, the classically required O(N) database queries when we have N different entries has been replaced by steps using quantum computers.

We follow ...