1. How is Quantum Algorithms and Complexity Theory essentially different from Classical Counterparts?

  2. Also how are non-deterministic Turing Machines(NTM) different from Quantum Turing Machines(QTM)? More precisely, Is there an QTM that can solve the SAT 'fairly fast'?

I wanted to know how are QTMs different from NTMs, for instance we have parallelism in NTMs which (i think) are not exhibited by QTMs, also there are certain class of problems (in linear optics) that the QTMs can solve easier than NTMs..

So, what are their limitations and computational powers?

  • $\begingroup$ PS. Please do not quote the vazirani book :) also, any reference on quantum algorithms and Complexity theory is welcomed $\endgroup$ – Subhayan Aug 29 '13 at 10:54
  • $\begingroup$ What do you know about either model? Can you focus your question? Note that your first and second question are not necessarily related. You also need to state what you mean by "fairly fast". $\endgroup$ – Raphael Aug 30 '13 at 8:27
  • $\begingroup$ edit: 'fairly fast': lets say polynomial time $\endgroup$ – Subhayan Aug 30 '13 at 11:28
  • $\begingroup$ @Raphael I realise that they are different questions, I intentionally merged the two, to avoid multiple questions of similar type... $\endgroup$ – Subhayan Aug 30 '13 at 11:35
  • 1
    $\begingroup$ see also parallelism vs nondeterminism. I think there is at least a conceptual analogy to be made here. NTMs seem to be something like parallelism where the "acceptance" is parallelized but the "nonacceptance" is not. but have not seen this concept/analogy pursued in the literature so far. feel there is probably some interesting [research] question to be asked/pursued here but am not yet able to formulate it myself. also think there may be some conceptual link between QTMs/NTMs... $\endgroup$ – vzn Sep 1 '13 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.