INTELLIGENT QUANTUM, INC.

Exact Order Search

Compute the least positive \(r\) satisfying \(a^r\equiv1\pmod N\).

Shor’s algorithm

Order finding and factor extraction.

  1. Given a composite \(N\), handle even values and perfect powers classically. Choose \(a\) uniformly with \(1<a<N\). If \(\operatorname{gcd}(a,N)>1\), return that factor.
  2. Choose \(Q=2^t\) with \(N^2\leq Q<2N^2\), and prepare the control and work registers:
    \[ \lvert 0\rangle^{\otimes t}\lvert 1\rangle \xrightarrow{\;H^{\otimes t}\otimes I\;} \frac{1}{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle\lvert 1\rangle . \]
  3. Apply controlled modular exponentiation:
    \[ \frac{1}{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle\lvert 1\rangle \longmapsto \frac{1}{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle \lvert a^x\bmod N\rangle . \]
  4. Apply the inverse quantum Fourier transform to the control register and measure:
    \[ \left(\operatorname{QFT}_{Q}^{-1}\otimes I\right) \frac{1}{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle \lvert a^x\bmod N\rangle \xrightarrow{\;\mathrm{measure}\;} y . \]
  5. Apply continued fractions to \(y/Q\) to obtain a reduced candidate \(s/q\). For a successful sample, \(q=r/\operatorname{gcd}(k,r)\), so \(q\mid r\). Test whether \(a^q\equiv1\pmod N\). If not, repeat the measurement. If it does, then \(r\mid q\), and therefore \(q=r\), the exact order. If \(r\) is odd, choose a new base.
  6. Set \(z=a^{r/2}\bmod N\). Exactness guarantees \(z\not\equiv1\pmod N\). If \(z\equiv-1\pmod N\), choose a new base. Otherwise return
    \[ \operatorname{gcd}(z-1,N) \qquad\text{and}\qquad \operatorname{gcd}(z+1,N). \]