Reply to post: Re: Uses for quantum computers

Big Blue's quantum rainmaker jumps to room-temp diamond quantum accelerator company

Michael Wojcik Silver badge

Re: Uses for quantum computers

Grover's Algorithm is often described as "database search", but that doesn't mean QC will magically make your SQL SELECTs faster. What Grover's actually does is: Given a function that takes a bit string and returns {0,1}, Grover's will find an input that returns 1 with probability 0.5 by examining N1/2 candidates.

So if you define the function as taking "the parameters of the thing I'm searching for and its index" and the result 1 as "yes, this is the thing I'm searching for", and you keep running Grover's until you get a correct result, then on average you only have to run it twice and examine 2 * \sqrt N to find the thing you're looking for.

Similarly, you can use it to find the key for a symmetric encryption algorithm as long as you have a good oracle for testing candidate keys (e.g. a known plaintext prefix). There are various other applications.

But it only gives a quadratic speedup, and it's useful for unstructured search of the domain. For "databases" in the common sense, we already have O(lg N) indices, so a quadratic speedup is worse (much worse if N is large, obviously). And for breaking symmetric keys, even if your QC is as fast as the fastest conventional computer (which it will not be), doubling the key length kills the quantum advantage.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2021