Timeline for How exactly does modular exponentiation in Shor's algorithm work?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 26, 2020 at 20:26 | comment | added | Mark Spinelli | My pleasure! Glad to be of some help. (take note I'm a hack. I like thinking about this stuff but don't trust me too too much). | |
| Oct 26, 2020 at 10:36 | comment | added | foaly | Thank you for your time Mark. After taking a closer look at the probability calculations it is now clear to me why the second register is there. :) Still not quite used to quantum spookiness :P | |
| Oct 24, 2020 at 13:32 | comment | added | Mark Spinelli | @foaly I've reviewed some of your other posts and they seem pretty sophisticated to me. Maybe Nielsen and Chuang is standard. I also really liked O'Donnell's lecture series at CMU. As to your question, yes there is "spooky action" and "probability amplitudes". If we were to measure the second register and get $y$ then the wave function collapses to a comb of all $x$ satisfying $a^x\bmod N=y$. But we don't need to measure. Can you consider asking another question? | |
| Oct 24, 2020 at 2:40 | comment | added | foaly | @MarkS thanks so much for replying. I figured that there must be some spooky quantum action at play, but it doesn't seem clear to me where. In the probability calculations Shor does it's not apparent to me where the second register influences the outcome at all. Since I come from a math background, I've been looking all over for a mathematical explanation of that relationship. Do you know of any good literature, maybe? | |
| Oct 23, 2020 at 13:11 | comment | added | Mark Spinelli | @foaly Don't worry, it's a common point of confusion; Shor's algorithm (and most quantum algorithms) appear strange in that we evaluate a (say boolean) function and store the results in a second register, but then we perform some quantum action (e.g. a Fourier transform) only on the first register, without having to touch the second register again. Nonetheless in this case Alice needs to compute $a^x\bmod N$ in the second register to affect the amplitudes of the entire wave function. The Fourier transform on the first register does the constructive/destructive interference. | |
| Oct 23, 2020 at 5:37 | comment | added | foaly | Dear @MarkS, I don't mean to necro this question, but since as you say "Alice computes $a^x$ but never measures it", why does she need to compute it at all? | |
| Mar 26, 2019 at 3:20 | vote | accept | Poramet Pathumsoot | ||
| Mar 9, 2019 at 13:52 | comment | added | Mark Spinelli | @PorametPathumsoot Why do you say that "Alice has to measure the second register anyway?" Alice needs to calculate $a^x \mod N$ in the second register, while keeping the first register coherent. She does not need to measure the second register after she has calculated $a^x\mod N$ in the second register. Measuring the second register is optional in that she can measure before performing the QFT or after performing the QFT, or not at all. | |
| Mar 8, 2019 at 16:56 | comment | added | Poramet Pathumsoot | So either before or after QFT, Alice has to measure on the second register anyway. Is the meaning of optional is either before or after? Initially, I think that measurement on the second register is optional, Alice can either measure or not measure regardless of before or after QFT. | |
| Mar 1, 2019 at 15:15 | history | answered | Mark Spinelli | CC BY-SA 4.0 |