3 ms·
Here's my rather crude understanding of what QC can do (please feel free to comment if this is correct): Let's say you have a problem that requires examining 2^
by sytelus 9y ago
Here's my rather crude understanding of what QC can do (please feel free to comment if this is correct): Let's say you have a problem that requires examining 2^N different possibilities. So the brute force solution would have O(2^N) runtime. QC can potentially help to solve this problem in O(2^(sqrt(N))) time instead. This can make a world of difference. For example, if N=1024 and examining each possibility took 1 nanosecond, it would still exceed the time far far more than age of universe. With QC with 1024 qubits, it would take 1 microsecond to solve it.
- mercutio2 9y agoUtterly unimportant to your point, but 2^32 nanoseconds is not a microsecond...
- Sniffnoy 9y agoI'm afraid you're a bit off. A quantum computer can search N possibilities (such as when, say, looking up data in a database, though I doubt you'd go to the trouble of using a QC for that) in time O(sqrt(N)). So for 2^N things, that's 2^(N/2), not 2^(sqrt(N)). Obviously still a big improvement.