Why does “discarding” a qubit register, in the Hidden Subgroup Problem, give a randomly chosen coset $|x+H\rangle$?

Question

I am reading up on the Hidden Subgroup Problem (HSP), and found this resource by Professor Childs.

I am a bit confused at this part though:

Basically, he’s saying that removing the second register from

$$ \frac{1}{\sqrt{\left | G \right |}} \sum_{x \in G} |x, f(x) \rangle $$

Gives us

$$ |x + H \rangle = \frac{1}{\sqrt{|H|}} \sum_{h \in H} | x + h \rangle $$

I don’t see how this was derived though. Based on what he said, why isn’t it just this:

$$ \frac{1}{\sqrt{|G|}} \sum_{x \in G} |x\rangle $$

I know it doesn’t include the hidden subgroup, but I don’t get how the math checks out in Professor Childs’ formula.

Thanks for any help.

Here is the full excerpt

Answer 1

Let's start from the state (ignoring normalization) $$ |\psi\rangle = \sum_{g \in G} | x\rangle |f(x)\rangle. $$ There are two registers here: the "data" register that stores $x$ and the "result" register which stores $f(x)$. These two registers are entangled, so discarding can't be done trivially. Formally, let $\rho = |\psi\rangle\langle \psi|$, be the density matrix of the two registers. Then the process of discarding result register (labelled 2) leaves the state $\tau = Tr_2[\rho]$, the partial trace over the result register.

You can do this computation, but here is a nicer way of thinking about this. Suppose, instead we measure the result register. To see the outcome of this, realize that in the non-trivial case, there are many different $x\in G$ with the same value for $f(x)$ (which is the whole point of the hidden subgroup).

Suppose, for instance that $y_0,y_1,\dots,y_k \in G$ are such that $$f(y_0) = f(y_0) = \cdots = f(y_k) = F_y.$$ And further suppose that when we measure the result register, we get the value $F_y$. We don't particularly care about this value for our algorithm, so we can just forget/discard it. But note what happens to the first register. If the second register had value $F_y$, the the first register must be left in the state $$ |\phi \rangle = |y_0\rangle + |y_1\rangle + \cdots + |y_k\rangle. $$ How are these $y_i$s related. They are obviously $y_0 + H$. Which gives the desired result.

---

Edit: We can also write $$ |\psi\rangle = \sum_i \left(\sum_{h\in H} |y^{(i)} + h\rangle\right) |f(y^{(i)})\rangle, $$ where $y^{(i)}$ are the representatives of the cosets of $H$ in $G$. This should make clear what happens if measuring the second register yields the value $f(y^{(i)})$.

Answer 2

That description is a bit imprecise. "Discard" really means "measure this register and discard the result". It's impossible to just "discard" registers in quantum computing if they are entangled to another register (which it is in this case); such an operation isn't even linear, so it's definitely not allowed by the laws of quantum mechanics.

So, suppose you measure the second register and get some random value $K$. The precise value $K$ is basically useless to you, but you can see that the only states remaining in superposition will be those $|x\rangle$ such that $f(x)=K$.

Because $f$ hides the subgroup $H$, the set of all $x$ such that $f(x)=K$ is precisely the coset $x_K+H$ (where I'm writing $x_K$ to denote some unknown representative element of that coset).

This is why, after measuring the register with $f(x)$, the state from (3) becomes the state in (4).

Answer 3

(Made CW as an expansion of some other other answers)

Understanding the answer to why quantum algorithms often ignore the second register is a bit of a pons asinorum test toward figuring out more of the power afforded by quantum computers. For example, this point in particular even gave Simon (of Simon's alogirthm) pause, when he said:

I certainly envisioned executing this step [i.e., measuring the second register] — it would have been a lot harder to think through the algorithm without this simplification...

In Shor's original paper, he provided:

it would be sufficient to observe solely the value of $|c\rangle$ in the first register, but for clarity we will assume that we observe both $|c\rangle$ and $|x^a\pmod n\rangle$...

I think as Sam hinted there may be a confusion with the meaning of "discarding" or "removing" the second register. Here, this means that we need not actively measure the second register, and indeed, it's been suggested that we can throw this register into the trash, or say that we measure it but secretly not, or give it to our friend who says she'll measure it but won't.

The reason we need not measure this is because as both Sam and Abdulla indicate, you can trace out this second register and get the indicated results in the first register.

Many (most?) quantum algorithms have this weird feel where you do a little bit of work to prepare a first register into a uniform superposition, then do lot of work to calculate an oracle into a second register, then throw away this second register or ignore any results from measurement. After calculating the oracle into the second register, the critical information is stored into the phases in the overall wavefunction; these phases are available after performing the QFT on the first register.