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 video's where Aaronson discusses the subject. I have also recently read 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.

  • 1
    $\begingroup$ This question is probably more suitable for Math.SE. Please read the FAQ. $\endgroup$ – Kaveh Jun 15 '11 at 0:57
  • 1
    $\begingroup$ @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. $\endgroup$ – Dave Clarke Jun 16 '11 at 16:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Jun 16 '11 at 22:19
  • $\begingroup$ I agree with Suresh. You can find the answer easily by Googling e.g. in the wikipedia article for Church–Turing 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. $\endgroup$ – Kaveh Jun 16 '11 at 22:28
  • $\begingroup$ 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. $\endgroup$ – Kaveh Jun 16 '11 at 22:33