When preparing the initial state of the algorithm to factor $n$ he computes $q = 2^l$ such that $n^2 \leq q < 2n^2$.

The first register then contains $l$ qubits. Why does this need to be so high. If we take $q=2^m$ such that $n \leq q < 2n$ we have $m$ qubits which is enoug to be able to represent all integers up to $n$.

Why does he take $l$ qubits is about half of that ($m$ qubits) would be enough?


There is a superposition of states initially, and there must be enough qubits in the circuit so that after the iterations the correct period of the function $f(x)=a^x\bmod N$ where $a$ is random and $N=pq$ can be found, i.e., the convergence should take place without wraparound effects, since we are working in a cyclic group and wraparound can introduce false alarms via accumulation.

Quoting Wikipedia:

Shor's algorithm consists of two parts:

  1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.

  2. A quantum algorithm to solve the order-finding problem.


The quantum circuits used for this algorithm are custom designed for each choice of $N$ and each choice of the random $a$ used in $f(x) = a^x \bmod N.$ Given $N,$ find $Q = 2q$ such that $$N^{2}\leq Q<2N^{2},$$ which implies $Q/r>N.$ The input and output qubit registers need to hold superpositions of values from $0$ to $Q − 1$ and so have $q$ qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least $N$ different $x$ which produce the same $f(x),$ even as the period $r$ approaches $N/2.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.