It is thought that Graph Isomorphism, at least the HSP with the symmetric group, is unsolvable on quantum computers. This is a case of the non-abelian HSP.

But if a solution to this problem were to exist, what would it look like? What are some relevant papers on this, if there are any?

For example, what is the minimum number of oracle calls does it need to the $f$ mapping (that maps $\sigma \in S_N$ to $\sigma(G)$)?

Would it need to only prepare the state

$$ \frac{1}{\sqrt{N!}} \sum_{i = 0}^{N! - 1} | \sigma_i \rangle | \sigma_i (G) \rangle $$

and extract just $| \sigma_i (G) \rangle$? This is similar to the methods used in abelian HSP cases, but if a solution were to exist to Graph Isomorphism, would this necessarily lead to it?

Is there any research like this?


1 Answer 1


I wouldn't necessarily say that Graph Isomorphism (GI) is thought to be unsolvable on quantum computers. The consensus among many computer scientists (see e.g. Scott Aaronson) seems to be that GI might as well be in P, which would certainly place it within BQP. However, it seems like making progress on either confirming or denying this would require techniques fundamentally different to what we have currently available.

A particular way to solve GI for two graphs $G,H$ might be to construct the state (ignoring normalization) $$ |0\rangle \sum_{i=1}^{n!}|\pi_i(G)\rangle + |1\rangle\sum_{i=1}^{n!}|\pi_i(H)\rangle$$ and perform a SWAP test on the first register. Here $\pi_i(G)$ are permutations of the adjacency matrix of $G$. It is however not clear how to efficiently construct such a state.

  • $\begingroup$ Thanks for the answer, it provided me with some good resources. But is the solution method you provided (that we cannot construct the state for) seems to be for Graph Isomorphism, not the HSP on the symmetric group, and these are not exactly equivalent problems right? $\endgroup$ Commented May 10, 2023 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.