On page 14 of his classic paper, Quantum factoring, discrete logarithms and the hidden subgroup problem, Jozsa introduced a function $f$ for the non-abelian hidden subgroup representation of the graph isomorphism problem. I would like to quote him here.
In our standard algorithm the function $f$ used to generate the random coset state $|g_0 K \rangle$ is the efficiently computable $f : G \to > X$ where $X$ is the set of all matrices of size $2n \times 2n$ with $0,1$ entries and $f(\Pi)$ is the matrix obtained by permuting the rows and columns of $M_C$ by $\Pi$.
My question is:
- How is $|g_0 K \rangle$ created? If we are checking two $n$ node graphs, how many qubits are required to construct the state?