<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions">NP-intermediate problems with efficient quantum solutions</a>  </p>
</blockquote>



<p>Many suspect that quantum computers will not be able to efficiently solve <strong>NP-complete</strong> problems and  thus focus on the class <strong>NPI</strong>. Among the problems regarded as likely canditates to be in <strong>NPI</strong> 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? </p>

CC BY-SA 3.0
2012-04-13T16:20:14.327Z
possible duplicate: http://cstheory.stackexchange.com/q/3888/4896. also Peter Shor's answer answers your question
Sasho Nikolov
CC BY-SA 3.0
2012-04-13T19:34:27.923Z
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.
Mahdi Cheraghchi
<cc.complexity-theory><quantum-computing><np>
Polynomial Quantum Algorithm for Graph Isomorphism?
d. th. man
# Polynomial Quantum Algorithm for Graph Isomorphism?

(Asked by: username_0 on 2012-04-13)

> **Possible Duplicate:**  
> [NP-intermediate problems with efficient quantum solutions](https://cstheory.stackexchange.com/questions/3888/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?

**Tags:** cc.complexity-theory, quantum-computing, np
> **Comments:**
> **username_1**: possible duplicate: http://cstheory.stackexchange.com/q/3888/4896. also Peter Shor's answer answers your question  
> **username_2**: 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.  

---

## 0 answers

