<p>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.</p>

<p>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 <em>only when required</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-12-24T03:01:09.210Z
"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?
Turbo
CC BY-SA 3.0
2013-11-27T22:42:37.890Z
2013-11-27T22:42:37.890Z
Andy Drucker
<p>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?</p>

<it.information-theory>
grover's algorithm
sanjay palit
# grover's algorithm

(Asked by: username_0 on 2013-11-27)

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?

**Tags:** it.information-theory

---

## 1 answers

### Answer by username_1 on 2013-11-27. Score: 4

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.

> **Comments:**
> **username_2**: "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?  

---

