Grover’s algorithm
Grover's algorithm lets a quantum computer search an unstructured database in square root of n steps rather than n steps, which is the classical cost of checking every entry one by one. Along with Shor's algorithm for factoring large primes, it is one of two foundational quantum algorithms that have driven the bulk of funding and interest in quantum computing.
Transcript
This chapter, from the episode video's captions · 148 words
1:54:51searching of an unstructured database. So if you want to find like where something is, you can do it in square root of n time instead of like n would be you know you got to check every single one to figure out where it is. Square root of n is what he showed. So this is also this can be like you know applied to a various other things. These are the two big algorithms that are the reason why um I think quantum computing has found all of this funding. Specifically, I think shores to be perfectly honest. >> They're they sort of have two fundamental entry points of what they're actually either doing or solving for. One is this sort of large factoring large primes and the other is like uh un
1:55:35like some unbounded database search or bounded database search. >> Yeah. Um and
From How Quantum Computing Actually Works (Part 1)
Part I of our quantum computing deep dive traces the field from Bell and Feynman to Deutsch and Shor—and explains what quantum computers actually do differently from classical machines.