3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ possible duplicate: cstheory.stackexchange.com/q/3888/4896. also Peter Shor's answer answers your question $\endgroup$
    – Sasho Nikolov
    Apr 13, 2012 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$
    – Mahdi Cheraghchi
    Apr 13, 2012 at 19:34

0

Reset to default