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

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.

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.

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$$.
• @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. – Mark S Mar 9 '19 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? – foaly 2 days ago
• @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. – Mark S yesterday