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

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีของชอร์ ตั้งชื่อตามนักคณิตศาสตร์ชื่อปีเตอร์ ชอร์ที่คิดขึ้นในปีค.ศ.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 \le \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. ถ้า ar-1 หารด้วย N ลงตัว และ r เป็นเลขคู่ แยกตัวประกอบของ a r-1 ได้เป็น ar/2-1 กับ ar/2+1
  3. หรม.ของar/2 ± 1 กับ N คือตัวประกอบที่เราสนใจของN

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

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

    เช่น ถ้าN=15 qจะมีค่าเป็น2^8ซึ่งมากกว่า 152 แต่น้อยกว่า 2*152 จะได้ 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 คือจำนวนเต็มที่มากที่สุดที่น้อยกว่า (qb) /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

ดูเพิ่ม[แก้]