There'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.
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.