Do we know any function which has same quantum and classical time complexity (bounded error), or at least same upper bound? Of course, let's rule out trivial functions like the constant function, and may be assume the time complexity of the desired function be at least polynomial in input size.

  • $\begingroup$ There are infinitely many upper bounds and any pair of functions $f$ and $g$ have the common upper bound $f(n)+g(n)$ (and infinitely many other ones). So "the same upper bound" doesn't actually make sense. $\endgroup$ – David Richerby Oct 15 '18 at 17:51
  • $\begingroup$ What I mean is that the best known classical and quantum algorithm being same for some well studied function. $\endgroup$ – user189803 Oct 15 '18 at 18:16

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.