What's a compiled quantum algorithm?

Question

Many works on quantum algorithms, including this article, mention

a compiled version of (Shor's factoring) algorithm

What's a compiled quantum algorithm?

_{Meta: and is it worth to create a tag for that? I don't have the required rep.}

Answer 1

The Nature paper Oversimplifying quantum factoring explains the concept well.

All experimental realizations of Shor’s algorithm to date have relied on a further optimization, that of “compiling” the algorithm. This means employing the observation that different bases $a$ in the modular exponentiation lead to different periods of the function $a^x \bmod N$. Some of the periods are both short and lead to a factorization of the composite $pq$. [arxiv:1301.7007]

For instance, in this paper the authors claim having done the factorization of $21$ using Shor's algorithm. But the catch is that they had to use the fact that $21 = 3 \times 7$ to choose an "easy" base $a$. So it's not factorization of $21$ in the true sense; they only verified the factors. Thus, the qubits needed drastically reduced from $10$ (i.e., $2 + (3/2)\log N$, per Zalka) to only $2$ qubits! The compilation procedure was also implemented for the 2001 factorization of $15$.

It is absolutely crucial to note the following comment by Smolin et al. here.

Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language.