Possible Duplicate:
NP-intermediate problems with efficient quantum solutions

Many suspect that quantum computers will not be able to efficiently solve NP-complete problems and thus focus on the class NPI. Among the problems regarded as likely canditates to be in NPI are factoring and graph isomorphism. Known yet Shor's algorithm for efficient factorization, what steps have been done towards the design of a polynomial algorithm for graph isomorphism?


marked as duplicate by Tsuyoshi Ito, Kaveh Apr 13 '12 at 19:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ possible duplicate: cstheory.stackexchange.com/q/3888/4896. also Peter Shor's answer answers your question $\endgroup$ – Sasho Nikolov Apr 13 '12 at 16:20
  • $\begingroup$ GI reduces to the hidden subgroup problem over symmetric group. Quantum polynomial time algorithms are known for any abelian group. However the symmetric group case is still open. $\endgroup$ – MCH Apr 13 '12 at 19:34