What is known about the 'structure' of the solution for Graph Isomorphism on quantum computers?

Question

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?

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.