ขั้นตอนวิธีของชอร์

ขั้นตอนวิธีของชอร์ ตั้งชื่อตามนักคณิตศาสตร์ชื่อปีเตอร์ ชอร์ที่คิดขึ้นในปีค.ศ.1994 โดยขั้นตอนวิธีนี้เป็นขั้นตอนวิธีควอนตัม (ขั้นตอนวิธีที่ทำงานบนควอนตัมคอมพิวเตอร์) ที่ใช้ในการแยกตัวประกอบของจำนวนเต็ม ซึ่งโดยทั่วไปแล้วใช้ในการแก้ปัญหา:ให้จำนวนเต็ม N แล้วให้หาตัวประกอบเฉพาะของ N

ในควอนตัมคอมพิวเตอร์นั้น การแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์จะใช้เวลาในการทำงานไม่เกินฟังก์ชันพหุนาม (Polynomial) ของขนาดข้อมูล โดยจะใช้เวลาเป็น O ( (log N) 3) ซึ่งแสดงให้เห็นว่าเป็นการแก้ปัญหาการแยกตัวประกอบของจำนวนเต็มที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ วิธีนี้จัดเป็นวิธีที่เร็วกว่าหลาย ๆ วิธีที่มีประสิทธิภาพที่รู้จักกันทั่ว ๆ ไปทีมักจะใช้เวลาเป็นฟังก์ชันเลขชี้กำลัง (Exponential) ขนาดของข้อมูล

ให้ควอนตัมคอมพิวเตอร์มีจำนวนคิวบิตที่เพียงพอ ขั้นตอนวิธีของชอร์จะสามารถถอดรหัสประเภทระบบเข้ารหัสแบบกุญแจอสมมาตรได้ ยกตัวอย่างเช่น รหัสลับRSA โดยRSAนั้นตั้งอยู่บนสมมติฐานที่ว่าการคำนวณหาตัวประกอบของเลขที่มีจำนวนมาก ๆ นั้นเป็นไปไม่ได้ เท่าที่รู้กันสมมติฐานนี้ใช้ได้สำหรับคอมพิวเตอร์ทั่วไป และไม่มีขั้นตอนวิธีใดที่จะทำงานในเวลาไม่เกินฟังก์ชันพหุนาม อย่างไรก็ตามขั้นตอนวิธีของชอร์แสดงให้เห็นถึงวิธีการแยกตัวประกอบที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ เพื่อให้ควอนตัมคอมพิวเตอร์มีขนาดที่ใหญ่พอที่จะถอดรหัสRSAได้ จึงสร้างแรงจูงใจอย่างมากในการออกแบบและการสร้างควอนตัมคอมพิวเตอร์ และสำหรับศึกษาแบบวิธีการบนควอนตัมคอมพิวเตอร์ใหม่ ๆ ในขณะที่ก็มีการให้การสนับสนุนการวิจัยระบบการเข้ารหัสแบบใหม่เพื่อสร้างความปลอดภัยจากควอนตัมคอมพิวเตอร์ เรียกว่าวิทยาการเข้ารหัสลับหลังควอนตัม (post-quantum cryptography)

กระบวนการของขั้นตอนวิธีของชอร์

ปัญหาที่เราต้องการจะหาคำตอบคือ: ให้$N$เป็นจำนวนประกอบที่เป็นเลขคี่ ให้หาจำนวนเต็ม d ที่อยู่ระหว่าง 1และ$N$ และ หาร$N$ลงตัว เราสนใจ$N$ที่มีค่าเป็นจำนวนคี่เนื่องจากถ้าเป็นจำนวนคู่จะมี “2” เป็นตัวประกอบเฉพาะอยู่แล้ว โดยเราสามารถใช้การทดสอบจำนวนเฉพาะเพื่อหาว่า $N$ นั้นเป็นจำนวนประกอบหรือไม่

นอกจากนั้นแล้ว เรายังต้องการ$N$ที่ไม่ใช่เลขยกกำลังของจำนวนเฉพาะ เราสามารถทดสอบโดยใช้รากที่2, รากที่4, ....., รากที่ k ของ N โดยที่ $k\leq \log _{2}(N)$ และต้องตรวจสอบว่าไม่มีจำนวนใดในนั้นที่เป็นจำนวนเต็ม

เนื่องจาก $N$ ไม่ใช่เลขยกกำลังของจำนวนเฉพาะ คำตอบต้องเป็นผลลัพธ์ของจำนวนเฉพาะสองตัวที่มีค่ามากกว่า 1 จากทฤษฎีบทเศษเหลือของจีน โดยจุดมุ่งหมายของอัลกอริทึ่มนี้คือการหาตัวประกอบของNที่มีค่าไม่เป็น 1 และ -1

ในการแยกตัวประกอบโดยใช้ขั้นตอนวิธีของชอร์นั้นประกอบด้วย2ส่วนคือ

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

ส่วนลดรูปปัญหา

1. หาคาบซ้ำ ๆ (r) ที่เกิดจากผลของฟังก์ชัน:

   $f(x)=a^{x}\ {\mbox{mod}}\ N$

   นั่นคือ ลำดับ$r$ของ$a$ใน$(\mathbb {Z} _{N})^{\times }$ที่เป็นจำนวนเต็มบวกที่น้อยที่สุดสำหรับ$f(x+r)=f(x)$
2. ถ้า a^r-1 หารด้วย N ลงตัว และ r เป็นเลขคู่ แยกตัวประกอบของ a ^r-1 ได้เป็น a^r/2-1 กับ a^r/2+1
3. หรม.ของa^r/2 ± 1 กับ N คือตัวประกอบที่เราสนใจของN

ส่วนควอนตัม: ใช้หาคาบที่เกิดจากฟังก์ชัน

1. สร้างหน่วยความจำของควอนตัมคอมพิวเตอร์ขึ้น2ส่วน
   1. ส่วนแรกใช้เก็บจำนวนเต็มxที่มีค่าตั้งแต่0ถึงq-1 โดยที่qเป็นเลขยกกำลังของ2 ที่ $N^{2}\leq q<2N^{2}$
   2. ใช้เก็บผลลัพธ์ฟังก์ชัน $f(x)=a^{x}\ {\mbox{mod}}\ N$ ซึ่งเป็นไปได้ตั้งแต่ 0 ถึง N −1 โดยจำนวนเต็มที่เก็บไว้ในหน่วยความจำแต่ละส่วนจะแทนด้วยฐาน (base) แต่ละตัวของหน่วยความจำ และสถานะของหน่วยความจำจะเป็นผลรวม (superposition) ของฐานต่าง ๆ ซึ่งมีแอมพลิจูด (amplitude) เท่ากันทุกฐาน

   เช่น ถ้าN=15 qจะมีค่าเป็น2^8ซึ่งมากกว่า 15^2 แต่น้อยกว่า 2*15^2 จะได้ x มีค่าตั้งแต่ 0-255 ซึ่งต้องใช้หน่วยความจำส่วนแรกขนาด 8 คิวบิต เพื่อเก็บตัวเลข 256 ตัว คือ

   • ฐาน 00000000 แทนเลข 0
   • ฐาน 00000001 แทนเลข 1
   • ฐาน 00000010 แทนเลข 2
   • ฐาน 00000011 แทนเลข 3
   • ฐาน 11111111 แทนเลข 255
   และหน่วยความจำส่วนที่สองต้องใช้ 4 คิวบิตเพื่อเก็บเลข 0 ถึง 14
2. ตอนเริ่มต้นนั้นหน่วยความจำของควอนตัมคอมพิวเตอร์จะอยู่ในสถานะ

   $q^{-1/2}\sum _{x=0}^{q-1}\left|x\right\rangle \left|0\right\rangle$

   เมื่อ$\left|x\right\rangle$ เป็นฐานที่แทนจำนวนเต็ม x
3. คำนวณค่าของฟังก์ชัน$f(x)=a^{x}\ {\mbox{mod}}\ N$จากค่า x ในหน่วยความจำส่วนแรกแล้วเก็บผลลัพธ์ไว้ในส่วนที่สอง ซึ่งจะให้สถานะของหน่วยความจำเป็น

   $q^{-1/2}\sum _{x=0}^{q-1}\left|x\right\rangle \left|f(x)\right\rangle$

   เนื่องจากคุณสมบัติที่ทำงานหลาย ๆ อย่างขนานกันไปได้ของควอนตัมคอมพิวเตอร์ จึงสามารถคำนวณค่า$f(x)=a^{x}\ {\mbox{mod}}\ N$ของจำนวนx ต่าง ๆ ได้พร้อม ๆ กันในคราวเดียว ทำให้สามารถทำงานได้รวดเร็วกว่าคอมพิวเตอร์ปกติซึ่งต้องคำนวณทีละตัว
4. ทำการวัดสถานะของหน่วยความจำส่วนที่สองซึ่งเก็บผลลัพธ์ไว้ การวัดนี้จะทำให้ฟังก์ชันคลื่นของหน่วยความจำเกิดการยุบรวมกัน เหลือเพียงฐานที่ทำให้เกิดผลลัพธ์ที่วัดได้ ถ้าวัดสถานะของผลลัพธ์ได้เป็น k จะเหลือเพียงฐาน

   $x=b,b+r,b+2r,b+3r,...,b+nr$

   เมื่อ:b คือจำนวนเต็มที่น้อยที่สุดที่ $f(b)=a^{b}\ {\mbox{mod}}\ N=k$

   r คือคาบของ $f(x)$

   n คือจำนวนเต็มที่มากที่สุดที่น้อยกว่า (q−b) /r

   หลังทำการวัดแล้วจะได้สถานะของหน่วยความจำเป็น

   $||A||^{-1/2}\sum _{x'=x'\in A}\left|x',k\right\rangle$

   เมื่อ A คือเซตของ x ซึ่ง ให้ $a^{x}\ {\mbox{mod}}\ N=k$ และ A คือจำนวนสมาชิกของเซตดังกล่าว
5. แปลงหน่วยความจำส่วนแรกด้วยการแปลงฟูริเยร์ไม่ต่อเนื่อง

   $\left|x\right\rangle \rightarrow q^{1/2}\sum _{c=0}^{q-1}e^{2\pi ixc/q}\left|c\right\rangle$

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

ประวัติของขั้นตอนวิธีของชอร์

แนวคิดที่จะใช้การคำนวณต่าง ๆ บนอุปกรณ์ที่อยู่ทำงานด้วยพื้นฐานของกลศาสตร์ควอนตัมเริ่มมีการนำเสนอมาตั้งแค่ทศวรรษที่ 1970 จากทั้งนักคอมพิวเตอร์ และนักฟิสิกส์หลายคน โดยแนวคิดนี้เริ่มต้นมาจากการที่พวกเขาทั้งหลายได้เริ่มไตร่ตรองถึงขีดจำกัดในการคำนวณ เนื่องมาจากกฎของมัวร์ (Moore’s law) ซึ่งจะทำให้ขนาดวงจรบนชิพซิลิกอนนั้นมีขนาดเล็กลงไปเรื่อย ๆ จนถึงขนาด 2-3 อะตอม ซึ่งถ้าหากมีขนาดเล็กขนาดนั้นก็จะทำให้อะตอมแสดงคุณสมบัติของควอนตัมออกมาในวงจร จึงเกิดแนวคิดเกี่ยวกับคอมพิวเตอร์ชนิดใหม่ที่จะทำงานบนพื้นฐานของกฎทางกลศาสตร์ควอนตัม

ในปี 1982 เฟย์แมน ได้เสนอว่า มีความเป็นไปได้ที่ควอนตัมคอมพิวเตอร์จะทำงานได้เร็วกว่าคอมพิวเตอร์ดั้งเดิมที่มีประสิทธิภาพเป็นฟังก์ชันเลขชี้กำลัง และเครื่องจักรทัวริง (Turing machine) นั้นไม่สามารถจำลองระบบทางควอนตัมได้ หากไม่ใช้ขั้นตอนเป็นฟังก์ชันเลขชี้กำลังของหน่วยย่อยในระบบ นอกจากนี้ เฟย์แมน ยังได้แนะไว้ว่า หากใช้เครื่องมือที่มีพฤติกรรมแบบควอนตัมในตัวเองแล้ว จะสามารถทำการจำลองระบบทางควอนตัมได้โดยไม่ต้องใช้ขั้นตอนเป็นเอ็กโพเนนเชียล ซึ่งจะทำให้นักวิทยาศาสตร์สามารถทำการทดลองทางกลศาสตร์ควอนตัมบนควอนตัมคอมพิวเตอร์ได้

ต่อมาในปี 1985 ดอยซ์ ได้ขยายแนวความคิดของ เฟย์แมน ออกไปว่า ระบบทางฟิสิกส์ใด ๆ ก็ตามสามารถจำลองได้ด้วยควอนตัมคอมพิวเตอร์ ซึ่งแสดงให้เห็นว่าควอนตัมคอมพิวเตอร์มีความสามารถมากกว่าคอมพิวเตอร์ดั้งเดิมทั้งหมด หลังจากการตีพิมพ์ผลงานชิ้นนี้จึงเริ่มมีการหาทางประยุกต์ใช้ควอนตัมคอมพิวเตอร์

แต่ความพยายามในการหาวิธีประยุกต์ใช้ควอนตัมคอมพิวเตอร์นี้ ยังไม่ประสบผลสำเร็จจนกระทั่ง ปีเตอร์ ชอร์ นักวิจัยของเอทีแอนด์ที (AT&T) ได้เสนอวิธีการแก้ปัญหาการแยกตัวประกอบด้วยควอนตัมคอมพิวเตอร์ในปี 1994 โดย ชอร์ แสดงให้เห็นว่าจะต้องรวมตัวดำเนินการทางคณิตศาสตร์ที่ออกแบบมาเฉพาะกับควอนตัมคอมพิวเตอร์นั้นเข้าด้วยกันอย่างไร จึงจะสามารถทำการแยกตัวประกอบของจำนวนขนาดใหญ่ได้ จากจุดนี้เองทำให้ควอนตัมคอมพิวเตอร์ได้เปลี่ยนจากคำถามในวงการวิชาการ มาเป็นความสนใจของโลกที่จะสร้างควอนตัมคอมพิวเตอร์ขึ้นมาจริง ๆ

จนกระทั่งในปี 2001 ลีเว็น วานเดอร์ไซเพ็น นักวิจัยของไอบีเอ็ม และคณะ ได้ใช้ควอนตัมคอมพิวเตอร์แบบ เอ็นเอ็มอาร์ (NMR) ขนาด 7 คิวบิต แก้ปัญหาการแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์ โดยทำการแยกตัวประกอบของ 15 ได้เป็นผลสำเร็จ

ลำดับเหตุการณ์ในการคิดค้นขั้นตอนวิธีของชอร์

ตั้งแต่อดีตจนถึงปัจจุบัน ขั้นตอนวิธีของชอร์ได้มีการพัฒนาในการคิดค้น การออกแบบวงจร และ การประยุกต์ใช้จริงตามลำดับ ดังนี้

ปี 1982 ริชาร์ด เฟย์แมนเสนอว่าควอนตัมคอมพิวเตอร์สามารถจำลองระบบทางควอนตัมได้ด้วยขั้นตอนที่ไม่เป็นฟังก์ชันเลขชี้กำลัง

ปี 1985 เดวิด ดอยซ์เสนอว่าควอนตัมคอมพิวเตอร์สามารถจำลองระบบทางฟิสิกส์ใด ๆ ได้อย่างสมบูรณ์แบบ

ปี 1994 ปีเตอร์ ชอร์เสนอขั้นตอนวิธีสำหรับแยกตัวประกอบด้วยควอนตัมคอมพิวเตอร์

ปี 1996 เวนดรัลและคณะ ออกแบบวงจรควอนตัมอย่างง่ายสำหรับ ขั้นตอนวิธีของชอร์ ใช้หน่วยความจำประมาณ 5L คิวบิต เมื่อ L เป็นขนาดของอินพุต และใช้เวลาไม่เกินL3

ปี 1998 กอสเซ็ตต์ออกแบบวงจรควอนตัมสำหรับ ขั้นตอนวิธีของชอร์ ให้ทำงานได้อย่างรวดเร็วไม่เกิน Llog L และใช้หน่วยความจำไม่เกิน L2 คิวบิต

ปี 1998 ซาลกาออกแบบวงจรควอนตัมสำหรับ ขั้นตอนวิธีของชอร์ ที่ใช้หน่วยความจำ 50Lคิวบิต และใช้เวลาทำงานประมาณ 217 L2

ปี 2001 ลีเว็น วานเดอร์ไซเพ็น นักวิจัยของไอบีเอ็มและคณะ ได้ใช้ควอนตัมคอมพิวเตอร์แบบ NMR ขนาด 7 คิวบิต แยกตัวประกอบของ 15 ด้วย ขั้นตอนวิธีของชอร์

ปี 2003 บิวเรการ์ดออกแบบวงจรควอนตัมสำหรับ ขั้นตอนวิธีของชอร์ ที่ใช้หน่วยความจำน้อยที่สุดเพียง 2L คิวบิต แตใช้เวลาในการทำงานประมาณ 32L3

ปี 2005 จูฮา วาติไอเน็นและคณะใช้โจเซ็ปสันชาร์จคิวบิก (Josephson charge qubit) แยกตัวประกอบของ 21

ปี 2005 ออสติน ฟาวเลอร์ แห่งมหาวิทยาลัยเมลเบิร์น ประเทศออสเตรเลีย และคณะได้ประดิษฐ์วงจรควอนตัมคอมพิวเตอร์เพื่อแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์ ที่ใช้หน่วยความจำ 2L + 4 คิวบิต และใชเวลาทำงานเป็น 32L3

อ้างอิง

• Ekert, Artur and Jozsa, Richard. 1996. “Quantum Computation and Shor’s Factoring Algorithm.” Review of Modern Physics, Vol. 68, No. 3, July 1996; p.733.
• Fowler, Austen et al. 2005. “Implementation of Shor’s Algorithm on a Linear Nearest Neighbour Qubit Array.” quant-ph/0402196
• Hayward, Matthew. 2005. “Quantum Computing and Shor’s Algorithm.” [Online] AvailabeURL: http://alumni.imsa.edu/~matth/quant/299/paper/index.html (5 เมษายน 2549)
• Singh, Simon. 1999. The Code Book: the Evolution of Secrecy from Mary Queen of Scots to Quantum Cryptography. 1st ed.
• Shor, P. W., 1994, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA); p.124.
• Vandersypen, Lieven and others. 2001. “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance.” Nature, Vol. 414, December 2001; p.883.
• Vartiainen, Juha et al. “Implementing Shor’s algorithm on Josephson Charge Qubits.”. quant-ph/0308171
• www.kmitl.ac.th/dslabs/ksripima/readme/49/technical...49/watan.pdf

ดูเพิ่ม

• Nielsen, Michael A. & Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge University Press.
• Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 019857049X
• "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). Scott Aaronson suggests the following 12 references as further reading (out of "the 10¹⁰⁵⁰⁰⁰ quantum algorithm tutorials that are already on the web.") :
• Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput., 26 (5): 1484–1509, arXiv:quant-ph/9508027v2, Bibcode:1999SIAMR..41..303S, doi:10.1137/S0036144598347011. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
• Quantum Computing and Shor's Algorithm, Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document, also available as a 61 page PDF or postscript document.
• Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
• Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
• Chapter 6 Quantum Computation เก็บถาวร 2020-04-30 ที่ เวย์แบ็กแมชชีน, 91 page postscript document, Caltech, Preskill, PH229.
• Quantum computation: a tutorial by Samuel L. Braunstein.
• The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
• III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm, Lecture notes on Quantum computation, Cornell University, Physics 481-681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
• arXiv quant-ph/0303175 Shor's Algorithm for Factoring Large Integers. C. Lavor, L.R.U. Manssur, R. Portugal. Submitted on 29 Mar 2003. This work is a tutorial on Shor's factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra. 25 pages, 14 figures, introductory review.
• arXiv quant-ph/0010034 Shor's Quantum Factoring Algorithm, Samuel J. Lomonaco, Jr, Submitted October 9, 2000, This paper is a written version of a one hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
• Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.
• A Step Toward Quantum Computing: Entangling 10 Billion Particles เก็บถาวร 2011-01-20 ที่ เวย์แบ็กแมชชีน, from "Discover Magazine", Dated January 19, 2011.