Similar to this list over at cstheory, I'm looking for a list of computational problems in the query complexity model for which it is known that no super-polynomial quantum speedups exist. What are some natural problems for which quantum computers are known to have only 'limited' advantage?


1 Answer 1


Disclaimer: I am not sure if this is your are looking for, so I do not pretend this to be an answer.

As far as I know, one example is calculation of a binary function parity. Binary function has odd parity in case it returns one for odd number of inputs. In other case it has even parity. In this task, a quantum computer is as fast as classical computer.

  • 1
    $\begingroup$ This is an excellent first entry for the list, thank you! $\endgroup$
    – gen
    Feb 9, 2021 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.