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).
- is there a more concise and correct statement about where quantum computing can help?
- 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...)