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!)

  • $\begingroup$ I seriously doubt we can prove anything like that, unless it's a black box problem. Note that constant speedup doesn't really make sense, since we ignore multiplicative constants (for good reason!) when analyzing the complexity of algorithms. We don't really want to come up with an instruction set and count execution time. $\endgroup$ – Yuval Filmus Mar 26 '18 at 21:03
  • $\begingroup$ @YuvalFilmus That's a very good point. I've edited my question to clarify that I'm counting oracle consultations rather than time steps. $\endgroup$ – tparker Mar 27 '18 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.