Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58
Ian Goldberg (iang@CS.Berkeley.EDU)
11 Aug 1998 18:03:57 GMT
In article <199808110440.GAA09692@replay.com>,
Anonymous <nobody@replay.com> wrote:
>It might be interesting to see how this would apply to hash collisions,
>if Grover doesn't discuss it. Hash collisions are already a square root
>problem. They wouldn't seem to fit into the Grover algorithm model where
>you are searching a database for a match to a given value. Instead, you
>want to find two matching values in a large database. Can you do better
>than the square root?
Yes. Grover's algorithm finds hash collisions in O(cuberoot(n)) time.
- Ian
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58