4 ms·
a quantum computer could do it in O(n^.5) with grover's algorithm
by voldacar 6y ago
a quantum computer could do it in O(n^.5) with grover's algorithm
- raldi 6y agoHow would it beat O(1)? Even a quantum computer can't read in the wordlist without looking at every word.
- jordan_curve 6y agoQuantum computers can see information about more than one word with just a single “look.” You’re right to think this is impossible though. Grover’s algorithm was one of the first examples of something that clearly could not ever exist classically.