# Quantum algorithm for hidden subgroup problems: question on cosets

We have a group $$G$$ and a function $$f$$ which hides a subgroup $$H$$, and we want to find $$H$$. The quantum algorithm for solving the problem involves the use of two registers, initially at $$\left|0,0\right>$$. Hadamard gates are applied to the first, then the following operation is performed: $$\left|g,y\right> \to \left|g, y+f(g)\right>$$

It is claimed that the resulting state is related to a coset state of $$H$$. This should mean a uniform superposition of $$\left|k+x\right>$$, with a fixed $$x\in G$$ and any $$k\in H$$. However, this relation is not explicitly written. In particular, in this paper by Van den Nest, an even more puzzling claim is made, i.e. that the state is actually a "mixture" $$\rho$$, see eq. 9, where $$\rho$$ is actually an operator. I do not see how a "mixture" can be generated by the above operations. Unfortunately, the claim is cited as "it is well known that" without citations.

I'm asking for a clarification of the relation between the obtained state and the coset states of $$H$$. An example with factorization is welcome.

Consider that if we enumerate the cosets of $$H$$ as $$g_0+H,g_1+H,\dots, g_n+H$$, then every $$g\in G$$ can be written as $$g_i+h$$ for some $$i$$ and some $$h\in H$$, and this correspondence is 1-to-1. This means we can write (ignoring normalization)

$$\sum_{g\in G}\vert g\rangle = \sum_{i=0}^n\sum_{h\in H}\vert g_i+h\rangle$$

which hasn't changed the state at all, just changed how we write it.

Using this expression for a uniform superposition over $$G$$, the map you have above will have the action of

$$\sum_{i=0}^n\sum_{h\in H}\vert g_i+h\rangle\vert y\rangle \mapsto \sum_{i=0}^n\sum_{h\in H}\vert g_i+h\rangle \vert y + f(g_i+h)\rangle$$

By assumption on $$f$$ (and this assumption is critical for this to work), $$f$$ is constant on cosets, so $$f(g_i+h)=f(g_i+h')$$ for all $$h,h'\in H$$. Let's denote this value as $$f(g_i)$$ for simplicity. This means we can rewrite the state above as:

$$\sum_{i=0}^n\underbrace{\sum_{h\in H}\vert g_i+h\rangle}_{(*)} \vert y + f(g_i)\rangle$$

but now we notice that the second register has no dependence on the sum over $$H$$. This means the term $$(*)$$ is exactly a coset state $$\vert g_i+H\rangle$$. Thus, we can rewrite it as

$$\sum_{i=0}^n \vert g_i+H\rangle \vert y+f(g_i)\rangle$$

where the presence of coset states is clear.

Generally, mapping a single state $$\vert g\rangle \vert y\rangle$$ to $$\vert g\rangle \vert y+f(g)\rangle$$ won't involve coset states, because we don't have a superposition over the right set. But in the HSP, we always start with a uniform superposition, so that's where the coset states come from.

In the paper you cite, when it says "the state $$\rho$$ of register 1", they mean that we are taking the partial trace of the second register (effectively measuring it). If you do that, you will get a mixed state, exactly as they describe in Equation 9.

• The explanation is very clear. Can I ask an additional clarification about the connection with factorization? According to your explanation, it is critical that the first register is actually a superposition of $\left|g\right>$ with $g\in G$. In Shor's algorithm, it is prepared as a superposition of all the elements of $\mathbb{Z}_{2^m}$; in a later stage, we also make the Fourier transform on $\mathbb{Z}_{2^m}$. So it seems that $G$ is $\mathbb{Z}_{2^m}$, while I was expecting to look for subgroups of $\mathbb{Z}_N$, with $N$ the number to factor. Are the two algorithms completely different? Feb 15, 2022 at 14:52
• Consider that each element $a\in\mathbb{Z}_N^*$ can be represented by any integer $A$ such that $A\equiv a \mod N$. So first, imagine we have a "double superposition", i.e., a superposition of integers so that we have exactly 2 integers $A_1,A_2$ in superposition for every $a\in \mathbb{Z}_N^*$. First, convince yourself that the setup will also give us something like the coset states described. Next, imagine that the superposition isn't perfect: maybe we miss a few states in the superposition. Then we approximately get coset states. Feb 15, 2022 at 15:21
• Finally, a superposition over $\mathbb{Z}_{2^m}$ combines these two ideas: We choose $m$ large enough that we get many representatives of each element in $\mathbb{Z}_N^*$. The number of representatives will vary a bit for each element (since $2^m$ is not exactly a multiple of the order of the group) but that just means we get approximately the right state. We imagine we choose $m$ large enough that the approximation is good enough to measure the right phase in the end with high probability. Feb 15, 2022 at 15:24
• Again very clear. I promise, this is my last question. Van den Nest notices that the state is a superposition of coset states. Then he claims that we can use the theorem 1, which requires a coset state (not a superposition) to conclude that the state, after the final Fourier transform, can be calculated classically efficiently, provided that $H$ is known. Do you think he is correct? Feb 15, 2022 at 15:56
• Sorry, I understood: after measuring the second register, the first is in a coset state! So Van den Nest is right. Feb 15, 2022 at 18:22