<p>I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial time just amazes me.</p>

<p>The only real knowledge I have about the model is stuff I picked up from the blog and from recent <a href="http://www.youtube.com/watch?v=SczraSQE3MY" rel="nofollow">youtube</a> video's where Aaronson discusses the subject. I have also recently <a href="http://bigthink.com/ideas/38695" rel="nofollow">read</a> that the first quantum computer was sold.</p>

<p>Now I am wondering, and I hope this is not a stupid question, is quantum computing a turing complete computational model?</p>

<p>Also, how come there is an efficient factoring algorithm and not, say, an efficient algorithm for the graph isomorphism problem? What are the boundaries?</p>

<p>I hope answers will give me a more clear image of quantum computing.</p>

CC BY-SA 3.0
2011-06-15T00:57:02.563Z
This question is probably more suitable for Math.SE. Please read the FAQ.
Kaveh
CC BY-SA 3.0
2011-06-16T16:26:36.407Z
@Kaveh: I'm inclined to thin that a question such as "what are the boundaries of quantum computation?" sounds like a research level question. Granted, this is not my field. Maybe with if the question is sufficiently rephrased to focus on that point, it could be reopened.
Dave Clarke
CC BY-SA 3.0
2011-06-16T22:19:12.217Z
Jeroen, the problem with the question is that it's really a basic question in quantum computing (as to how a TM can simulate a quantum machine for example). It's in scope, but not at the right level, and that's why it got closed.
Suresh Venkat
CC BY-SA 3.0
2011-06-16T22:28:14.847Z
I agree with Suresh. You can find the answer easily by Googling e.g. in the wikipedia article for [Church–Turing thesis](http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis). IIRC, Scott also mentions the answer in the talk. We welcome research-level quantum computing questions, but for more general level question please use Math.SE or Physics.SE.
Kaveh
CC BY-SA 3.0
2011-06-16T22:33:01.600Z
ps: the second question doesn't seem a real one to me, why would you expect that if Factoring is in BQP, GI should be also? If you generally want to learn more about quantum computing, then I would suggest reading a tutorial/lecture notes/textbook, you can find some in the book/lecture notes question on cstheory or in the references part of the Wikipedia article for quantum computing or on Scott's blog. Also check [QWiki](http://qwiki.stanford.edu/).
Kaveh
<computability><quantum-computing>
Are quantum computers turing complete?
codd
# Are quantum computers turing complete?

(Asked by: username_0 on 2011-06-15)

I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial time just amazes me.

The only real knowledge I have about the model is stuff I picked up from the blog and from recent [youtube](http://www.youtube.com/watch?v=SczraSQE3MY) video's where Aaronson discusses the subject. I have also recently [read](http://bigthink.com/ideas/38695) that the first quantum computer was sold.

Now I am wondering, and I hope this is not a stupid question, is quantum computing a turing complete computational model?

Also, how come there is an efficient factoring algorithm and not, say, an efficient algorithm for the graph isomorphism problem? What are the boundaries?

I hope answers will give me a more clear image of quantum computing.

**Tags:** computability, quantum-computing
> **Comments:**
> **username_1**: This question is probably more suitable for Math.SE. Please read the FAQ.  
> **username_2**: @Kaveh: I'm inclined to thin that a question such as "what are the boundaries of quantum computation?" sounds like a research level question. Granted, this is not my field. Maybe with if the question is sufficiently rephrased to focus on that point, it could be reopened.  
> **username_3**: Jeroen, the problem with the question is that it's really a basic question in quantum computing (as to how a TM can simulate a quantum machine for example). It's in scope, but not at the right level, and that's why it got closed.  
> **username_1**: I agree with Suresh. You can find the answer easily by Googling e.g. in the wikipedia article for [Church–Turing thesis](http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis). IIRC, Scott also mentions the answer in the talk. We welcome research-level quantum computing questions, but for more general level question please use Math.SE or Physics.SE.  
> **username_1**: ps: the second question doesn't seem a real one to me, why would you expect that if Factoring is in BQP, GI should be also? If you generally want to learn more about quantum computing, then I would suggest reading a tutorial/lecture notes/textbook, you can find some in the book/lecture notes question on cstheory or in the references part of the Wikipedia article for quantum computing or on Scott's blog. Also check [QWiki](http://qwiki.stanford.edu/).  

---

## 0 answers

