3 ms·

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 c

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.

bawolff 3y ago
I think you have to scale very big before that starts to matter.
fsh 3y ago
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 https://doi.org/10.1145/3571725
ted_dunning 3y ago
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.
pclmulqdq 3y ago
To load those bits into your quantum computer, you need to spend O(n) time. Most practical searches are O(n).
- bawolff 3y ago
  Not neccesarily, you can calculate them on the fly.
  - zerodensity 3y ago
    How so you mean calculating them on the fly? You need to at least load the data to perform operations on it.
    - bawolff 3y ago
      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.
      - zerodensity 3y ago
        That clears that up thanks.

bawolff 3y ago

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

fsh 3y ago

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 https://doi.org/10.1145/3571725

ted_dunning 3y ago

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.

pclmulqdq 3y ago

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

bawolff 3y ago
Not neccesarily, you can calculate them on the fly.
- zerodensity 3y ago
  How so you mean calculating them on the fly? You need to at least load the data to perform operations on it.
  - bawolff 3y ago
    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.
    - zerodensity 3y ago
      That clears that up thanks.