[jules]

The 'database' is not really a database in the sense that it stores a list of things. Instead the database is like a predicate p(x) where x ranges over some finite set (you can assume that this set is just 0..N). So if p(x) really has to search a database to determine whether x is the one you want, then the algorithm doesn't work. It is assumed that executing p(x) is fast. Classically you'd have to call the predicate on each of 0..N to find the x for which p(x) = 1. In a quantum computer you can start with a superposition of all states 0..N (think probability distribution over 0..N), and by cleverly applying a quantum analog to a predicate p in Grover's algorithm you can change this probability distribution so that the x for which p(x) is true gets more and more likely (i.e. more and more probability mass). This probability mass increases fast enough that on average you need O(sqrt(N)) steps to find the x that satisfies p(x).