I Shor Algorithm - Post measurement state

[Ricardo Belchior]

Hello!

So I'm working to try to understand shor algorithm and I have some doubts.

So, after the hadamard gates we apply the unitary gate that construct the function y^k mod N. Next we do a measurement in the second register to get some function value. So, when I do this measurement on the second register, I will get, in the first register, only the values of k that correspond to that function value.

My question is, is that right? I'm I thinking straight? If so, who does that happen? Entanglement?

Thanks

 

[Strilanc]

You don't actually need to measure the second register. You can just throw it out.

But yes, if you measure the second register and get the result $m$ then that tells you the first register is in a state proportional to $\sum_{j} |jl+x \rangle$, where $x$ is the value that satisfies $b^x \equiv m \pmod{R}$ and $b^l \pmod{R} \equiv 1$. But you still don't know $x$ or $l$, and they're intractable to compute, so really you haven't learned anything more at that point than you would by just classical random sampling. The fun quantum stuff only happens in the next step when you apply the quantum Fourier transform (and at that point it matters that you have a superposition instead of a probability distribution).

I wouldn't consider "entanglement" to be a good description of why this happens. It's just kinda what has to happen in order for things to be consistent. If you some register storing $x$, then compute $b^x$ into another register, then obviously the relationship between the two isn't affected by the order you measure them. If you measured the second register and got $m$, then measured the first register and got some value $x$ that didn't satisfy $b^x = m$, that would be pretty ridiculous.

 

[Ricardo Belchior]

Thanks for the great answer.

Exactly, that state cannot be computed. But if I throw away the second register, the first one will have the same probabilities for all values, just like the output of hadamard gates, right?

(and at that point it matters that you have a superposition instead of a probability distribution).

What do you mean by that?

I think my biggest struggle is to understand what goes into the QFT.

Sorry for all the questions, but I'm having a really hard time to understand all this.

Thanks

 

[Strilanc]

You should learn about the discrete Fourier transform separately, classically, before trying to understand it in combination with quantum computing and in combination with a specific algorithm in quantum computing.

 

[Ricardo Belchior]

Hello again,

So I have another question. In Shor algorithm it is applied the deffered measurment principle, right? I mean, if i did the measurment at the beginning, the results would be the same?

cheers

 

[Strilanc]

What do you mean "at the beginning"? If you measure the phase-estimation register before the QFT, or the work register when only some of the multiplications have been done, no you won't get the same answer.

 

[Ricardo Belchior]

Ok I get it. But i still have some hard times to understand the phase-estimation. I think the bottom question is : How do I implement the controlled-U to implement a^x mod N?

 

[Strilanc]

You break it down into simpler and simpler operations until you're left with just (a whole lot of) constant-sized operations.

I've been working on a paper that does this. Here's my simplified dependency graph:

And two of the steps, as an example: