The story I linked to yesterday on a quantum computing development says this:
If a traditional computer were given the task of looking up a person's phone number in a telephone book, it would look at each name in order until it found the right number.
That's just stupid. The phonebook is in order for a start. So at worst, you'd use a binary search (but there are better things to do than that). That's already "exponentially better" (using their own words).