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.


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$ Commented Feb 15, 2022 at 14:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sam Jaques
    Commented Feb 15, 2022 at 15:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sam Jaques
    Commented Feb 15, 2022 at 15:24
  • $\begingroup$ 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? $\endgroup$ Commented Feb 15, 2022 at 15:56
  • $\begingroup$ Sorry, I understood: after measuring the second register, the first is in a coset state! So Van den Nest is right. $\endgroup$ Commented Feb 15, 2022 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.