4
$\begingroup$

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}|j\rangle|1\rangle$,

and applying the controlled $U^j$ gates,

$\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}|j\rangle|a^j\text{ mod }N\rangle$

rewritten in terms of eigenvectors $|u_0\rangle,|u_1\rangle,...,|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^{2\pi ijs/r}|j\rangle|u_s\rangle$

and then applying the inverse QFT, we have

$\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|\widetilde{\frac{s}{r}}\rangle| u_s\rangle$

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}|j\rangle$

irrespective of the second register (which is in a superposition of states $|a^j\text{ mod }N\rangle$) yield $|0\rangle$ 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 $|0\rangle$, which does not make sense to me, at all, as a result. How are these two approaches reconciled? Am I missing something basic here?

Improve this question
$\endgroup$
4
  • $\begingroup$ Doesn't the Discrete Fourier Transform return for a constant input signal $[1 1 1 1 ... 1]$ a scalar multiple of the vector $[1 0 0 0 0 .... 0](=|0\rangle)$ (in the frequency domain)? $\endgroup$
    – user823
    Feb 3, 2021 at 14:14
  • $\begingroup$ What is constant? I like to think of measuring the second register to get an output of, say, $y=\vert a^j\bmod N\rangle$, this collapses the first register to only store those $j$ such that $a^j\bmod N=y$. This creates a "comb" of basis states with a fixed amplitude, spaced evenly by $r$. The QFT will determine this $r$. $\endgroup$
    – Mark Spinelli
    Feb 3, 2021 at 16:56
  • $\begingroup$ Your view seems a very reasonable approach. I thought that the measurement of the second register is not a necessary step. I had difficulty understanding the following equality: $\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}|j\rangle |a^j\mod N\rangle$ $=\frac{1}{\sqrt{r2^n}}\sum_{s=0}^{r-1}\sum_{j=0}^{2^n-1}\omega^{js}|j\rangle |u_s\rangle$ with respect to the following inverse quantum fourier transform of the upper register thereafter. $\endgroup$
    – user823
    Feb 3, 2021 at 17:22
  • $\begingroup$ I thought that the inverse QFT must have the same effect on both representations in the mentioned equality, because they describe the identical physical situation from a different "perspective". $\endgroup$
    – user823
    Feb 3, 2021 at 17:29

1 Answer 1

Reset to default
1
$\begingroup$

To expand a bit more on the comments, measurement of the second (lower) register after preparing this register to be in $\vert a^j\bmod N\rangle$ 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:

  1. You can measure the output qubits.
  2. The janitor can fish the output qubits out of the trash and measure them for you.
  3. You can secretly not measure the output qubits and say you did.
  4. 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^j\bmod 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^j\bmod 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 $1\times 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,9\ldots]$$

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 $1\times 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,1\ldots]$$

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,0\ldots]$. 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,0\ldots]$$

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,0\ldots]$$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I think looking at the second register is certainly helpful and a useful idea and thinking it was measured to get a better understanding, but what happens if you apply the inverse QFT to $\frac{1}{2^{n/2}}\sum_{j=0}^{2^n-1}|j\rangle$ irrespective of the second register? What would a classical discrete fourier transform do to the signal encoded by $\frac{1}{2^{n/2}}\sum_{j=0}^{2^n-1}|j\rangle$ thought of as a signal in your opinion? $\endgroup$
    – user823
    Feb 3, 2021 at 21:38
  • $\begingroup$ If you didn't have a second register entangled with the first register in a uniform superposition over all $j$ between $0$ and $2^n-1$, then the inverse QFT of the first register would indeed revert to $\vert 0\rangle$ as you suggest, because the state is initially in the uniform superposition and the only frequency of note is the DC term (the $0$ term). But your second register is entangled with the first register in Shor's algorithm. Remember you do the Fourier transform on the amplitudes. When I refer to a comb, these are combs of amplitudes, and a $0$ amplitude means no probability. $\endgroup$
    – Mark Spinelli
    Feb 3, 2021 at 21:55
  • $\begingroup$ Would you help me get a complete understanding by formulating your thought on my question mathematically? $\endgroup$
    – user823
    Feb 6, 2021 at 15:01
  • $\begingroup$ Thanks for your addition. This is helpful, though why can't we apply the rule $(\text{QFT}^{\dagger}\otimes I)(\sum_{j=0}^{2^n-1}|j\rangle\otimes|a^j\text{mod } N\rangle)=(\text{QFT}^{\dagger}\sum_{j=0}^{2^n-1}|j\rangle)\otimes(I |a^j\text{mod } N\rangle)$. I have learnt $(AB\otimes CD=(A\otimes C)(B\otimes D)$, if $A,B,C,D$ having the corresponding dimensions. I assume my argument is still incorrect, but still that was my basic introduction how quantum logic gates act on a composite Hilbert space. How does this argument fail? $\endgroup$
    – user823
    Feb 7, 2021 at 11:18
  • $\begingroup$ It's getting hard to communicate over comments. Can you consider asking a separate question? I think you can apply the rule as you state. But remember the second register is entangled with the first register, and is still dependent on $j$. Interference only happens when both the first register and the second register are the same. $\endgroup$
    – Mark Spinelli
    Feb 7, 2021 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.