3 ms·
Quantum computers SHOULD destroy regular computers at knapsack style problems and other combinatorial explosions. The problem there is that decomposing real wo
by CuriouslyC 3y ago
Quantum computers SHOULD destroy regular computers at knapsack style problems and other combinatorial explosions. The problem there is that decomposing real world problems into 128bit combinatorial selection is really hard.
- cwillu 3y agoThere's no reason to think that quantum computers will have any fundamental advantage at knapsack problems; the √n advantage from grovers is not substantial when classical computers are going to be many orders of magnitude bigger than quantum computers for the foreseeable future. If a problem can be reduced to efficiently sampling from the summation of an exponentially large numbers of FFT's, then a quantum computer will destroy a classical computer. It's largely an open research problem whether there are useful quantum algorithms between those two problem classes.
- fooker 3y ago>Quantum computers SHOULD destroy regular computers at knapsack style problems and other combinatorial explosions. You can get a Turing award if you can show this, even theoretically.