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

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?

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$$.

• 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 8, 2019 at 16:56
• @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 9, 2019 at 13:52
• 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? Oct 23, 2020 at 5:37
• @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 13:11
• @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 24, 2020 at 2:40