How exactly does modular exponentiation in Shor's algorithm work?

Question

Consider the modular exponentiation part of Shor's algorithm which in many works is just referred to as $$U_{f}\sum^{N-1}_{x = 0}\vert x\rangle\vert 0\rangle = \vert x\rangle\vert a^{x}\text{ mod }N\rangle$$ where $a$ is random number between $1 < a < N.$

$U_{f}$ is frequently left as a black box, but sometimes when I look in papers that write about it and see the actual circuit I don't really understand. More so when I trying to connect it with the algorithm.

So, here is my understanding: Shor's algorithm begins with the initialization of 2 registers of qubits. First set to hold the superposition of number from $0$ to $N$ ($N$ is the number that needs to be factored) and the second register to hold the function $f(x) = a^{x} \text{ mod } N$. Then with or without measuring the second register, the result is the same. So does measurement matter or not? Then one obtains the result after applying quantum Fourier transform on the first register (leave the matter of extract period).

Now I am confused about how the second register holds $f(x)$. I mean the algorithm computes $f(x)$ with repeated squaring (classically) right? Then how does the second register of qubits hold the value in a superposition of sequence (modular exponentiation sequence)? Did I misunderstand something?

Answer 1

There are a number of questions here.

Regarding your first question:

So does measurement matter or not?

I learned a lot about quantum computing/quantum mechanics by figuring out why measuring the second register is optional. If it weren't optional, then we can send superluminal messages.

For example, suppose Alice runs Shor's algorithm. After applying a Hadarmard operation to $\vert x \rangle$, and then the repeating squaring operation $U_f$ to the second register, the state is in:

$$U_{f}\sum^{N-1}_{x = 0}\vert x\rangle\vert 0\rangle = \vert x\rangle\vert a^{x}\text{ mod }N\rangle$$

Alice will perform the QFT on the first register. But we have a couple of different things we can do to the second register.

• If Alice were to measure and obtain $y$ in the second register before performing the QFT on the first register, Alice will simply collapse the first register to a state consisting of all $\vert x \rangle$ such that $y=a^x\mod N$.
• If Alice were to measure and obtain $y$ in the second register after performing the QFT, Alice will likewise collapse the first register into a state where the global phase depends on $y$

But suppose Alice gives the second register to her friend Bob.

• Bob can decide whether to measure the second register, or not measure the second register, or measure the second register after Alice performs the QFT on the first register, or measure the second register before Alice performs the QFT...
• Bob can be very far away!
• E.G. he can be on the other side of Earth, or on the other side of Alpha Centauri
• More controversially he could jump into the event horizon of a black hole

If his course of action affected Alice's first register in such a way that Alice can figure out what he did, then he could send a message superluminally to Alice. Importantly there is no spooky action at a distance that he can do to affect Alice's QFT.

Regarding your second question:

I mean the algorithm computes $f(x)$ with repeated squaring (classically) right?

Shor's paper was rightfully light on details on how modular exponentiation would be implemented, but his argument was effectively "because there's a classically fast solution to modular exponentiation - i.e. repeated squaring, there's a quantum mechanical sequence of unitaries that efficiently implements repeated squaring."

That is, one of Shor's many insights is that because modular exponentiation can be easily implemented "classically" by means of repeated squaring, with a bunch of $\mathsf{NAND}$ gates, $\mathsf{NOR}$ gates, etc., modular exponentiation can also be implemented "quantum mechanically" with $\mathsf{CCNOT}$ gates, etc.

Regarding your third question:

Then how does the second register of qubits hold the value in a superposition of sequence (modular exponentiation sequence)?

The contents of the second register is dependent on the contents of the first register. The first and second register are entangled after applying $U_f$.