In the Quantum Computation and Quantum Information (10th ed.) textbook by Nielsen and Chuang, section 5.3.1 (titled "Application: order-finding") describes how phase estimation can be used to find the order $r$ of a positive integer.

After performing the inverse Fourier transform on the first register and then performing a measurement, we'll get an estimation of the phase $\varphi\approx\frac{s}{r}$ accurate to $2L+1$ bits. We hope to find $s$ and $r$ by performing the continued fractions procedure, which in certain cases returned $s'$ and $r'$ instead which happens when $s$ and $r$ share common factors.

The book describes three methods to fix this problem, two of which repeats the order-finding algorithm $O(L)$ times and the third requires a constant number of trials.

The third method:

The idea is to repeat the phase estimation - continued fractions procedure twice, obtaining $r'_1$, $s'_1$ the first time, and $r'_2$, $s'_2$ the second time. Provided $s'_1$, $s'_2$ have no common factors, $r$ may be extracted by taking the least common multiple of $r'_1$, $r'_2$


I don't understand why $r$ may be extracted by taking the least common multiple of $r'_1$, $r'_2$ and what is the rationale of repeating the phase estimation — continued fractions procedure twice?


2 Answers 2


Numerators and denominators of convergents of continued fractions are always co-prime. If $s$ and $r$ have a common factor, the $r'$ returned by the continued fractions algorithm would be a factor of $r$.
For example, $r=60$, provided the phase estimation step gives a good approximate to $40/60$ (i.e. $s=40$), you'll get $2/3$ as a convergent. Performing the phase estimation again might give you a good approximate to $21/60$ (i.e. $s=21$), and you'll get $7/20$ as a convergent. $lcm(3,20)=60$ will give you the correct $r$.
Although doing phase estimation-CF twice doesn't guarantee the correctness of resultant $r$ (e.g. if we got $40/60=2/3$ and $28/60=7/15$ in our two attempts, $lcm(3,15)=15$ does not give us the correct $r$), some number theoretic theorem guarantees that we succeed with probability at least $1/4$ (see the last remark on the last page of Prof Jozsa's Part II QI&C Notes).
(P.S. I'll update my answer with the aforementioned theorem of number theory when I find it)


You need that $\gcd(s_1,s_2)=1$. It's nos enough that $\gcd(s_1',s_2')=1$. Nan uses this in his example.

Lemma : $\gcd(a,mn)=1$ if and only if $\gcd(a,m)=1$ and $\gcd(a,n)=1$

Suppose that $\gcd(s_1,s_2)=1$,

$$\frac{s_1'}{r_1'}=\frac{s_1'a}{r_1'a}=\frac{s_1}{r}\quad\&\quad\frac{s_2'}{r_2'}=\frac{s_2'b}{r_2'b}=\frac{s_2}{r} $$ with $\gcd(r_1',s_1')=\gcd(s_2',r_2')=1$.

$\gcd(s_1,s_2)=1\implies \gcd(s_1'a,s_2'b)=1$

Lemma implies, $\gcd(a,b)=1$

$$ r=r_1'a=r_2'b\implies a|r_2'b,b|r_1'a\;\&\; \gcd(a,b)=1\implies a,b\text{ have no common factors}\\ \implies a|r_2'\quad\&\quad b|r_1' $$

So $r_1'=bc$ and $r_2'=ad$ for some integers c,d.

Then $abc = r = abd$ and thus, $c = d$.

Hence $\gcd(r_1',r_2')=c$.

Finally, $$r = abc=\frac{abcc}{c}=\frac{r_1'r_2'}{\gcd(r_1',r_2')}=lcm(r_1',r_2').$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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