Classical Fourier analysis for the nonabelian hidden subgroup problem

Question

I am hoping to disentangle some subtle distinctions between solving the hidden subgroup problem on a quantum computer and performing classical Fourier analysis on functions on groups valued in fields.

Given a group $G$, a subgroup $H \le G$, and a set $X$, we say $f: G \rightarrow X$ hides $H$ if $f$ is constant on cosets of $H$ and different on distinct cosets.

The function $f$ may be evaluated using an oracle using $\mathcal{O}(\log |G| + \log |X|)$ bits. Using information from the oracle, we want to determine a generating set for $H$.

My confusion is in the set $X$, which seems to have little to no structure. I am most interested in the nonabelian case where $G=S_n$ is the symmetric group. We are essentially using $X$ to label basis states via $x \in X \mapsto | x \rangle$ so that we can create superpositions like $\frac{1}{\sqrt{|G|}}\sum_{g \in G}|g \rangle |f(g)\rangle$.

At that point one can the quantum Fourier transform to try to extract information about $H$ using various coset states.

In practice, what is $X$? For instance, if I define $f_G(\sigma) = \sigma G$ for a graph $G$, I need to represent $G$ via an adjacency matrix (otherwise the unlabeled graph is hard to represent, one would need the orbit under all permutations, or the stabilizer). Adjacency matrices $A$ (labeled graphs) can be represented as $\binom{N}{2}$ ordered bits, so then just integers $k_A$ between 0 and $2^{\binom{n}{2}+1}$. Is $X$ just this finite set of integers?

It seems natural to just embed graphs into a field, say $F_q$ via a generator $\alpha$ for the multiplicative group via $A \mapsto \alpha^{k_A}$. Then $f_G: S_n \rightarrow F_q$ via this embedding $X \rightarrow F_q$. $f_G$ should still be constant on cosets and distinct on different cosets. It seems like one could study $f_G$ using classical nonabelian Fourier analysis over $F_q$. Similarly, one could choose an embedding to $\mathbb{C}$ and study $f_G: S_n \rightarrow \mathbb{C}$.

Is there a reason replacing $X$ by a field and studying the harmonic analysis of $f_G$ is a nonstarter?

Answer 1

Even with the Abelian Hidden Subgroup problem, $X$ need not be integers but instead could be, say, animals or cities and towns or colors or... anything without any structure at all! Colors is the approach that O'Donnell used to lecture on the period-finding algorithm and the HSP; it's also how Shor has briefly described Simon's problem, see his comments at about the 8 minute mark.

Of course, for the specific problem of factoring it's really convenient to have $X$ be integers in $[0, 2^{2n}]$ because we have the very nice and easy-to-calculate function $f(x)=a^x\bmod N$. And, for a putative hidden subgroup algorithm for graph isomorphism, I would probably also choose to work with adjacency matrices and have $\sigma$ swap the columns/rows thereof, but I guess you could also use adjacency lists or any other convenient way to encode graphs, as long as applying $\sigma$ is easy.

The Fourier transform is on the domain of $f$ - we QFT the first register $|x\rangle$ and we discard the second register $|f(x)\rangle$ with entries in $X$. But if there's particular value in having $X$ be replaced by a particular field, then I say go for it! Then again, that might have been what Moore, Russell, and Schulman proposed to do here - they ran into issue with the characters of irreps being too small (or something...)