Shor's algorithm - modular exponentiation and Quantum Fourier transform and quantum phase estimation method

Question

I have a question about Shor's algorithm with respect to the eigenvector representation of the second (lower) register. In the following I use the notation of Nielsen, M., Chuang, I., 2016, Quantum Computation and Quantum Information, p. 232 on Quantum order-finding. I am using the quantum phase estimation approach to Shor's algorithm.
Starting off with the following preparation
$frac{1}{sqrt{2^n}}sum_{j=0}^{2^n-1}|jrangle|1rangle$,
and applying the controlled $U^j$ gates,
$frac{1}{sqrt{2^n}}sum_{j=0}^{2^n-1}|jrangle|a^jtext{ mod }Nrangle$
rewritten in terms of eigenvectors $|u_0rangle,|u_1rangle,...,|u_{r-1}rangle$ of $U$ of the second register
$frac{1}{sqrt{r2^n}}sum_{s=0}^{r-1}sum_{j=0}^{2^n-1}e^{2pi ijs/r}|jrangle|u_srangle$
and then applying the inverse QFT, we have
$frac{1}{sqrt{r}}sum_{s=0}^{r-1}|widetilde{frac{s}{r}}rangle| u_srangle$
where $|widetilde{frac{s}{r}}rangle$ is considered an approximation to an integer.
Would the application of the $QFT^{dagger}$ to
$frac{1}{sqrt{2^n}}sum_{j=0}^{2^n-1}|jrangle$
irrespective of the second register (which is in a superposition of states $|a^jtext{ mod }Nrangle$) yield $|0rangle$ for the upper register before measurement, thinking of the inverse QFT as the quantum equivalent to the discrete Fourier transform? If measured would that not result in the state $|0rangle$, which does not make sense to me, at all, as a result. How are these two approaches reconciled? Am I missing something basic here?

Mark S · Answer

To expand a bit more on the comments, measurement of the second (lower) register after preparing this register to be in $vert a^jbmod Nrangle$ and prior to performing the inverse QFT of the first register is not necessary, but may be a useful fiction we tell ourselves.
For example I'll quote whole-cloth from Greg Kuperberg on Shtetl-Optimized:

You can measure the output qubits.
The janitor can fish the output qubits out of the trash and measure them for you.
You can secretly not measure the output qubits and say you did.
You can keep the output qubits and say you threw them away.

The reason it may be convenient to think of measuring the second (lower) register prior to the inverse QFT of the first (upper) register is that, if you measure the second register and get an output $y$, this enables you to picture the first upper register as collapsing to a comb corresponding to the uniform superposition of all $j$ such that $a^jbmod N=y$.  These $j$ are just binary numbers, but magically they are spaced evenly at $r$ steps apart.  The inverse QFT, plus the other classical tricks with continued fractions, enables you to figure out what this $r$ is.
Notice that if you had measured the second register and had gotten a different $y$, then your comb would have been shifted over, but your spacing would still be $r$.
Alternatively, if you do not want to picture measuring the second register to get $y$ and collapsing the first register to the uniform superposition of all $j$ such that $y=a^jbmod N$, then after the QFT the first register will still be in a state inversely proportional to $r$.  The global phase of this state would be dependent on the specific $y$ that you would have measured, if you had measured the second register, but you didn't measure the second register.  This global phase can I think be thought of the amount of shifting mentioned above, but importantly this global phase is irrelevant to the state of the first register.
ADDED
Trying to relate an intuition about classical discrete/fast Fourier transforms to quantum Fourier transforms, there is always a risk that there are subtleties that are left behind.  Nonetheless one could consider the wavefunction, after calculating the modular exponentiation in the second register, as something similar to a $1times N$ array, such as:
$$[5,8,2,10,13,4,6,9,5,8,2,10,13,4,6,9,5,8,2,10,13,4,6,9,5,8,2,10,13,4,6,9ldots]$$
where each index corresponds to the first register, and the value of the index corresponds to the second register.  (I made up these numbers, but note that there is a period of $8$, for example).
You may also think of the wavefunction as having another array parallel to this $1times N$ array; this parallel wavefunction corresponds to the amplitude of each basis state.  Thus this parallel array might initially be a normalized version of:
$$[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1ldots]$$
It appears the OP is trying to envision this above probability array as independent of the above array of values.  For example, clearly treated in isolation a Fourier transform of this array will indeed return $[1,0,0,0,0,0ldots]$. But critically this probability amplitude array is tied to the above array of values of this matrix.
For example suppose we now we measure the second register and get, say, $2$ as an output.  This collapses the wavefunction and changes our array of probability amplitudes to a normalized version of:
$$[0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0ldots]$$
Certainly when we do the QFT on the above amplitudes, we will recognize the periodicity of $8$.
Alternatively if we had measured and gotten output of $10$, then our array of probability amplitudes would be a normalized version of:
$$[0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0ldots]$$
The QFT in either case gives the same periodicity.  The difference between measuring and returning the value of $2$ vs. the value of $10$ is only reflected in the physically irrelevant global phase of the output register.

Shor's algorithm - modular exponentiation and Quantum Fourier transform and quantum phase estimation method

One Answer

Add your own answers!

Ask a Question