Hacker News Reader

Comment by erikaww | Hacker News Reader

I'm not educated on QC. But wouldn't Grover's algorithm be very useful? I believe it provides a sqrt(n) time search. For QC to be useful,it just needs to make common utilities very fast. I should look more into QC. It would be cool if it could speed all computation up. I understand there are algorithms that it could execute that a classical composer could not, but I wonder if it could eventually he like just faster hardware.

View on HN

Most general purpose computing is based on algorithms that are essentially O(n).

What that means is that they are a constant times the cost of simply reading the input. Often, the computation is actually cheaper.

Quantum computing might make some computations have a smaller theoretical constant, but it is almost certain that the practical constant ($/bit of input) will be much, much worse due to scale.

Right now, only very specialized computations look like they will ever have any speedup. And even that is only maybe, in practice.

According to a recent article [1], quadratic quantum speedups are very unlikely to outperform classical computers in any application. This is assuming very optimistic parameters for future quantum computers. Grover's algorithm is therefore not considered useful in practice.

[1] https://doi.org/10.1145/3571725

To load those bits into your quantum computer, you need to spend O(n) time. Most practical searches are O(n).

Not neccesarily, you can calculate them on the fly.

How so you mean calculating them on the fly? You need to at least load the data to perform operations on it.

Grover's algorithm does not require you to load the data to be searched through if it can be generated instead. Grover's algorithm is not neccesarily searching through a list but searching through the output of a function. Sure if your function is an array index operator you need to load the underlying data, but many large search problems are not that.

That clears that up thanks.

I think you have to scale very big before that starts to matter.

Reply on news.ycombinator.com