5
$\begingroup$

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:

enter image description here

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

enter image description here

$\endgroup$

3 Answers 3

5
$\begingroup$

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)})$.

$\endgroup$
5
  • $\begingroup$ Thanks for the response. I don’t really understand why the final state must be left in the state $|y_0\rangle + |y_1 \rangle \cdots$. $\endgroup$ Mar 23, 2023 at 13:46
  • $\begingroup$ As a simpler example: does it make sense why, if you measure the second qubit in the state $\vert 00\rangle + \vert 11\rangle$ and the result $1$, then the remaining state on the first qubit is $\vert 1\rangle$? That is, in general the the only states left in a superposition after measurement are those entangled with the measured value. This is the same principle, just a bit larger and more abstract. $\endgroup$
    – Sam Jaques
    Mar 23, 2023 at 14:49
  • 1
    $\begingroup$ I should add that there are two notation conventions here: In the state above, if you measure the second qubit, is the resulting state $\vert 11\rangle$ (the second qubit is still there, but it is projected into the $\vert 1\rangle$ state), or is the resulting state $\vert 1\rangle$ (the second qubit is "gone", i.e., it is no longer an available quantum resource). I've seen the first used more in introductory material, and the second used frequently in research papers, so that might also be confusing. $\endgroup$
    – Sam Jaques
    Mar 23, 2023 at 14:51
  • $\begingroup$ Oh, I was discounting the entanglement. Thanks. $\endgroup$ Mar 23, 2023 at 15:36
  • $\begingroup$ @TwentyCents I have added a bit more detail. Also, if you really want to understand this, do all steps of Simon's algorithm in full detail for n=2 or 3. Identify all cosets etc. $\endgroup$ Mar 23, 2023 at 19:04
4
$\begingroup$

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).

$\endgroup$
0
4
$\begingroup$

(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.

$\endgroup$

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.