อัลกอริทึมของ Shor

ต่อไปเราจะมาดูปัญหาการแยกตัวประกอบจำนวนเต็ม และดูว่าคอมพิวเตอร์ควอนตัมสามารถแก้ปัญหานี้ได้อย่างมีประสิทธิภาพด้วยการใช้การประมาณเฟสได้อย่างไร อัลกอริทึมที่เราจะได้มาคือ อัลกอริทึมของ Shor สำหรับการแยกตัวประกอบจำนวนเต็ม Shor ไม่ได้อธิบายอัลกอริทึมของตัวเองในแง่ของการประมาณเฟสโดยตรง แต่มันเป็นวิธีที่เป็นธรรมชาติและเข้าใจง่ายในการอธิบายว่ามันทำงานอย่างไร

เราจะเริ่มต้นด้วยการพูดถึงปัญหาระดับกลางที่เรียกว่า ปัญหาการหาอันดับ และดูว่าการประมาณเฟสให้วิธีแก้ปัญหานี้ได้อย่างไร จากนั้นเราจะดูว่าวิธีแก้ที่มีประสิทธิภาพสำหรับปัญหาการหาอันดับนำไปสู่วิธีแก้ที่มีประสิทธิภาพสำหรับปัญหาการแยกตัวประกอบจำนวนเต็มได้อย่างไร (เมื่อวิธีแก้ปัญหาหนึ่งให้วิธีแก้ปัญหาอีกปัญหาหนึ่งในลักษณะนี้ เราบอกว่าปัญหาที่สอง ลดรูป ไปสู่ปัญหาแรก — ดังนั้นในกรณีนี้เรากำลังลดรูปการแยกตัวประกอบจำนวนเต็มให้เป็นการหาอันดับ) ส่วนที่สองของอัลกอริทึม Shor นี้ไม่ได้ใช้การประมวลผลเชิงควอนตัมเลย แต่เป็นแบบคลาสสิกล้วนๆ การประมวลผลเชิงควอนตัมจำเป็นเฉพาะสำหรับการแก้ปัญหาการหาอันดับเท่านั้น

ปัญหาการหาอันดับ

ทฤษฎีจำนวนเบื้องต้น

เพื่ออธิบายปัญหาการหาอันดับและวิธีแก้ปัญหาด้วยการประมาณเฟส จะเป็นประโยชน์ถ้าเราเริ่มด้วยแนวคิดทฤษฎีจำนวนพื้นฐานสักสองสามอย่าง และแนะนำสัญลักษณ์ที่สะดวกไปพร้อมกัน

ก่อนอื่น สำหรับจำนวนเต็มบวก $N$ ใดๆ ให้นิยามเซต $\mathbb{Z}_N$ ดังนี้

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

ตัวอย่างเช่น $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ และต่อๆ ไป

เซตเหล่านี้เป็นเซตของตัวเลข แต่เราสามารถมองมันได้มากกว่าแค่เซต โดยเฉพาะ เราสามารถคิดถึง การดำเนินการทางคณิตศาสตร์ บน $\mathbb{Z}_N$ เช่น การบวกและการคูณ — และถ้าเราตกลงที่จะนำคำตอบมอดุโล $N$ เสมอ (นั่นคือ หารด้วย $N$ แล้วเอาเศษเป็นผลลัพธ์) เราจะยังอยู่ในเซตนี้เสมอเมื่อทำการดำเนินการเหล่านี้ การดำเนินการสองอย่างคือการบวกและการคูณ ทั้งคู่นำมาด้วยมอดุโล $N$ ทำให้ $\mathbb{Z}_N$ กลายเป็น ริง ซึ่งเป็นประเภทวัตถุที่สำคัญมากในพีชคณิต

ตัวอย่างเช่น $3$ และ $5$ เป็นสมาชิกของ $\mathbb{Z}_7$ และถ้าเราคูณกันจะได้ $3\cdot 5 = 15$ ซึ่งเหลือเศษ $1$ เมื่อหารด้วย $7$ บางครั้งเราเขียนสิ่งนี้ดังนี้

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

แต่เราสามารถเขียนง่ายๆ ว่า $3 \cdot 5 = 1$ ได้เช่นกัน หากชัดเจนว่าเราทำงานใน $\mathbb{Z}_7$ เพียงเพื่อให้สัญลักษณ์เรียบง่ายที่สุด

ตัวอย่างเช่น นี่คือตารางการบวกและตารางการคูณสำหรับ $\mathbb{Z}_6$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

ในบรรดาสมาชิก $N$ ตัวของ $\mathbb{Z}_N$ สมาชิก $a\in\mathbb{Z}_N$ ที่ตอบสนอง $\gcd(a,N) = 1$ มีความพิเศษ บ่อยครั้งเซตที่ประกอบด้วยสมาชิกเหล่านี้ถูกแทนด้วยดาวดังนี้

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

ถ้าเราเน้นที่การดำเนินการคูณ เซต $\mathbb{Z}_N^{\ast}$ ก่อรูป กรุป — โดยเฉพาะ กรุปอาเบเลียน — ซึ่งเป็นประเภทวัตถุสำคัญอีกอย่างในพีชคณิต เป็นข้อเท็จจริงพื้นฐานเกี่ยวกับเซตเหล่านี้ (และกรุปจำกัดโดยทั่วไป) ว่าถ้าเราเลือกสมาชิกใดๆ $a\in\mathbb{Z}_N^{\ast}$ แล้วคูณ $a$ กับตัวเองซ้ำๆ เราจะได้จำนวน $1$ ในที่สุดเสมอ

สำหรับตัวอย่างแรก ลองใช้ $N=6$ เรามีว่า $5\in\mathbb{Z}_6^{\ast}$ เพราะ $\gcd(5,6) = 1$ และถ้าเราคูณ $5$ กับตัวเองจะได้ $1$ ดังที่ตารางข้างต้นยืนยัน

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

สำหรับตัวอย่างที่สอง ลองใช้ $N = 21$ ถ้าเราผ่านตัวเลขจาก $0$ ถึง $20$ ตัวที่มี GCD เท่ากับ $1$ กับ $21$ มีดังนี้

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

สำหรับสมาชิกแต่ละตัว เราสามารถยกกำลังจำนวนนั้นเป็นเลขชี้กำลังจำนวนเต็มบวกเพื่อให้ได้ $1$ นี่คือกำลังที่น้อยที่สุดที่ใช้ได้:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

โดยธรรมชาติเราทำงานใน $\mathbb{Z}_{21}$ สำหรับสมการทั้งหมดเหล่านี้ ซึ่งเราไม่ได้เขียนไว้ เรานัยว่ามันเป็นนัยโดยอ้อมเพื่อหลีกเลี่ยงความรกรุงรัง เราจะทำแบบนี้ต่อไปตลอดบทเรียนที่เหลือ

คำกล่าวปัญหาและความเชื่อมโยงกับการประมาณเฟส

ตอนนี้เราสามารถระบุปัญหาการหาอันดับได้

การหาอันดับ

อินพุต: จำนวนเต็มบวก $N$ และ $a$ ที่ตอบสนอง $\gcd(N,a) = 1$
เอาต์พุต: จำนวนเต็มบวกที่น้อยที่สุด $r$ ที่ทำให้ $a^r \equiv 1$ $(\textrm{mod } N)$

หรือในแง่ของสัญลักษณ์ที่เราแนะนำข้างต้น เราได้รับ $a \in \mathbb{Z}_N^{\ast}$ และเรากำลังมองหาจำนวนเต็มบวกที่น้อยที่สุด $r$ ที่ทำให้ $a^r = 1$ จำนวน $r$ นี้เรียกว่า อันดับ ของ $a$ มอดุโล $N$

เพื่อเชื่อมปัญหาการหาอันดับกับการประมาณเฟส ลองคิดถึงการดำเนินการที่นิยามบนระบบที่มีสถานะคลาสสิกสอดคล้องกับ $\mathbb{Z}_N$ โดยเราคูณด้วยสมาชิกคงที่ $a\in\mathbb{Z}_N^{\ast}$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

เพื่อให้ชัดเจน เราทำการคูณใน $\mathbb{Z}_N$ ดังนั้นเป็นนัยว่าเราคิดผลคูณมอดุโล $N$ ภายในเคตทางขวามือของสมการ

ตัวอย่างเช่น ถ้าเราใช้ $N = 15$ และ $a=2$ การกระทำของ $M_2$ บนฐานมาตรฐาน $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ มีดังนี้

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

นี่คือการดำเนินการยูนิทารีเมื่อ $\gcd(a,N)=1$ เพราะมันสับเปลี่ยนสมาชิกของฐานมาตรฐาน $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$ ดังนั้นในฐานะเมทริกซ์มันคือเมทริกซ์การสับเปลี่ยน จากนิยามของมันชัดเจนว่าการดำเนินการนี้เป็นแบบดีเทอร์มินิสติก และวิธีง่ายๆ ที่จะเห็นว่ามันกลับได้คือคิดถึงอันดับ $r$ ของ $a$ มอดุโล $N$ และตระหนักว่าอินเวิร์สของ $M_a$ คือ $M_a^{r-1}$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

มีอีกวิธีหนึ่งในการคิดถึงอินเวิร์สที่ไม่ต้องรู้ $r$ (ซึ่งท้ายที่สุดเราก็กำลังพยายามคำนวณมันอยู่) สำหรับสมาชิกทุกตัว $a\in\mathbb{Z}_N^{\ast}$ มีสมาชิกเดียวที่ไม่ซ้ำ $b\in\mathbb{Z}_N^{\ast}$ ที่ตอบสนอง $ab=1$ เสมอ เราแทนสมาชิก $b$ นี้ด้วย $a^{-1}$ และสามารถคำนวณได้อย่างมีประสิทธิภาพ ส่วนขยายของอัลกอริทึม GCD ของ Euclid ทำได้โดยมีต้นทุนกำลังสองใน $\operatorname{lg}(N)$ ดังนั้น

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

ดังนั้น การดำเนินการ $M_a$ ทั้งเป็นแบบดีเทอร์มินิสติกและกลับได้ ซึ่งหมายความว่ามันถูกอธิบายด้วยเมทริกซ์การสับเปลี่ยน และดังนั้นจึงเป็นยูนิทารี

ตอนนี้ลองคิดถึงเวกเตอร์เฉพาะและค่าเฉพาะของการดำเนินการ $M_a$ โดยสมมติว่า $a\in\mathbb{Z}_N^{\ast}$ ดังที่เพิ่งโต้แย้งไว้ สมมติฐานนี้บอกเราว่า $M_a$ เป็นยูนิทารี

มีค่าเฉพาะ $N$ ค่าของ $M_a$ ซึ่งอาจมีค่าเฉพาะเดิมซ้ำหลายครั้ง และโดยทั่วไปมีอิสระในการเลือกเวกเตอร์เฉพาะที่สอดคล้องกัน — แต่เราไม่จำเป็นต้องกังวลเกี่ยวกับความเป็นไปได้ทั้งหมด ลองเริ่มง่ายๆ และระบุเวกเตอร์เฉพาะหนึ่งตัวของ $M_a$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

จำนวน $r$ คืออันดับของ $a$ มอดุโล $N$ ที่นี่และตลอดบทเรียนที่เหลือ ค่าเฉพาะที่เชื่อมโยงกับเวกเตอร์เฉพาะนี้คือ $1$ เพราะมันไม่เปลี่ยนเมื่อเราคูณด้วย $a$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

สิ่งนี้เกิดขึ้นเพราะ $a^r = 1$ ดังนั้นสถานะฐานมาตรฐานแต่ละตัว $\vert a^k \rangle$ จะถูกเลื่อนไปที่ $\vert a^{k+1} \rangle$ สำหรับ $k\leq r-1$ และ $\vert a^{r-1} \rangle$ จะถูกเลื่อนกลับมาที่ $\vert 1\rangle$ พูดอย่างไม่เป็นทางการ มันเหมือนกับเรากำลังคนช้าๆ $\vert \psi_0 \rangle$ แต่มันถูกคนจนสม่ำเสมอแล้วจึงไม่มีอะไรเปลี่ยนแปลง

นี่คืออีกตัวอย่างหนึ่งของเวกเตอร์เฉพาะของ $M_a$ ตัวนี้น่าสนใจกว่าในบริบทของการหาอันดับและการประมาณเฟส

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

หรือเราสามารถเขียนเวกเตอร์นี้โดยใช้การรวมดังนี้

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

ที่นี่เราเห็นจำนวนเชิงซ้อน $\omega_r = e^{2\pi i/r}$ ปรากฏขึ้นโดยธรรมชาติ เนื่องจากวิธีที่การคูณด้วย $a$ ทำงานมอดุโล $N$ คราวนี้ค่าเฉพาะที่สอดคล้องคือ $\omega_r$ เพื่อดูสิ่งนี้ เราสามารถคำนวณดังนี้ก่อน

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

จากนั้น เพราะ $\omega_r^{-r} = 1 = \omega_r^0$ และ $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$ เราจะเห็นว่า

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

ดังนั้น $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle$

ด้วยเหตุผลเดียวกัน เราสามารถระบุคู่เวกเตอร์เฉพาะ/ค่าเฉพาะเพิ่มเติมสำหรับ $M_a$ ได้ สำหรับทุกการเลือก $j\in\{0,\ldots,r-1\}$ เรามีว่า

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

เป็นเวกเตอร์เฉพาะของ $M_a$ ที่มีค่าเฉพาะสอดคล้องคือ $\omega_r^j$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

มีเวกเตอร์เฉพาะอื่นๆ ของ $M_a$ แต่เราไม่จำเป็นต้องใส่ใจกับมัน — เราจะเน้นเฉพาะเวกเตอร์เฉพาะ $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ ที่เราเพิ่งระบุไว้เท่านั้น

การหาอันดับผ่านการประมาณเฟส

เพื่อแก้ปัญหาการหาอันดับสำหรับการเลือก $a\in\mathbb{Z}_N^{\ast}$ ที่กำหนด เราสามารถใช้กระบวนการประมาณเฟสกับการดำเนินการ $M_a$

เพื่อทำสิ่งนี้ เราต้องสร้าง Circuit ควอนตัมที่สามารถนำ $M_a$ ไปใช้งานอย่างมีประสิทธิภาพได้ ไม่เพียงแค่ $M_a$ เท่านั้น แต่ยังรวมถึง $M_a^2,$ $M_a^4,$ $M_a^8,$ และต่อๆ ไป ไปจนถึงเท่าที่จำเป็นเพื่อให้ได้การประมาณที่แม่นยำพอจากกระบวนการประมาณเฟส เราจะอธิบายว่าสามารถทำสิ่งนี้ได้อย่างไร และจะคำนวณว่าต้องการความแม่นยำมากแค่ไหนในภายหลัง

ลองเริ่มด้วยการดำเนินการ $M_a$ เพียงตัวเดียว โดยธรรมชาติ เพราะเราทำงานกับโมเดล Circuit ควอนตัม เราจะใช้สัญลักษณ์ไบนารีในการเข้ารหัสตัวเลขระหว่าง $0$ ถึง $N-1$ ตัวเลขที่ใหญ่ที่สุดที่เราต้องเข้ารหัสคือ $N-1$ ดังนั้นจำนวนบิตที่เราต้องการคือ

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

ตัวอย่างเช่น ถ้า $N = 21$ เรามี $n = \operatorname{lg}(N-1) = 5$ นี่คือลักษณะการเข้ารหัสสมาชิกของ $\mathbb{Z}_{21}$ เป็นสตริงไบนารีความยาว $5$

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

และตอนนี้ นี่คือนิยามที่แม่นยำของวิธีที่ $M_a$ ถูกนิยามเป็นการดำเนินการ $n$-Qubit

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

ประเด็นคือแม้เราจะสนใจเฉพาะวิธีที่ $M_a$ ทำงานสำหรับ $\vert 0\rangle,\ldots,\vert N-1\rangle$ เราก็ต้องระบุวิธีที่มันทำงานสำหรับสถานะฐานมาตรฐานที่เหลืออีก $2^n - N$ ตัว — และเราต้องทำสิ่งนี้ในทางที่ยังคงให้เราได้การดำเนินการยูนิทารี การนิยาม $M_a$ เพื่อให้ไม่ทำอะไรกับสถานะฐานมาตรฐานที่เหลือนั้นบรรลุเป้าหมายนี้

โดยใช้อัลกอริทึมสำหรับการคูณและหารจำนวนเต็มที่กล่าวถึงในบทเรียนก่อนหน้า ร่วมกับวิธีการสำหรับการนำไปใช้งานแบบกลับได้และปราศจากขยะ เราสามารถสร้าง Circuit ควอนตัมที่ทำการดำเนินการ $M_a$ สำหรับทุกการเลือก $a\in\mathbb{Z}_N^{\ast}$ ด้วยต้นทุน $O(n^2)$ นี่คือวิธีหนึ่งที่สามารถทำได้

1. สร้าง Circuit สำหรับทำการดำเนินการ

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   โดยที่

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   โดยใช้วิธีที่อธิบายในบทเรียนก่อนหน้า สิ่งนี้ให้ Circuit ที่มีขนาด $O(n^2)$

2. สลับสองระบบ $n$-Qubit โดยใช้ Gate สลับ $n$ ตัวเพื่อสลับ Qubit แต่ละตัว

3. คล้ายกับขั้นตอนแรก สร้าง Circuit สำหรับการดำเนินการ

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   โดยที่ $a^{-1}$ คืออินเวิร์สของ $a$ ใน $\mathbb{Z}_N^{\ast}$

โดยการเริ่มต้น Qubit ล่าง $n$ ตัวและประกอบสามขั้นตอน เราได้การแปลงดังนี้:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

วิธีนี้ต้องการ Qubit พื้นที่ทำงาน แต่พวกมันจะถูกส่งคืนสู่สถานะเริ่มต้นที่ตอนท้าย ซึ่งช่วยให้เราใช้ Circuit เหล่านี้สำหรับการประมาณเฟสได้ ต้นทุนรวมของ Circuit ที่เราได้คือ $O(n^2)$

ในการทำ $M_a^2,$ $M_a^4,$ $M_a^8,$ และต่อๆ ไป เราสามารถใช้วิธีเดียวกันนี้ เพียงแต่เปลี่ยน $a$ เป็น $a^2,$ $a^4,$ $a^8,$ และต่อๆ ไป ในฐานะสมาชิกของ $\mathbb{Z}_N^{\ast}$ นั่นคือ สำหรับทุกกำลัง $k$ ที่เราเลือก เราสามารถสร้าง Circuit สำหรับ $M_a^k$ ไม่ใช่โดยการทำซ้ำ Circuit สำหรับ $M_a$ $k$ ครั้ง แต่โดยการคำนวณ $b = a^k \in \mathbb{Z}_N^{\ast}$ แล้วใช้ Circuit สำหรับ $M_b$

การคำนวณกำลัง $a^k \in \mathbb{Z}_N$ คือปัญหา การยกกำลังมอดุลาร์ ที่กล่าวถึงในบทเรียนก่อนหน้า การคำนวณนี้สามารถทำได้ แบบคลาสสิก โดยใช้อัลกอริทึมสำหรับการยกกำลังมอดุลาร์ที่กล่าวถึงในบทเรียนก่อนหน้า (มักเรียกว่า อัลกอริทึมกำลัง ในทฤษฎีจำนวนเชิงคำนวณ) ที่จริง เราต้องการเฉพาะกำลัง กำลังสองของ 2 ของ $a$ โดยเฉพาะคือ $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$ และเราสามารถได้กำลังเหล่านี้โดยการยกกำลังสองซ้ำๆ $m-1$ ครั้ง การยกกำลังสองแต่ละครั้งสามารถทำได้โดย Circuit บูลีนที่มีขนาด $O(n^2)$

โดยพื้นฐานแล้ว สิ่งที่เราทำที่นี่คือการโอนปัญหาการทำซ้ำ $M_a$ มากถึง $2^{m-1}$ ครั้งไปให้การคำนวณแบบคลาสสิกที่มีประสิทธิภาพ และมันเป็นโชคดีที่สิ่งนี้เป็นไปได้! สำหรับการเลือก Circuit ควอนตัมโดยพลการในปัญหาการประมาณเฟส สิ่งนี้ไม่น่าจะเป็นไปได้ — และในกรณีนั้นต้นทุนที่ได้สำหรับการประมาณเฟสจะเพิ่มขึ้น แบบเอกซ์โปเนนเชียล ตามจำนวน Qubit ควบคุม $m$

วิธีแก้เมื่อมีเวกเตอร์เฉพาะที่สะดวก

เพื่อทำความเข้าใจว่าเราสามารถแก้ปัญหาการหาอันดับโดยใช้การประมาณเฟสได้อย่างไร ลองเริ่มด้วยการสมมติว่า เราเรียกใช้กระบวนการประมาณเฟสกับการดำเนินการ $M_a$ โดยใช้เวกเตอร์เฉพาะ $\vert\psi_1\rangle$ การหาเวกเตอร์เฉพาะนี้ไม่ง่าย ดังที่จะเห็นต่อไป ดังนั้นนี่จะยังไม่ใช่ตอนจบของเรื่อง — แต่มีประโยชน์ที่จะเริ่มตรงนี้

ค่าเฉพาะของ $M_a$ ที่สอดคล้องกับเวกเตอร์เฉพาะ $\vert \psi_1\rangle$ คือ

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

นั่นคือ $\omega_r = e^{2\pi i \theta}$ สำหรับ $\theta = 1/r$ ดังนั้น ถ้าเราเรียกใช้กระบวนการประมาณเฟสกับ $M_a$ โดยใช้เวกเตอร์เฉพาะ $\vert\psi_1\rangle$ เราจะได้การประมาณ $1/r$ โดยการคำนวณส่วนกลับเราจะสามารถเรียนรู้ $r$ ได้ — หากการประมาณของเราแม่นยำพอ

รายละเอียดมากขึ้น เมื่อเราเรียกใช้กระบวนการประมาณเฟสโดยใช้ Qubit ควบคุม $m$ ตัว สิ่งที่เราได้คือจำนวน $y\in\{0,\ldots,2^m-1\}$ เราใช้ $y/2^m$ เป็นการเดาสำหรับ $\theta$ ซึ่งคือ $1/r$ ในกรณีนี้ เพื่อคิดออกว่า $r$ คืออะไรจากการประมาณนี้ สิ่งที่เป็นธรรมชาติที่ทำคือคำนวณส่วนกลับของการประมาณและปัดเศษไปยังจำนวนเต็มที่ใกล้ที่สุด

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

ตัวอย่างเช่น สมมติว่า $r = 6$ และเราทำการประมาณเฟสกับ $M_a$ พร้อมเวกเตอร์เฉพาะ $\vert\psi_1\rangle$ โดยใช้บิตควบคุม $m = 5$ บิต การประมาณ $5$ บิตที่ดีที่สุดของ $1/r = 1/6$ คือ $5/32$ และเรามีโอกาสที่ค่อนข้างดี (ประมาณ $68\%$ ในกรณีนี้) ที่จะได้ผลลัพธ์ $y=5$ จากการประมาณเฟส เรามี

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

และการปัดเศษไปยังจำนวนเต็มที่ใกล้ที่สุดให้ $6$ ซึ่งเป็นคำตอบที่ถูกต้อง

ในทางกลับกัน ถ้าเราไม่ใช้ความแม่นยำเพียงพอ เราอาจไม่ได้คำตอบที่ถูกต้อง ตัวอย่างเช่น ถ้าเราใช้ Qubit ควบคุม $m = 4$ ตัวในการประมาณเฟส เราอาจได้การประมาณ $4$ บิตที่ดีที่สุดของ $1/r = 1/6$ ซึ่งคือ $3/16$ การคำนวณส่วนกลับให้

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

และการปัดเศษไปยังจำนวนเต็มที่ใกล้ที่สุดให้คำตอบที่ผิดคือ $5$

แล้วเราต้องการความแม่นยำเท่าไรจึงจะได้คำตอบที่ถูกต้อง? เรารู้ว่าอันดับ $r$ เป็นจำนวนเต็ม และพูดอย่างเป็นสัญชาตญาณสิ่งที่เราต้องการคือความแม่นยำเพียงพอที่จะแยกแยะ $1/r$ จากความเป็นไปได้ใกล้เคียง รวมถึง $1/(r+1)$ และ $1/(r-1)$ จำนวนที่ใกล้เคียงที่สุดกับ $1/r$ ที่เราต้องกังวลคือ $1/(r+1)$ และระยะห่างระหว่างตัวเลขสองตัวนี้คือ

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

ดังนั้น ถ้าเราต้องการมั่นใจว่าเราไม่สับสน $1/r$ กับ $1/(r+1)$ ก็เพียงพอที่จะใช้ความแม่นยำที่รับประกันว่าการประมาณที่ดีที่สุด $y/2^m$ สำหรับ $1/r$ ใกล้กับ $1/r$ มากกว่าใกล้กับ $1/(r+1)$ ถ้าเราใช้ความแม่นยำเพียงพอให้

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

เพื่อให้ค่าผิดพลาดน้อยกว่าครึ่งของระยะห่างระหว่าง $1/r$ และ $1/(r+1)$ แล้ว $y/2^m$ จะใกล้กับ $1/r$ มากกว่าความเป็นไปได้อื่นใด รวมถึง $1/(r+1)$ และ $1/(r-1)$

เราสามารถตรวจสอบสิ่งนี้ดังนี้ สมมติว่า

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

สำหรับ $\varepsilon$ ที่ตอบสนอง

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

เมื่อเราคำนวณส่วนกลับจะได้

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

โดยการทำให้เศษส่วนมากที่สุดและส่วนน้อยที่สุด เราสามารถจำกัดว่าเราอยู่ห่างจาก $r$ มากแค่ไหนดังนี้

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

เราอยู่ห่างจาก $r$ น้อยกว่า $1/2$ ดังนั้นตามที่คาดไว้เราจะได้ $r$ เมื่อปัดเศษ

น่าเสียดายที่เนื่องจากเรายังไม่รู้ว่า $r$ คืออะไร เราไม่สามารถใช้มันบอกเราว่าต้องการความแม่นยำเท่าไร สิ่งที่เราทำได้แทนคือใช้ข้อเท็จจริงที่ว่า $r$ ต้องน้อยกว่า $N$ เพื่อให้แน่ใจว่าเราใช้ความแม่นยำเพียงพอ โดยเฉพาะ ถ้าเราใช้ความแม่นยำเพียงพอเพื่อรับประกันว่าการประมาณที่ดีที่สุด $y/2^m$ สำหรับ $1/r$ ตอบสนอง

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

เราจะมีความแม่นยำเพียงพอที่จะกำหนด $r$ ได้อย่างถูกต้องเมื่อเราคำนวณส่วนกลับ การใช้ $m = 2\operatorname{lg}(N)+1$ รับประกันว่าเรามีโอกาสสูงที่จะได้การประมาณที่มีความแม่นยำนี้โดยใช้วิธีที่อธิบายก่อนหน้า (การใช้ $m = 2\operatorname{lg}(N)$ เพียงพอหากเราพอใจกับขอบล่าง 40% ของความน่าจะเป็นความสำเร็จ)

วิธีแก้ทั่วไป

ดังที่เพิ่งเห็น ถ้าเรามีเวกเตอร์เฉพาะ $\vert \psi_1 \rangle$ ของ $M_a$ เราสามารถเรียนรู้ $r$ ผ่านการประมาณเฟส ตราบเท่าที่เราใช้ Qubit ควบคุมเพียงพอเพื่อทำสิ่งนี้ด้วยความแม่นยำที่เพียงพอ น่าเสียดายที่ไม่ง่ายที่จะหาเวกเตอร์เฉพาะ $\vert\psi_1\rangle$ ดังนั้นเราต้องคิดหาวิธีดำเนินการต่อ

ลองสมมติชั่วคราวว่าเราดำเนินการเหมือนข้างต้น แต่ใช้เวกเตอร์เฉพาะ $\vert\psi_k\rangle$ แทน $\vert\psi_1\rangle$ สำหรับทุกการเลือก $k\in\{0,\ldots,r-1\}$ ที่เราต้องการคิดถึง ผลที่เราได้จากกระบวนการประมาณเฟสจะเป็นการประมาณ

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

โดยทำงานภายใต้สมมติฐานว่าเราไม่รู้ทั้ง $k$ และ $r$ สิ่งนี้อาจหรืออาจไม่ช่วยให้เราระบุ $r$ ได้ ตัวอย่างเช่น ถ้า $k = 0$ เราจะได้การประมาณ $y/2^m$ ถึง $0$ ซึ่งน่าเสียดายไม่บอกอะไรเรา อย่างไรก็ตาม นี่เป็นกรณีที่ไม่ปกติ สำหรับค่าอื่นๆ ของ $k$ เราจะสามารถเรียนรู้บางอย่างเกี่ยวกับ $r$ ได้อย่างน้อย

เราสามารถใช้อัลกอริทึมที่รู้จักกันในชื่อ อัลกอริทึมเศษส่วนต่อเนื่อง เพื่อแปลงการประมาณ $y/2^m$ ของเราเป็นเศษส่วนที่ใกล้เคียง — รวมถึง $k/r$ ถ้าการประมาณดีพอ เราจะไม่อธิบายอัลกอริทึมเศษส่วนต่อเนื่องที่นี่ แต่นี่คือคำกล่าวของข้อเท็จจริงที่ทราบเกี่ยวกับอัลกอริทึมนี้

ข้อเท็จจริง

กำหนดจำนวนเต็ม $N\geq 2$ และจำนวนจริง $\alpha\in(0,1)$ มีการเลือกจำนวนเต็ม $u,v\in\{0,\ldots,N-1\}$ ที่มี $v\neq 0$ และ $\gcd(u,v)=1$ ตอบสนอง $\vert \alpha - u/v\vert < \frac{1}{2N^2}$ ได้มากที่สุดหนึ่งแบบ กำหนด $\alpha$ และ $N$ อัลกอริทึมเศษส่วนต่อเนื่อง หา $u$ และ $v$ หรือรายงานว่าไม่มีอยู่ อัลกอริทึมนี้สามารถนำไปใช้งานเป็น Circuit บูลีนที่มีขนาด $O((\operatorname{lg}(N))^3)$

ถ้าเรามีการประมาณที่ใกล้เคียงมาก $y/2^m$ ถึง $k/r$ และเราเรียกใช้อัลกอริทึมเศษส่วนต่อเนื่องสำหรับ $N$ และ $\alpha = y/2^m$ เราจะได้ $u$ และ $v$ ตามที่อธิบายในข้อเท็จจริง การวิเคราะห์ข้อเท็จจริงช่วยให้เราสรุปได้ว่า

$$\frac{u}{v} = \frac{k}{r}.$$

สังเกตโดยเฉพาะว่าเราไม่จำเป็นต้องเรียนรู้ $k$ และ $r$ เราเรียนรู้เพียง $k/r$ ในรูปแบบต่ำสุดเท่านั้น

ตัวอย่างเช่น และดังที่เราสังเกตไปแล้ว เราจะไม่ได้เรียนรู้อะไรจาก $k=0$ แต่นั่นเป็นค่าเดียวของ $k$ ที่เกิดเหตุการณ์นั้น เมื่อ $k$ ไม่ใช่ศูนย์ มันอาจมีตัวประกอบร่วมกับ $r$ แต่จำนวน $v$ ที่เราได้จากอัลกอริทึมเศษส่วนต่อเนื่องต้องอย่างน้อยหาร $r$ ได้

มันไม่ชัดเจนเลย แต่เป็นความจริงว่าถ้าเรามีความสามารถในการเรียนรู้ $u$ และ $v$ สำหรับ $u/v = k/r$ สำหรับ $k\in\{0,\ldots,r-1\}$ ที่เลือก แบบสม่ำเสมอแบบสุ่ม เราจะมีโอกาสสูงมากที่จะสามารถกู้คืน $r$ ได้หลังจากตัวอย่างเพียงไม่กี่ตัว โดยเฉพาะ ถ้าการเดาของเรา $r$ คือ ตัวคูณร่วมน้อย ของค่าทั้งหมดสำหรับตัวส่วน $v$ ที่เราสังเกต เราจะถูกต้องด้วยความน่าจะเป็นสูง พูดอย่างเป็นสัญชาตญาณ ค่า $k$ บางค่าไม่ดีเพราะมันมีตัวประกอบร่วมกับ $r$ และตัวประกอบเหล่านั้นถูกซ่อนจากเราเมื่อเราเรียนรู้ $u$ และ $v$ แต่การเลือก $k$ แบบสุ่ม ไม่น่าจะซ่อนตัวประกอบของ $r$ ได้นานนัก และความน่าจะเป็นที่เราเดา $r$ ไม่ถูกต้องโดยการคำนวณตัวคูณร่วมน้อยของตัวส่วนที่เราสังเกตลดลงแบบเอกซ์โปเนนเชียลตามจำนวนตัวอย่าง

ยังคงต้องแก้ไขปัญหาว่าเราจะหาเวกเตอร์เฉพาะ $\vert\psi_k\rangle$ ของ $M_a$ เพื่อเรียกใช้กระบวนการประมาณเฟสได้อย่างไร ที่จริง เราไม่จำเป็นต้องสร้างมันเลย!

สิ่งที่เราจะทำแทนคือเรียกใช้กระบวนการประมาณเฟสกับสถานะ $\vert 1\rangle$ ซึ่งหมายถึงการเข้ารหัสไบนารี $n$ บิตของจำนวน $1$ แทนเวกเตอร์เฉพาะ $\vert\psi\rangle$ ของ $M_a$ จนถึงตอนนี้เราพูดถึงแค่การเรียกใช้กระบวนการประมาณเฟสกับเวกเตอร์เฉพาะตัวหนึ่ง แต่ไม่มีอะไรขัดขวางเราจากการเรียกใช้กระบวนการนี้กับสถานะอินพุตที่ไม่ใช่เวกเตอร์เฉพาะของ $M_a$ และนั่นคือสิ่งที่เราทำที่นี่กับสถานะ $\vert 1\rangle$ (นี่ไม่ใช่เวกเตอร์เฉพาะของ $M_a$ เว้นแต่ $a=1$ ซึ่งไม่ใช่การเลือกที่เราสนใจ)

เหตุผลในการเลือกสถานะ $\vert 1\rangle$ แทนเวกเตอร์เฉพาะของ $M_a$ คือสมการต่อไปนี้เป็นความจริง

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

วิธีหนึ่งในการตรวจสอบสมการนี้คือเปรียบเทียบผลคูณภายในของทั้งสองข้างกับสถานะฐานมาตรฐานแต่ละตัว โดยใช้สูตรที่กล่าวถึงก่อนหน้าในบทเรียนเพื่อช่วยประเมินผลลัพธ์ทางขวามือ ผลที่ตามมาคือเราจะได้ผลการวัดที่เหมือนกันอย่างแม่นยำกับที่เราเลือก $k\in\{0,\ldots,r-1\}$ แบบสม่ำเสมอแบบสุ่มและใช้ $\vert\psi_k\rangle$ เป็นเวกเตอร์เฉพาะ

รายละเอียดมากขึ้น ลองจินตนาการว่าเราเรียกใช้กระบวนการประมาณเฟสพร้อมสถานะ $\vert 1\rangle$ แทนเวกเตอร์เฉพาะ $\vert\psi_k\rangle$ ตัวใดตัวหนึ่ง หลังจากการแปลงฟูริเยร์ควอนตัมผกผันถูกทำ สิ่งนี้จะเหลือเราพร้อมสถานะ

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

โดยที่

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

เวกเตอร์ $\vert\gamma_k\rangle$ แทนสถานะของ Qubit บนสุด $m$ ตัวหลังจากอินเวิร์สของการแปลงฟูริเยร์ควอนตัมถูกทำกับพวกมัน

ดังนั้น โดยอาศัยข้อเท็จจริงที่ว่า $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ เป็นเซตออร์โธนอร์มอล เราพบว่าการวัด Qubit บนสุด $m$ ตัว ให้การประมาณ $y/2^m$ ถึงค่า $k/r$ โดยที่ $k\in\{0,\ldots,r-1\}$ ถูกเลือกแบบสม่ำเสมอแบบสุ่ม ดังที่เราพูดถึงไปแล้ว สิ่งนี้ช่วยให้เราเรียนรู้ $r$ ด้วยระดับความเชื่อมั่นสูงหลังจากการรันอิสระหลายครั้ง ซึ่งเป็นเป้าหมายของเรา

ต้นทุนรวม

ต้นทุนในการสร้าง controlled-unitary $M_a^k$ แต่ละตัวคือ $O(n^2)$ มี controlled-unitary $m$ การดำเนินการ และเรามี $m = O(n)$ ดังนั้นต้นทุนรวมสำหรับ controlled-unitary คือ $O(n^3)$ นอกจากนี้ เรามี Gate Hadamard $m$ ตัว (ซึ่งให้ $O(n)$ ต่อต้นทุน) และการแปลงฟูริเยร์ควอนตัมผกผันให้ $O(n^2)$ ต่อต้นทุน ดังนั้น ต้นทุนของ controlled-unitary ครอบงำต้นทุนของกระบวนการทั้งหมด — ซึ่งจึงเป็น $O(n^3)$

นอกจาก Circuit ควอนตัมเอง มีการคำนวณแบบคลาสสิกสองสามอย่างที่ต้องทำระหว่างทาง ซึ่งรวมถึงการคำนวณกำลัง $a^k$ ใน $\mathbb{Z}_N$ สำหรับ $k = 2, 4, 8, \ldots, 2^{m-1}$ ซึ่งจำเป็นสำหรับการสร้าง Gate controlled-unitary รวมถึงอัลกอริทึมเศษส่วนต่อเนื่องที่แปลงการประมาณของ $\theta$ เป็นเศษส่วน การคำนวณเหล่านี้สามารถทำได้โดย Circuit บูลีนที่มีต้นทุนรวม $O(n^3)$

ตามปกติ ขอบเขตทั้งหมดเหล่านี้สามารถปรับปรุงได้โดยใช้อัลกอริทึมที่เร็วแบบอาซิมโทติก ขอบเขตเหล่านี้สมมติว่าเราใช้อัลกอริทึมมาตรฐานสำหรับการดำเนินการคำนวณพื้นฐาน

การแยกตัวประกอบด้วยการหาอันดับ

สิ่งสุดท้ายที่เราต้องพูดถึงคือวิธีที่การแก้ปัญหาการหาอันดับช่วยเราในการแยกตัวประกอบ ส่วนนี้เป็นแบบคลาสสิกล้วนๆ — ไม่มีส่วนเกี่ยวข้องกับการประมวลผลเชิงควอนตัมโดยเฉพาะ

นี่คือแนวคิดพื้นฐาน เราต้องการแยกตัวประกอบจำนวน $N$ และเราสามารถทำสิ่งนี้ แบบวนซ้ำ โดยเฉพาะ เราสามารถเน้นที่งานของการ แยก $N$ ซึ่งหมายถึงการหาจำนวนเต็มสองตัว $b,c\geq 2$ ที่ $N = bc$ สิ่งนี้เป็นไปไม่ได้ถ้า $N$ เป็นจำนวนเฉพาะ แต่เราสามารถทดสอบอย่างมีประสิทธิภาพเพื่อดูว่า $N$ เป็นจำนวนเฉพาะหรือไม่โดยใช้อัลกอริทึมการทดสอบจำนวนเฉพาะก่อน และถ้า $N$ ไม่ใช่จำนวนเฉพาะเราจะพยายามแยกมัน เมื่อเราแยก $N$ เราสามารถวนซ้ำกับ $b$ และ $c$ จนกว่าตัวประกอบทั้งหมดของเราจะเป็นจำนวนเฉพาะและเราได้การแยกตัวประกอบเฉพาะของ $N$

การแยกจำนวนคู่เป็นเรื่องง่าย: เราแค่ออก $2$ และ $N/2$

มันง่ายเช่นกันที่จะแยกกำลังสมบูรณ์ ซึ่งหมายถึงตัวเลขในรูปแบบ $N = s^j$ สำหรับจำนวนเต็ม $s,j\geq 2$ เพียงแค่ ประมาณรากที่สอง $N^{1/2},$ รากที่สาม $N^{1/3},$ รากที่สี่ $N^{1/4},$ และต่อๆ ไป แล้วตรวจสอบจำนวนเต็มใกล้เคียงว่าเป็นผู้ต้องสงสัยสำหรับ $s$ เราไม่จำเป็นต้องไปเกิน $\log(N)$ ขั้นตอนในลำดับนี้ เพราะที่จุดนั้นรากจะต่ำกว่า $2$ และจะไม่เปิดเผยผู้สมัครเพิ่มเติม

ดีที่เราทำทั้งสองสิ่งนี้ได้ เพราะการหาอันดับจะไม่ช่วยเราในการแยกตัวประกอบจำนวนคู่หรือสำหรับ กำลังเฉพาะ ที่จำนวน $s$ เป็นจำนวนเฉพาะ อย่างไรก็ตาม ถ้า $N$ เป็นเลขคี่และไม่ใช่กำลังเฉพาะ การหาอันดับช่วยให้เราแยก $N$ ได้

อัลกอริทึมแบบน่าจะเป็นสำหรับแยกจำนวนเต็มคี่ประกอบ N ที่ไม่ใช่กำลังเฉพาะ

1. สุ่มเลือก $a\in\{2,\ldots,N-1\}$

2. คำนวณ $d=\gcd(a,N)$

3. ถ้า $d > 1$ ให้ออก $b = d$ และ $c = N/d$ แล้วหยุด มิฉะนั้นดำเนินการต่อไปโดยรู้ว่า $a\in\mathbb{Z}_N^{\ast}$

4. ให้ $r$ เป็นอันดับของ $a$ มอดุโล $N$ (นี่คือที่ที่เราต้องการการหาอันดับ)

5. ถ้า $r$ เป็นเลขคู่:

   5.1 คำนวณ $x = a^{r/2} - 1$ มอดุโล $N$
   5.2 คำนวณ $d = \gcd(x,N)$
   5.3 ถ้า $d>1$ ให้ออก $b=d$ และ $c = N/d$ แล้วหยุด

6. ถ้าถึงจุดนี้ อัลกอริทึมล้มเหลวในการหาตัวประกอบของ $N$

การรันอัลกอริทึมนี้อาจล้มเหลวในการหาตัวประกอบของ $N$ โดยเฉพาะ สิ่งนี้เกิดขึ้นในสองสถานการณ์:

• อันดับของ $a$ มอดุโล $N$ เป็นเลขคี่
• อันดับของ $a$ มอดุโล $N$ เป็นเลขคู่และ $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1$

โดยใช้ทฤษฎีจำนวนพื้นฐานสามารถพิสูจน์ได้ว่า สำหรับการเลือก $a$ แบบสุ่ม ด้วยความน่าจะเป็นอย่างน้อย $1/2$ ทั้งสองเหตุการณ์นี้จะไม่เกิดขึ้น ที่จริง ความน่าจะเป็นที่เหตุการณ์ใดเหตุการณ์หนึ่งเกิดขึ้นมีมากที่สุด $2^{-(m-1)}$ โดยที่ $m$ คือจำนวนตัวประกอบเฉพาะที่ต่างกันของ $N$ ซึ่งเป็นเหตุผลที่ต้องการสมมติฐานว่า $N$ ไม่ใช่กำลังเฉพาะ (สมมติฐานว่า $N$ เป็นเลขคี่ก็จำเป็นสำหรับข้อเท็จจริงนี้ให้เป็นจริงด้วย)

นี่หมายความว่าการรันแต่ละครั้งมีโอกาสอย่างน้อย 50% ที่จะแยก $N$ ดังนั้น ถ้าเราเรียกใช้อัลกอริทึม $t$ ครั้ง สุ่มเลือก $a$ ในแต่ละครั้ง เราจะสำเร็จในการแยก $N$ ด้วยความน่าจะเป็นอย่างน้อย $1 - 2^{-t}$

แนวคิดพื้นฐานของอัลกอริทึมมีดังนี้ ถ้าเรามีการเลือก $a$ ที่อันดับ $r$ ของ $a$ มอดุโล $N$ เป็นเลขคู่ แล้ว $r/2$ เป็นจำนวนเต็มและเราสามารถพิจารณาตัวเลข

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

โดยใช้สูตร $Z^2 - 1 = (Z+1)(Z-1)$ เราสรุปได้ว่า

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

ตอนนี้ เรารู้ว่า $a^r \; (\textrm{mod}\; N) = 1$ จากนิยามของอันดับ — ซึ่งเป็นอีกวิธีในการบอกว่า $N$ หาร $a^r - 1$ ได้ลงตัว นั่นหมายความว่า $N$ หารผลคูณนี้ได้ลงตัว

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

เพื่อให้สิ่งนี้เป็นจริง ตัวประกอบเฉพาะทั้งหมดของ $N$ ต้องเป็นตัวประกอบเฉพาะของ $a^{r/2} - 1$ หรือ $a^{r/2} + 1$ (หรือทั้งคู่) — และสำหรับการสุ่มเลือก $a$ มันไม่น่าจะเป็นไปได้ที่ตัวประกอบเฉพาะทั้งหมดของ $N$ จะหารพจน์ใดพจน์หนึ่งและไม่มีตัวใดหารอีกพจน์หนึ่ง มิฉะนั้น ตราบเท่าที่ตัวประกอบเฉพาะบางส่วนของ $N$ หารพจน์แรกและบางส่วนหารพจน์ที่สอง เราจะสามารถหาตัวประกอบที่ไม่ใช่ตัวเล็กน้อยของ $N$ ได้โดยการคำนวณ GCD กับพจน์แรก