2 added 59 characters in body
source | link

This question is in a sense the converse of Will quantum computers out-scale classical computers at P-problems?. We know that there are oracle problems (e.g. oracleunstructured search) for which we can prove that quantum computers can only give a fixed polynomial speedup (in that case quadratic) for the number of oracle consultations. Are there any problems where we can prove that quantum computers can only give a constant speedup? Or even rule out a constant greater than 1?

(I'm excluding oracle problems where there's no quantum speedup for the trivial reason that the classical time complexity is already constant!)

This question is in a sense the converse of Will quantum computers out-scale classical computers at P-problems?. We know that there are problems (e.g. oracle search) for which we can prove that quantum computers can only give a fixed polynomial speedup (in that case quadratic). Are there any problems where we can prove that quantum computers can only give a constant speedup? Or even rule out a constant greater than 1?

(I'm excluding problems where there's no quantum speedup for the trivial reason that the classical time complexity is already constant!)

This question is in a sense the converse of Will quantum computers out-scale classical computers at P-problems?. We know that there are oracle problems (e.g. unstructured search) for which we can prove that quantum computers can only give a fixed polynomial speedup (in that case quadratic) for the number of oracle consultations. Are there any problems where we can prove that quantum computers can only give a constant speedup? Or even rule out a constant greater than 1?

(I'm excluding oracle problems where there's no quantum speedup for the trivial reason that the classical time complexity is already constant!)

1
source | link

Are there problems for which quantum computers don't even give a (nontrivial) polynomial speedup?

This question is in a sense the converse of Will quantum computers out-scale classical computers at P-problems?. We know that there are problems (e.g. oracle search) for which we can prove that quantum computers can only give a fixed polynomial speedup (in that case quadratic). Are there any problems where we can prove that quantum computers can only give a constant speedup? Or even rule out a constant greater than 1?

(I'm excluding problems where there's no quantum speedup for the trivial reason that the classical time complexity is already constant!)