<p>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. </p>

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

<p>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.</p>

CC BY-SA 3.0
2017-05-02T22:29:05.290Z
2017-05-02T22:29:05.290Z
kodlu
<p>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?</p>

<p>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).</p>

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

<p>are there relevant papers that discuss just that?</p>

<p>(sorry, new here. hope that question is appropriate &amp; understandable and there is not too much wrong in my statements...)</p>

CC BY-SA 3.0
2018-04-04T00:40:45.173Z
You can ask this question at: https://quantumcomputing.stackexchange.com/ .
Rob
CC BY-SA 3.0
2018-04-04T06:20:10.633Z
@Rob thanks! did that: https://quantumcomputing.stackexchange.com/questions/1584/general-statement-what-kinds-of-problems-can-be-solved-more-efficiently
hiro protagonist
<quantum-computing>
general statement what kinds of problems can be solved more efficiently
hiro protagonist
# general statement what kinds of problems can be solved more efficiently

(Asked by: username_0 on 2017-05-02)

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

**Tags:** quantum-computing
> **Comments:**
> **username_1**: You can ask this question at: https://quantumcomputing.stackexchange.com/ .  
> **username_0**: @Rob thanks! did that: https://quantumcomputing.stackexchange.com/questions/1584/general-statement-what-kinds-of-problems-can-be-solved-more-efficiently  

---

## 1 answers

### Answer by username_2 on 2017-05-02. Score: 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.


---

