<p>Even with the Abelian Hidden Subgroup problem, <span class="math-container">$X$</span> 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 <a href="https://www.youtube.com/watch?v=x8i6qs8uAog&amp;t=1538s" rel="nofollow noreferrer">period-finding algorithm and the HSP</a>; it's also how Shor has briefly <a href="https://www.youtube.com/watch?v=6qD9XElTpCE" rel="nofollow noreferrer">described Simon's problem</a>, see his comments at about the 8 minute mark.</p>
<p>Of course, for the <em>specific</em> problem of factoring it's really convenient to have <span class="math-container">$X$</span> be integers in <span class="math-container">$[0, 2^{2n}]$</span> because we have the very nice and easy-to-calculate function <span class="math-container">$f(x)=a^x\bmod N$</span>. And, for a putative hidden subgroup algorithm for graph isomorphism, I would probably also choose to work with adjacency matrices and have <span class="math-container">$\sigma$</span> 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 <span class="math-container">$\sigma$</span> is easy.</p>
<p>The Fourier transform is on the <em>domain</em> of <span class="math-container">$f$</span> - we QFT the first register <span class="math-container">$|x\rangle$</span> and we discard the second register <span class="math-container">$|f(x)\rangle$</span> with entries in <span class="math-container">$X$</span>.  But if there's particular value in having <span class="math-container">$X$</span> 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 <a href="https://arxiv.org/abs/quant-ph/0501056" rel="nofollow noreferrer">here</a> - they ran into issue with the characters of irreps being too small (or something...)</p>

CC BY-SA 4.0
2024-07-18T23:00:44.570Z
Right, we are applying the QFT to the first register after putting it in the "coset state" $|x+H\rangle$. Forming such a coset classically is difficult/impossible, and (to partially answer my question) the classical DFT is exponential in $n$. I am familiar with Moore et. al's paper, and I believe they are just using the QFT for $S_n$ over $\mathbb{C}$. The distribution of $\chi_\rho([m])/d_\rho$ is too close to 1 where $m$ is an involution (providing the automorphism). My hope was the (modular) rep'n of $S_n$ over $F_q$ would be better, or at least different than over $\mathbb{C}$.
Jackson Walters
CC BY-SA 4.0
2024-07-18T23:20:06.217Z
I think you know a lot more about this than I do! But it is an interesting question as to what other mappings and other applications of the HSP exist.
Mark S
CC BY-SA 4.0
2024-07-19T00:59:01.203Z
I don't know about that, but definitely the HSP is at the center of many things. Still curious if the subgroup hiding function has been studied outside the realm of quantum algorithms.
Jackson Walters
CC BY-SA 4.0
2024-07-18T21:15:52.693Z
2024-07-18T21:15:52.693Z
Mark S
<p>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.</p>
<p>Given a group <span class="math-container">$G$</span>, a subgroup <span class="math-container">$H \le G$</span>, and a set <span class="math-container">$X$</span>, we say <span class="math-container">$f: G \rightarrow X$</span> hides <span class="math-container">$H$</span> if <span class="math-container">$f$</span> is constant on cosets of <span class="math-container">$H$</span> and different on distinct cosets.</p>
<p>The function <span class="math-container">$f$</span> may be evaluated using an oracle using <span class="math-container">$\mathcal{O}(\log |G| + \log |X|)$</span> bits. Using information from the oracle, we want to determine a generating set for <span class="math-container">$H$</span>.</p>
<p>My confusion is in the set <span class="math-container">$X$</span>, which seems to have little to no structure. I am most interested in the nonabelian case where <span class="math-container">$G=S_n$</span> is the symmetric group. We are essentially using <span class="math-container">$X$</span> to label basis states via <span class="math-container">$x \in X \mapsto | x \rangle$</span> so that we can create superpositions like <span class="math-container">$\frac{1}{\sqrt{|G|}}\sum_{g \in G}|g \rangle |f(g)\rangle$</span>.</p>
<p>At that point one can the quantum Fourier transform to try to extract information about <span class="math-container">$H$</span> using various coset states.</p>
<p>In practice, what is <span class="math-container">$X$</span>? For instance, if I define <span class="math-container">$f_G(\sigma) = \sigma G$</span> for a graph <span class="math-container">$G$</span>, I need to represent <span class="math-container">$G$</span> 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 <span class="math-container">$A$</span> (labeled graphs) can be represented as <span class="math-container">$\binom{N}{2}$</span> ordered bits, so then just integers <span class="math-container">$k_A$</span> between 0 and <span class="math-container">$2^{\binom{n}{2}+1}$</span>. Is <span class="math-container">$X$</span> just this finite set of integers?</p>
<p>It seems natural to just embed graphs into a field, say <span class="math-container">$F_q$</span> via a generator <span class="math-container">$\alpha$</span> for the multiplicative group via <span class="math-container">$A \mapsto \alpha^{k_A}$</span>. Then <span class="math-container">$f_G: S_n \rightarrow F_q$</span> via this embedding <span class="math-container">$X \rightarrow F_q$</span>. <span class="math-container">$f_G$</span> should still be constant on cosets and distinct on different cosets. It seems like one could study <span class="math-container">$f_G$</span> using classical nonabelian Fourier analysis over <span class="math-container">$F_q$</span>. Similarly, one could choose an embedding to <span class="math-container">$\mathbb{C}$</span> and study <span class="math-container">$f_G: S_n \rightarrow \mathbb{C}$</span>.</p>
<p>Is there a reason replacing <span class="math-container">$X$</span> by a field and studying the harmonic analysis of <span class="math-container">$f_G$</span> is a nonstarter?</p>

<quantum-computing><fourier-analysis>
Classical Fourier analysis for the nonabelian hidden subgroup problem
Jackson Walters
# Classical Fourier analysis for the nonabelian hidden subgroup problem

(Asked by: username_0 on 2024-07-10)

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?

**Tags:** quantum-computing, fourier-analysis

---

## 1 answers

### Answer by username_1 on 2024-07-18. Score: 2

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](https://www.youtube.com/watch?v=x8i6qs8uAog&t=1538s); it's also how Shor has briefly [described Simon's problem](https://www.youtube.com/watch?v=6qD9XElTpCE), 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](https://arxiv.org/abs/quant-ph/0501056) - they ran into issue with the characters of irreps being too small (or something...)

> **Comments:**
> **username_0**: Right, we are applying the QFT to the first register after putting it in the "coset state" $|x+H\rangle$. Forming such a coset classically is difficult/impossible, and (to partially answer my question) the classical DFT is exponential in $n$. I am familiar with Moore et. al's paper, and I believe they are just using the QFT for $S_n$ over $\mathbb{C}$. The distribution of $\chi_\rho([m])/d_\rho$ is too close to 1 where $m$ is an involution (providing the automorphism). My hope was the (modular) rep'n of $S_n$ over $F_q$ would be better, or at least different than over $\mathbb{C}$.  
> **username_1**: I think you know a lot more about this than I do! But it is an interesting question as to what other mappings and other applications of the HSP exist.  
> **username_0**: I don't know about that, but definitely the HSP is at the center of many things. Still curious if the subgroup hiding function has been studied outside the realm of quantum algorithms.  

---

