อัลกอริทึมของชอร์

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

อัลกอริทึมของชอร์ (Shor’s Algorithm) เป็นควอนตัมอัลกอริทึมสำหรับการแยกตัวประกอบจำนวนเต็มขนาดใหญ่ อัลกอริทึมนี้ได้รับความสนใจเป็นอย่างมากเนื่องจากมันท้าทายกลไกการเข้ารหัสในยุคปัจจุบันอย่าง RSA โชคดีที่อัลกอริทึมนี้ออกแบบไว้สำหรับทำงานบนควอนตัมคอมพิวเตอร์ ซึ่งในปัจจุบันยังไม่ค่อยเสถียรนักและมีจำนวนคิวบิตที่ต่ำ มันจึงยังไม่สามารถแยกตัวประกอบอะไรหนักหนาได้ RSA จึงยังปลอดภัยดีอยู่ (แต่อนาคตใครจะรู้)

ความสำคัญของการแยกตัวประกอบ
กลไกการเข้ารหัสของ RSA นั้น ผู้รับข้อความจะหลีกเลี่ยงการบอก Key ในการเข้ารหัสให้แก่ผู้ส่งข้อความ แต่จะบอกผลคูณของตัวเลขซึ่งเกิดจาก Key ไปให้ผู้ส่งข้อความแทน ซึ่งผู้ส่งข้อความเองก็ไม่สามารถรู้ได้ว่าตัวเลขนั้นคือผลคูณของอะไร แต่เอาตัวเลขนั้นไปใช้เข้ารหัสแล้วผู้รับถอดรหัสข้อความได้ก็แล้วกัน ในเมื่อผู้ส่งข้อความเองยังไม่รู้ Key ในการถอดรหัส ดังนั้นจึงไม่ต้องกลัวเลยว่าใครจะมาขโมยข้อมูลไประหว่างทาง เพราะถ้าไม่รู้ Key ยังไงก็ถอดไม่ได้ การรักษาความลับของข้อมูลจึงอยู่ที่การรักษาความลับไว้ว่า Key ที่แท้จริงคืออะไร ความยากในการแยกตัวประกอบหรือการหาต้นตอของผลคูณจึงเป็นหัวใจสำคัญของ RSA แค่โจทย์การแยกตัวประกอบธรรมดานี่แหละ แต่หากตัวเลขนั้นใหญ่พอ จะต้องใช้เวลาแกะนานขึ้นอย่างไม่น่าเชื่อ ซึ่งอัลกอริทึมในการแยกตัวประกอบที่เร็วที่สุดในปัจจุบันอย่าง GNFS ยังอาจต้องใช้เวลาถึงO\left(e^{{1.9}n^{1/3}(\log n)^{2/3} }\right) (โดยที่ n คือจำนวนบิตของตัวเลขที่จะแยก)
ปี 1994 นักคณิตศาสตร์ชาวอเมริกัน Peter Shor ได้นำเสนอควอนตัมอัลกอริทึมซึ่งกล่าวว่าสามารถแยกตัวประกอบได้ด้วยความเร็วO\left(n^2(\log n)(\log \log n)\right) เท่านั้น ซึ่งหมายถึงระดับความนานเปลี่ยนจาก sub-exponential เป็น polynomial เลยทีเดียว ถ้าทำได้จริงล่ะก็ การแยกตัวประกอบเลขขนาด 512 บิต ที่อาจใช้เวลาหลายล้านๆ ปี จะเหลือแค่นาทีเดียว น่าสนใจพอไหม

ภาพรวมของอัลกอริทึม
โจทย์ของเราคือ มีเลขจำนวนเต็มอยู่ตัวหนึ่ง ต้องการแยกตัวประกอบว่ามันเกิดจากอะไรคูณกับอะไร
เช่น 15 เกิดจาก 3 x 5 หรือ 35 เกิดจาก 5 x 7 เป็นต้น (คือจริงๆ RSA เค้าใช้ตัวเลขขนาดใหญ่นะ แต่เราใช้เลขเล็กๆ พอให้เห็นตัวอย่าง)

ภาพรวมขั้นตอนวิธีของชอร์เป็นดังนี้

  1. ให้ N คือจำนวนเต็มที่เราต้องการแยกตัวประกอบ สมมติตัวอย่างเป็นเลข 35
  2. สุ่มเลขจำนวนเต็มขึ้นมาหนึ่งเลข ตั้งแต่ 2 ถึง N-1 ขอเรียกตัวเลขนี้ว่า a สมมติตัวอย่างเป็นเลข 4
  3. หา ห.ร.ม. (หารร่วมมาก หรือ GCD, Greatest Common Divisor) ระหว่าง a กับ N
    หากได้ค่าที่ไม่ใช่ 1 แสดงว่า ห.ร.ม. ที่ได้นั่นแหละคือคำตอบ จบเลยไม่ต้องทำอะไรต่อแล้ว
    แต่หากได้เท่ากับ 1 ให้ดูขั้นตอนต่อไป

  4. ให้ไล่ค่าตัวแปร x ตั้งแต่ 0 ขึ้นไปเรื่อยๆ แล้วดูค่าของฟังค์ชัน f(x)=ax Mod N (Mod คือการหารเอาเศษ เช่น 5 Mod 3 ได้ 2)
    จะพบว่าฟังค์ชันนี้มีลักษณะเป็น pattern ซ้ำๆ หรือเป็นคาบ ให้หาว่าคาบของฟังค์ชันนี้มีค่าเท่าไหร่ และเรียกตัวเลขคาบนี้ว่า r
    จากตัวอย่าง N=35, a=4 จะได้ตารางระหว่างค่า x และ f(x) ดังนี้

    x 0 1 2 3 4 5 6 7 8 9
    f(x) 1 4 16 29 11 9 1 4 16 29

    f(x) มันจะเริ่มวนซ้ำทุกๆ 6 ตัว ดังนั้นคาบจากเลขสุ่มนี้ก็คือ 6

    คาบ r ที่หาได้นี้หากได้เลขคี่จะใช้ไม่ได้ ให้สุ่มค่า a ใหม่

  5. เช็คอีกหน่อยนึง ถ้าหากว่า ar/2 Mod N = -1 Mod N ให้สุ่มค่า a ใหม่
  6. ถึงจุดนี้เราก็พร้อมจะคำนวณค่าตัวประกอบแล้ว โดยให้หา ห.ร.ม. ระหว่าง ar/2±1 กับ N
    เช่นในตัวอย่างเราก็คือ หา ห.ร.ม. ระหว่าง 46/2+1 กับ 35 ดู จะได้ 5
    และ ห.ร.ม. ระหว่าง 46/2-1 กับ 35 จะได้ 7
    ดังนั้นก็จะได้คำตอบเป็นตัวประกอบคือ 5 กับ 7 จบการคำนวณ แยกตัวประกอบได้สำเร็จ
    แต่หากคำนวณ ห.ร.ม. แล้ว ดันได้แต่ 1 กับ N ออกมา ก็ต้องกลับไปสุ่มค่าใหม่อีกครั้ง

ภาพรวมวิธีการแยกตัวประกอบก็มีอยู่เท่านี้เองครับ ดูง่ายๆ แต่ไม่รู้ว่าคิดออกมาได้ยังไง

เร็วขึ้นได้อีกด้วยควอนตัม
ขั้นตอนที่กล่าวมาข้างต้นนั้นถือว่ายังเป็นวิธีการแบบคลาสสิกอยู่ คือยังไม่ได้เอาควอนตัมมาช่วย ดูเผินๆ ก็น่าจะใช้งานได้แล้ว แต่ปัญหาคือข้อ 4 คือขั้นตอนในการหาคาบ r หากว่าตัวเลข N ของเรามีค่ามาก และคาบ r มีขนาดใหญ่มาก กว่าจะไล่ค่า x จนพบว่ามีคาบเกิดขึ้น ย่อมต้องใช้เวลาเท่ากับจำนวน x ที่ไล่ไป ตรงจุดนี้เองที่ชอร์ได้นำเสนอวงจรควอนตัมง่ายๆ แต่ช่วยให้สามารถหาคำตอบได้เร็วขึ้นอีก (หากคุณยังไม่รู้จักสถานะควอนตัม, ควอนตัมเกต หรือวงจรควอนตัม แนะนำให้อ่านโพสที่แล้วดูก่อนนะครับ)

shor quantum circuitวงจรควอนตัมสำหรับการหาคาบ r ของฟังค์ชัน f(x)=ax Mod N
  • อธิบายภาพคือ เราจะมีควอนตัมรีจิสเตอร์อยู่สองสาย สายบนสำหรับค่า x สายล่างสำหรับค่า y หรือ f(x)
    สายล่างเราเตรียมไว้สำหรับ f(x) ที่เกิดจากการ Mod N ซึ่งยังไงก็มีค่าไม่เกิน N ดังนั้นเราใช้คิวบิตจำนวน n = log2N ก็พอ
    ส่วนสายบนเราเตรียมไว้สำหรับไล่ค่า x โดยเค้าบอกว่าต้องเผื่อพื้นที่ไว้อย่างน้อย N2 (อันนี้ไม่รู้ว่าพิสูจน์ยังไง) หรือใช้คิวบิตจำนวน m = 2n คิวบิต

  • เสร็จแล้วทำการ Hadamard ทั้ง m คิวบิตของ x คือทำให้มันกลายเป็น superposition (คิวบิตมีโอกาสเป็นทั้ง 0 และ 1) หมายความว่าเลขที่ออกอาจจะเป็นอะไรก็ได้ตั้งแต่ 0 ถึง 2m-1 เช่นถ้า m เท่ากับ 12 คิวบิต พอทำ Hadamard ก็จะทำให้ x สามารถเป็นทุกค่าตั้งแต่ 0 ถึง 4095 เป็นต้น
  • ที่จุด ψ1 ป้อนค่า x เข้า Uf หรือ oracle ของฟังค์ชัน f(x) (oracle นั้นว่าง่ายๆ คือสิ่งที่ทำให้สามารถนำฟังค์ชันธรรมดาเข้ามาสวมในวงจรควอนตัมได้ โดยมันจะมีขา x และ y สำหรับค่าก่อนและหลังผ่านฟังค์ชัน)
    การป้อนค่า superposition ของ x ทุกค่าที่เป็นไปได้เข้าไป หมายความว่าเราจะมีโอกาสได้ f(x) ทุกค่าที่เป็นไปได้ออกมา นี่คือ parallelism ในแบบควอนตัม มีความเป็นไปได้ที่จะเป็นทุกค่า แต่ไม่ได้หมายความว่ามันเป็นทุกค่า

  • กลเม็ดของอัลกอริทึมนี้อยู่ตรงจุด ψ3 คือทำการ “วัดผล” ของ f(x) การวัดผลจะทำให้ค่า f(x) หลุดจากสถานะควอนตัมกลายเป็นค่าใดค่าหนึ่ง สิ่งที่เกิดขึ้นตามมาก็คือ superposition ของสาย x ก็จะถูกปรับความน่าจะเป็นให้เหลือเพียงกลุ่มตัวเลขที่สามารถให้ค่า f(x) นั้นๆ ด้วย นี่คือปรากฏการณ์ entanglement ระหว่าง x กับ f(x)
    เช่น จากตัวอย่างหัวข้อที่แล้ว ถ้าสมมติเราวัด f(x) แล้วได้เลข 16 ออกมา หมายความว่า x ที่เป็นไปได้จะเหลือเพียง 2, 8, 14, 20, … เท่านั้น ไม่ใช่ทุกค่าตั้งแต่ 0 ถึง 2m-1

    state distributeกราฟกระจายความน่าจะเป็นของค่า x (ตัวอย่างไม่ได้แสดง x ครบทุกค่า)
    ก่อนการวัด f(x) (จุด ψ2) x อาจเป็นได้ทุกค่าเท่าที่คิวบิตอำนวย
    แต่หลังการวัด f(x) (จุด ψ3) x ถูกจำกัดความเป็นไปได้เหลือแค่บางค่า
  • เพียงแค่นี้ หากเราทำการวัดผล x ซึ่งให้ค่า f(x) เดียวกันได้ซักพัก เราก็จะรู้คาบของฟังค์ชันแล้ว เช่นถ้าเราวัด f(x) ได้ 16 แล้วเราวัด x ได้ 14, 2, 20 เราก็จะเริ่มรู้ว่าคาบของ f(x) คือ 6

เร็วขึ้นได้อีกด้วยควอนตัมฟูเรียร์ทรานสฟอร์ม
แต่การใช้ entanglement บังคับความน่าจะเป็นของ x แค่นั้นยังไม่ดีพอ ถือว่าเรายังต้องพึ่งดวงอยู่เยอะ เพราะถ้า r มีขนาดใหญ่ โอกาสที่จะสุ่มวัด f(x) ได้ค่าเดิมนั้นถือว่ายากมาก แล้วเรายังต้องพึ่งดวงในการสุ่มวัดค่า x ซึ่งอาจจะไม่สามารถบอกขนาดของ r เลยก็ได้ ดังนั้นจึงจำเป็นต้องเพิ่มส่วนประกอบอีกตัวหนึ่งเข้ามาช่วยคือวงจรควอนตัมฟูเรียร์ทรานสฟอร์ม (QFT, Quantum Fourier Transform)

ปกติแล้ว ฟูเรียร์ทรานสฟอร์ม คือสูตรที่ใช้ในการแปลงค่าฟังค์ชันจากมุมมองด้านเวลา (Time Domain) เป็นมุมมองด้านความถี่ (Frequency Domain) เช่นกราฟโค้งๆ ทางซ้าย แท้จริงแล้วเกิดจาก กราฟ Sine สามตัว/สามความถี่ทางขวามาบวกกัน จึงสามารถพล็อตกราฟในอีกแบบหนึ่งได้ดังภาพด้านล่าง ซึ่งเป็นกราฟแท่งที่บอกส่วนประกอบทางความถี่แทนที่จะบอกค่าในแกนเวลา

fourier explainTime Domain

ตัวอย่าง กราฟสีน้ำเงินทางซ้าย เกิดจากกราฟ Sine สามความถี่(ในเฟสต่างๆ)มารวมกัน คือความถี่ 0, 2 และ 4 รอบ (เฮิรตซ์)
ซึ่งสามารถนำมาพล็อตใหม่เป็นกราฟในมุมมองด้านความถี่ดังภาพด้านล่าง
freq domainFrequency Domain

ถึงแม้ว่าเราจะไม่ได้มีค่าฟังค์ชันเป็นเส้นต่อเนื่องแบบเส้นกราฟสีน้ำเงินด้านบน การทำฟูเรียร์นี้ก็ยังใช้งานได้ เช่นถ้าเราสุ่มค่าเป็นจังหวะบนเส้นกราฟสีน้ำเงิน เราจะพบจุดสีส้มเป็นกราฟแบบไม่ต่อเนื่อง (discrete) ซึ่งก็ถือว่าเกิดจากส่วนประกอบทางความถี่แบบเดียวกัน
สิ่งที่ชอร์ต้องการทำก็คือ แปลงสถานะควอนตัมของ x ซึ่งเป็นค่า discrete ที่มีคาบเป็น r อยู่นั้น ให้กลายเป็นค่าทางความถี่ โดยการทำควอนตัมฟูเรียร์ทรานสฟอร์ม ผลก็คือ หากค่า x มีขอบเขตสูงสุดที่ 2m กราฟความถี่ที่ได้จะมีระยะห่างระหว่างแท่งความถี่หลักเท่ากับ 2m/r
จากตัวอย่างเดิมของเรา สถานะ superposition 2, 8, 14, 20, … เมื่อทำฟูเรียร์(หรืออินเวอร์สฟูเรียร์ก็ได้)แล้วจะได้กราฟความถี่ดังรูป

qtfกราฟทางซ้ายคือการกระจายความน่าจะเป็นของ x ซึ่งมีคาบเท่ากับ r (จุด ψ3)
เมื่อผ่าน QFT แล้วการกระจายความน่าจะเป็นจะเปลี่ยนไปเป็นกราฟทางขวา (จุด ψ4)
สังเกตว่าตลอดโดเมนของ x ถูกแท่งสเปคตรัมแบ่งออกเป็น r ส่วน

กราฟความน่าจะเป็นที่แหลมโด่งแบบนี้จึงทำให้เมื่อวัดค่าของ x ที่จุด ψ4 แล้ว จะได้ผลลัพธ์ที่แตกต่างกันออกมาประมาณ r ค่าเท่านั้น อาจมีค่าอื่นหลุดรอดมาได้บ้างแต่ก็ส่วนน้อยมาก จริงๆ แล้วเราสุ่มวัดค่าซักสองสามครั้งก็คำนวณค่า r ได้แล้ว เช่น สมมติสุ่มได้ค่า 1365 กับ 2048 เราจะรู้ว่ามันคือที่ตำแหน่ง 2m/3 และ 2m/2 แค่นี้เราก็พอจะเดาได้แล้วว่า r น่าจะเป็น ค.ร.น. ระหว่าง 3 กับ 2 ก็คือ 6
และนี่ก็คือวิธีหาคาบของฟังค์ชัน f(x) โดยใช้เทคนิคการคำนวณทางควอนตัม ซึ่งหลังจากได้ค่าคาบ r แล้ว ก็ต้องเอาไปเข้าอัลกอริทึมแบบคลาสสิกเพื่อคำนวณตัวประกอบต่อไป

บทส่งท้าย
บทความนี้แสดงให้เห็นวิธีการโดยรวมของอัลกอริทึมของชอร์ จริงๆ ยังมีรายละเอียดอีกว่าตัว oracle function หรือ QFT นั้นจะสามารถสร้างขึ้นมาจริงๆ ด้วยควอนตัมเกตได้อย่างไร แต่ผมคงลงรายละเอียดตรงนั้นไม่ไหวแล้ว
ถึงแม้อัลกอริทึมนี้ในทางทฤษฎีจะดูเทพมากขนาดไหน แต่ในทางปฏิบัติจริงน่าจะยังมีปัญหาอยู่ ถ้าไม่นับเรื่องของฮาร์ดแวร์ที่จะใช้ในการสร้างคิวบิตหรือควอนตัมเกตแล้ว ผมว่าตัวอัลกอริทึมเองก็ต้องพึ่งดวงพอสมควร เพราะโอกาสที่จะสุ่มเลข a แล้วใช้แยกตัวประกอบได้นั้นก็ยากอยู่ แล้วอัลกอริทึมก็ยังต้องมีการคำนวณเลขยกกำลังขนาดมหาศาล ซึ่งต้อง implement เป็นพิเศษ จะไปใช้วิธีคำนวณธรรมดาอย่างที่มีให้เล่นในเว็บ Quantum Computing Playground จะเห็นว่ามันไม่ค่อย work เท่าไหร่

ก็จบไปอีกหนึ่งบทความ ที่จะให้คุณผู้อ่านได้เห็นว่าควอนตัมคอมพิวติ้งมีวิธีการอย่างไร ขอย้ำอีกทีว่าควอนตัมคอมพิวติ้งไม่ใช่การทำ parallel processing ถ้าแตกตัวแล้วหาคำตอบได้ คงทำงานเสร็จด้วย O(1) ไปแล้ว ความหมายของ quantum parallelism คือ superposition ซึ่งเล่นกับความน่าจะเป็นของแต่ละสถานะ และใช้หลากหลายเทคนิคดังที่ได้เห็น เช่น entanglement, QFT, amplitude amplification เพื่อตัดแต่งความน่าจะเป็นให้คำตอบของโจทย์นั้นโผล่ออกมา ควอนตัมอัลกอริทึมจึงสร้างออกมาด้วยความยากลำบาก ไม่ใช่ว่ามี superposition แล้วจะก็จะตะลุยหาคำตอบได้ทุกอย่าง

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: