is there a general statement what kinds of problems can be solved more efficiently using quantum computers (quantum gate model only)? do the problems for which an algorithm is known today have a common property?

as far as i understand quantum computing helps with the hidden subgroup problem (shor); grover helps speedup search problems. i have read that quantum algorithms can provide speed-up if you look for a 'global property' of a function (grover/deutsch).

  1. is there a more concise and correct statement about where quantum computing can help?
  2. is it possible to give an explanation why quantum physics can help there (preferably something deeper that 'interference can be exploited')? and why it possibly will not help for other problems (e.g. for NP-complete problems)?

are there relevant papers that discuss just that?

(sorry, new here. hope that question is appropriate & understandable and there is not too much wrong in my statements...)


1 Answer 1


My limited understanding is that problems in which cyclic groups or their products play a central role usually have very good (exponential to polynomial complexity) speedups when quantum algorithms are used.

This is due to the fact that the complex Fourier transform plays a central role in the representation of quantum states.

The fact that Grover's search doesn't have this impressive speedup is also due to the fact that it is not tightly related to cyclic groups.


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.