- A group of problems where most can be solved with a quantum algorithm (e.g. Shor’s Algorithm)
Instances of HSP
| Problem | Quantum Algorithm | Abelian? | Polynomial time solution? |
|---|---|---|---|
| Deutsch’s problem | Deutsch’s algorithm; Deutsch-Jozsa algorithm | Yes | Yes |
| Simon’s problem | Simon’s algorithm | Yes | Yes |
| Order finding | Shor’s order finding algorithm | Yes | Yes |
| Discrete logarithm / Factoring | Shor’s algorithm § Discrete logarithms | Yes | Yes |
| Period finding | Shor’s algorithm | Yes | Yes |
| Abelian stabilizer | Kitaev’s algorithm (https://en.wikipedia.org/wiki/Hidden_subgroup_problem#cite_note-4) | Yes | Yes |
| Graph Isomorphism | None | No | No |
| Shortest vector problem | None | No | No |