About Shor's quantum algorithm

Question

I know very little about quantum computing, and I've been trying to understand Shor's algorithm for the factorization of an integer $N$. I'm following Computational Complexity — a modern approach by Arara and Barak, which I find enjoyable to read.

There is a specific step in the algorithm which I don't understand, or rather, I don't understand how it can be done efficiently. It is no doubt the result of a deeper misunderstanding on my part, about quantum computing in general, and I feel that if I could wrap my head around this particular point, many other things would become clearer.

I hope the notation is self-explanatory in what follows. Integers are sometimes identified with the strings of 0's and 1's which you get by writing them in base 2.

So things are reduced to computing the multiplicative order (mod $N$) of a random $A$. At some point, we are in the step

$$ \left( \frac{1}{M} \sum_{x\in \mathbb{Z}/M} \lvert x\rangle \right) \otimes \lvert0^n\rangle $$

for some appropriate $M$ and some $n$ (details don't matter). The next step is then to apply the map

$$\lvert x\rangle \otimes \lvert y\rangle \mapsto \lvert x\rangle\otimes \lvert y \oplus (A^x \bmod N)\rangle. $$

This confuses me. I know that, given a fixed $x$, we can compute $A^x$ efficiently, with $O(\log(x))$ operations. However, as I understand it we are required to do the same for all $x$ here! it's more like $\log(M!)$ operations (and $M$ is close to $N$).

Also, if we end up computing $A^x$ for all $x$, and what we want is the order of $A$, why don't we stop when we find the smallest $x$ such that $A^x=1$… obviously something else is meant here. But what?

Answer 1

Per OP's suggestion, turning my comments into an answer.

It appears that there are two questions. First, what's going on with the unitary $$|x\rangle + |y \rangle \mapsto |x\rangle + |A^x + y \mod N\rangle$$ in Arora & Barak? Second, why not just stop after finding the smallest $x$ with $A^x \equiv 1 \mod N$?

For the first question: I still don't have my copy of Arora & Barak handy, but my memory is that their discussion of quantum computing is rather sketchy. One of Peter Shor's major contributions was to show that one can use the familiar trick of modular exponentiation to build a quantum circuit that efficiently computes $|x\rangle + |y \rangle \mapsto |x\rangle + |A^x + y\rangle$. Of course, his factoring algorithm also uses the Fourier transform, but it's perhaps worth noting that the modular exponentiation circuit is more complicated and generally understood to be the main bottleneck for being able to implement Shor’s algorithm fault tolerantly. Arora & Barak presumably does not construct this circuit and is probably just breezily asserting its existence.

The OP's second question seems to stem from Arora & Barak's sketchiness related to the first question. In particular, one does not implement the operation $|y\rangle \mapsto |A^x + y \mod N\rangle$ for several different choices of $x$. The key is to realize a quantum circuit for the more complicated operation of the previous paragraph, as this allows one to input a state in the first register that is in superposition over all $x \in (\mathbb{Z}/N\mathbb{Z})^*$.