# What's a compiled quantum algorithm?

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.

• I don't think the "compiled quantum algorithm" is a general term as such. I've only ever heard it in the context of Shor's algorithm, which I've explained below. Dec 16, 2019 at 18:06

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