0
$\begingroup$

Grover's algorithm searches an unstructured database (or an unordered list) with N entries. what type of data it works on? will it be possible to search data about some images that is stored in database?

$\endgroup$
4
$\begingroup$

The Grover algorithm in its simplest form searches a list of $N$ bits for an occurrence of a bit with value 1. If a 1 is present, Grover will find one with high probability in $O(\sqrt{N})$ steps.

While this seems quite specific, the algorithm is actually applicable in a variety of settings. For example, say you want to search in a image database for an image that contains a cat. Let us assume that there is some algorithm $CAT$ that will decide whether a given image contains a cat, outputting a 1 on input $Img$ if a cat is found in $Img$. Suppose $CAT$ requires $S$ steps per image. Then instead of running $CAT$ on all $N$ images (for $NS$ total work), we can run Grover search on the list of $N$ bits, computing the bits only when required by the Grover algorithm. These various calls to the $CAT$ routine are applied in quantum superposition, and the total work required is $O(\sqrt{N}\cdot S)$, a substantial savings.

Of course, the technology needed to implement Grover search and the superposition of subroutine calls does not yet exist, except perhaps in embryonic form. Hopefully it will become possible in our lifetimes.

$\endgroup$
1
  • $\begingroup$ "The Grover algorithm in its simplest form searches a list of N bits for an occurrence of a bit with value 1". Why can we just check equality? $\endgroup$ – 1.. Dec 24 '16 at 3:01

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.