ขั้นคิดคำนวณแบบควอนตัม


เมื่อหนึ่งปีเต็มที่แล้วถูกชักชวนจากจิรวัฒน์ ตั้งปณิธานนท์ (Center for Quantum Technologies, สิงคโปร์) ให้ไปช่วยเขียนหนังสือให้ความรู้เกี่ยวกับคอมพิวเตอร์เชิงควอนตัม ด้วยความช่วยเหลือตรวจแก้จากบรรณาธิการและผู้ร่วมชะตากรรมเขียนคนอื่นๆทำให้สำเร็จออกมาเป็นหนังสือ(ฟรี) รูป รส กลิ่น เสียง สัมผัส ไอทีควอนตัม (๓): “คอมพิวเตอร์เชิงควอนตัม” จนได้ แต่ส่วนที่มีคณิตศาสตร์ที่เกินกว่าการนับเลขถูกตัดออกหมดก็เลยอยากจะลงต้นฉบับที่มีคณิตศาสตร์ไว้ ณ ที่นี้เพื่อความเข้าใจคอมพิวเตอร์เชิงควอนตัมที่แม่นยำและลึกซึ้งขึ้นครับ (ขอขอบคุณปัณฑิตา ผลิตผลการพิมพ์ (University of Calgary, แคนาดา) ที่อ่านและวิจารณ์ดราฟท์แรกอย่างละเอียดจนกลายมาเป็นต้นฉบับนี้ได้ แต่ข้อผิดพลาดใดๆหรือภาษาที่ไม่สละสลวยเป็นความรับผิดชอบของผมเอง)


อัลกอริธึมนั้นสำคัญไฉน

นี่คือหน้าตาของเมืองเคอนิกสแบร์ก (Königsberg) ในศตวรรษที่ 18 ที่แม่น้ำ Pregel ไหลผ่านตัดแยกตัวเมืองเป็นสี่ผืนดินที่เชื่อมกันด้วยสะพานเจ็ดสะพาน (ก่อนจะเหลือแค่ห้าจากการทิ้งระเบิดสมัยสงครามโลกครั้งที่สอง) ชาวเมืองเคอนิกสแบร์กมักจะใช้เวลาบ่ายวันอาทิตย์เดินชมเมืองอันสวยงามของพวกเขา จนมีคนนึกสนุกตั้งปัญหาขึ้นมาว่าเป็นไปได้ไหมที่จะเดินข้ามสะพานครบทั้งเจ็ดสะพานโดยไม่ข้ามสะพานใดสะพานหนึ่งมากกว่าหนึ่งครั้ง?

อีกปัญหาที่มีความคล้ายกันมากมาจากเกมที่วิลเลียม โรวัน แฮมิลตัน (William Rowan Hamilton) ชาวไอริชคิดขึ้นในปี 1857 ชื่อว่าเกมไอโคเซียน (Icosian) เป้าหมายของเกมคือการหาเส้นทางเดินบนขอบ (ที่เป็นเส้นหนึ่งมิติ ไม่ใช่หน้า) ของรูปเหลี่ยม 12 หน้า (dodecahedron) ที่ผ่านทุกมุมแต่ไม่ผ่านมุมใดมุมหนึ่งมากกว่าหนึ่งครั้ง

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

เลออนฮาร์ด ออยเลอร์ (Leonhard Euler) ชาวสวิตเซอร์แลนด์ที่ช่วงนั้นทำงานอยู่ที่เซนต์ ปีเตอร์สเบอร์ก สังเกตว่าปัญหาสะพานทั้งเจ็ดของเคอนิกสแบร์กจะมีคำตอบก็ต่อเมื่อไม่มีโหนดที่มีเส้นออกจากโหนดเป็นจำนวนคี่ หรือถ้ามีก็มีแค่สองโหนด เพราะการผ่านโหนดใดโหนดหนึ่งโดยไม่เดินซ้ำเส้นทางเดิมจะต้องมีทางเข้าทางหนึ่งกับทางออกทางหนึ่ง แต่โหนดเริ่มต้นไม่ต้องมีทางเข้าและโหนดสุดท้ายไม่ต้องมีทางออก คำตอบของออยเลอร์ลึกซึ้งที่ว่ามันไม่ใช่คำตอบของปัญหาสะพานทั้งเจ็ดของเคอนิกสแบร์กปัญหาเดียวแต่เป็นคำตอบของการเดินโดยไม่ซ้ำเส้นทางเดิมบนทุกๆเน็ตเวิร์ค และมันยังบอกขั้นตอนการหาคำตอบหรืออัลกอริธึม (algorithm) ที่มีประสิทธิภาพสำหรับทุกๆเน็ตเวิร์คโดยการนับจำนวนเส้นเชื่อมที่ออกจากโหนดแต่ละโหนดเท่านั้น

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

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

  • 1,000,000 เม็ดในช่องที่ 20
  • 1,000,000,000,000 เม็ดในช่องที่ 40
  • 18,000,000,000,000,000,000 เม็ดในช่องสุดท้ายซึ่งถ้าตีเป็นน้ำหนักก็จะได้ประมาณ 460,000,000 ตัน

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

บัตรเครดิต, เสียงดนตรี, และคอมพิวเตอร์ควอนตัม

ไอเดียของคอมพิวเตอร์ที่อาศัยพฤติกรรมเชิงควอนตัมของสสารในการคำนวณมีมาตั้งแต่ปี 1980 แล้วแต่ในตอนนั้นยังไม่ชัดเจนว่าคอมพิวเตอร์ควอนตัมจะแก้ปัญหายากๆได้เร็วกว่าคอมพิวเตอร์ธรรมดาขนาดไหน จุดเปลี่ยนที่ทำให้คนหันมาสนใจคอมพิวเตอร์ควอนตัมในวงกว้างมาจากวงการที่แทบจะไม่เกี่ยวข้องกับฟิสิกส์เลย: วงการรหัสลับ

การส่งข้อความลับจะต้องมีกุญแจเข้ารหัส (encrypt) และกุญแจถอดรหัส (decrypt) รหัสลับก่อนสงครามโลกครั้งที่สองมักใช้กุญแจเดียวกันทั้งในการเข้าและถอดรหัส จึงถูกเรียกว่ากุญแจแบบสมมาตร (symmetric key) รหัสแบบนี้สามารถให้ความปลอดภัยอย่างสมบูรณ์แบบได้ในทางทฤษฎีเช่น one-time pad ที่มีกุญแจเป็นข้อความสุ่มมั่วๆเอามาใช้แปลงข้อความจริง ถ้ารู้ข้อความสุ่มนั้นก็จะกู้ข้อความจริงกลับมาได้ แต่กุญแจต้องใช้แล้วทิ้ง ห้ามใช้ซ้ำกัน ตามชื่อว่า one-time (การที่โปรเจ็กต์ VENONA ของ NSA สหรัฐอเมริกาจับตัวสายลับโซเวียตในช่วงสงครามโลกครั้งที่สองได้ก็เชื่อกันว่ามาจากการใช้กุญแจซ้ำของโซเวียตที่มีเหตุจากการเร่งการผลิตกุญแจลับเพราะการบุกของเยอรมัน) ยิ่งข้อความลับยาวกุญแจก็ยิ่งต้องใหญ่ นอกจากนี้การที่ทั้งผู้ส่งและผู้รับจะต้องมีกุญแจเดียวกันก็แปลว่าจะต้องมีการส่งกุญแจกันไปมา ถ้าถูกดักตีหัวขโมยกุญแจก็เสร็จ

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

ถ้าดูนาฬิกาเป็นก็จะเข้าใจไอเดียของ RSA ได้ สังเกตว่าในการบวก-ลบเวลา เราจะไม่พูดว่า “10 ชั่วโมงหลัง 20 นาฬิกาคือ 30 นาฬิกา” แต่เราจะเริ่มนับส่วนที่เกิน 24 ใหม่ นอกจากบวก-ลบแล้วการคูณหรือการยกกำลังในระบบเลขคณิตแบบนี้ก็เป็นสิ่งที่ทำได้เพราะการคูณคือการบวกซ้ำๆกันและการยกกำลังคือการคูณซ้ำๆกัน ซึ่งคนส่วนใหญ่คงจะไม่เคยทำ แต่ถ้าลองทำดูจะพบสิ่งหนึ่งที่น่าสนใจคือการคูณเลขด้วยตัวมันเองซ้ำๆจะทำให้ย้อนกลับมายังเลขตั้งต้นได้ ตารางด้านล่างเป็นผลคูณ 2 ด้วยตัวมันเองถ้ามี 15 ชั่วโมงในหนึ่งวัน

กำลัง 1 2 3 4 5 6 7
ค่าของ 2 ยกกำลัง 2 4 8 1 2 4 8

การเข้ารหัสแบบ RSA แปลงข้อความให้เป็นจำนวนเต็มก่อน เรียกจำนวนนี้ว่า m (message) กุญแจสาธารณะคือจำนวนของ“ชั่วโมง” N และตัวเลข x ที่ทำให้ผู้เข้ารหัสสามารถคำนวณ m ยกกำลัง x ในเลขคณิตแบบนาฬิกาได้ เมื่อถึงมือผู้รับรหัส มีกุญแจลับ y ที่บอกว่าจะต้องยกกำลังต่ออีกเท่าไรจึงจะได้ข้อความ m กลับมา การจะรู้ y ได้จะต้องแยกตัวประกอบของ N ซึ่งเป็นส่วนหนึ่งของกุญแจสาธารณะที่ใครๆก็มี แต่ปัญหาก็คือทุกๆอัลกอริธึมการแยกตัวประกอบที่มีในปัจจุบันต้องใช้เวลาเป็นทวีคูณ การจะถอดรหัส RSA ที่ N เป็นเลขหลายร้อยหลักอาจจะต้องใช้เวลาเป็นล้านปี

แต่ถ้ามีคอมพิวเตอร์ควอนตัม การแยกตัวประกอบเลขหลายร้อยหลักจะใช้เวลาเพียงไม่กี่วินาที! 2 สิ่งที่ต่างก็คือคอมพิวเตอร์ควอนตัมมีอัลกอริธึมควอนตัมที่สามารถหาทางลัดในการแก้บางปัญหาได้ การทำงานของอัลกอริธึมควอนตัมแยกตัวประกอบค่อนข้างซับซ้อนแต่หัวใจของมันมาจากการปั่นรวมการยกกำลังในเลขคณิตนาฬิกากับการแปลงฟูเรียร์ (Fourier transform) ให้ผสมกลมกลืนเป็นรสเดียว การแปลงฟูเรียร์เป็นการแตกคลื่นเป็นผลรวมของหลายๆคลื่นที่มีความถี่เฉพาะตัว ไม่ต่างกับการแยกเสียงดนตรีเป็นโน๊ตความถี่ต่างๆ ทำให้สามารถขับหรือลดเสียงของเครื่องดนตรีแต่ละชนิดแยกกันได้ หน้าที่ของการแปลงฟูเรียร์ในอัลกอริธึมควอนตัมคือการหาคาบ (ส่วนกลับของความถี่) ของการยกกำลังในเลขคณิตนาฬิกา เมื่อรู้คาบ — จำนวนครั้งที่ต้องคูณเพื่อให้ได้ค่าเดิมกลับมา — ก็จะทำให้แยกตัวประกอบและรู้ y ได้ จึงทำลายรหัสลับ RSA ได้

บางปัญหาที่ยากสำหรับคอมพิวเตอร์ธรรมดาเป็นปัญหาที่ง่ายสำหรับคอมพิวเตอร์ควอนตัม นี่เป็นการค้นพบของ ปีเตอร์ ชอร์ (Peter Shor) ชาวอเมริกันในปี 1994 ที่สั่นสะเทือนวงการการถอดรหัสลับและฟิสิกส์ ปัจจุบันยังไม่มีคอมพิวเตอร์ควอนตัมขนาดใหญ่พอที่จะทำแบบนี้ได้ อินส์บรุค (Innsbruck) จับมือกับ MIT เพิ่งจะตีพิมพ์การแยกตัวประกอบ 15 ออกเป็น 3x5 ได้สำเร็จด้วยคอมพิวเตอร์ควอนตัมจิ๋ว 5 อะตอมเมื่อปีที่แล้ว 3 แต่ก็ไม่ต้องห่วงว่าถ้าทำสำเร็จโลกนี้จะไม่มีความลับอีกต่อไปเพราะนักวิทยาศาสตร์ได้เตรียมรหัสลับต้านทานอัลกอริธึมควอนตัมไว้เรียบร้อยแล้ว (post-quantum cryptography)

เรขาคณิตของอัลกอริธึมควอนตัม

ความเข้าใจผิดที่ได้ยินกันแพร่หลายมากที่สุดเกี่ยวกับคอมพิวเตอร์ควอนตัมคือคอมพิวเตอร์ควอนตัมเหมือนกับคอมพิวเตอร์ธรรมดาที่ประมวลผลแบบคู่ขนาน แก้ปัญหาโดยการเช็คคำตอบทุกคำตอบที่เป็นไปได้พร้อมๆกัน ซึ่งถ้าทำได้จริงก็จะมหัศจรรย์มาก ไม่ว่าปัญหาใดๆ อัลกอริธึมควอนตัมที่ลองทุกคำตอบก็จะแก้ได้ในหนึ่งขั้นตอนเท่านั้น แต่ความจริงไม่ง่ายแบบนั้น ซึ่งก็อาจจะเป็นเรื่องดีเพราะการเข้ารหัสลับที่ต้านทานอัลกอริธึมควอนตัมก็ต้องอาศัยปัญหาที่ยากสำหรับทั้งอัลกอริธึมธรรมดาและอัลกอริธึมควอนตัม ตัวอย่างที่ดีเยี่ยมในการแสดงให้เห็นการความแตกต่างของการทำงานของอัลกอริธึมธรรมดากับอัลกอริธึมควอนตัมจึงเป็นอัลกอริธึมควอนตัมในการเช็คคำตอบที่ลอฟ โกรเวอร์ (Lov Grover) ชาวอเมริกัน-อินเดีย คิดขึ้นมาในปี 1996 หลังจากชอร์ 2 ปี

การจะเข้าใจการทำงานของอัลกอริธึมนี้จะต้องรู้พื้นฐานของทฤษฎีควอนตัมเสียก่อนทฤษฎีควอนตัมรวมคณิตศาสตร์ของความน่าจะเป็นกับเรขาคณิต แต่เป็นเรขาคณิตที่มีแต่ทิศทาง ไม่มีระยะทาง (สำหรับคนที่รู้จักเวกเตอร์ จึงไม่ใช่เรขาคณิตของเวกเตอร์เสียทีเดียวเพราะเวกเตอร์มีทั้งขนาดและทิศทาง) ในเรขาคณิตแบบนี้ เหนือกับใต้ถือว่าเป็นทิศเดียวกันเพราะการเดินไปทางเหนือก็คือการเดินไปทางใต้ด้วยระยะทางติดลบ พูดอีกอย่างก็คือมุม 180 องศากลายเป็น 0 องศา (แทนที่ 360 องศาจะเป็น 0 องศา) แต่ความใกล้กันของสองทิศทางก็ยังวัดได้ด้วยมุมที่ไม่เกิน 90 องศา สิ่งที่สำคัญคือยังมีทิศทางที่ตั้งฉากกัน (ทำมุม 90 องศา) นิยามของมิติจึงเหมือนกับในเรขาคณิตปกติ คือจำนวนที่มากที่สุดของทิศทางที่ตั้งฉากกัน เหมือนที่ 3 มิติมีความกว้าง ความยาว และความสูง 4

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

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

องศา 0 30 45 60 90 120 135 150 180
โคไซน์กำลังสอง 1 3/4 1/2 1/4 0 1/4 1/2 3/4 1

สมมติว่าปัญหาหนึ่งมีคำตอบที่เป็นไปได้ 4 คำตอบ ปกติแล้วจะต้องเช็คคำตอบทีละคำตอบ จึงเป็นไปได้ว่าจะต้องเช็คถึง 4 ครั้งกว่าจะได้คำตอบที่ถูกต้อง สำหรับคอมพิวเตอร์ควอนตัม 4 คำตอบนี้แทนด้วย 4 ทิศทางที่ตั้งฉากกัน (จึงมี 4 มิติ) การเช็คคำตอบด้วยการวัดก็ไม่ช่วยอะไรเช่นกัน แต่คอมพิวเตอร์ควอนตัมสามารถเช็คคำตอบโดยปราศจากการวัดได้โดยการเก็บคำตอบ “ใช่” หรือ “ไม่ใช่” ไว้กับตัวมันเอง ซึ่งถ้าเราไม่ไปวัดก็จะไม่รู้ ดูเป็นความสามารถที่ไร้ประโยชน์สิ้นดี แต่ทริคของอัลกอริธึมควอนตัมคือการแปลงการเช็คคำตอบแบบหลังไปเป็นการพลิกสถานะควอนตัมที่ขนานกับทิศของคำตอบ ถ้าคำตอบอยู่ในทิศเหนือ-ใต้ (อย่าลืมว่าเป็นทิศเดียวกันในเรขาคณิตแบบควอนตัม) แล้วสถานะควอนตัมชี้ไปทางเหนือ การเช็คคำตอบก็จะพลิกมันมาทางทิศใต้ สถานะควอนตัมที่ชี้ไปทางใต้ก็จะถูกพลิกไปยังทิศเหนือ และปล่อยทิศทางที่ตั้งฉากกับคำตอบไว้คงเดิม ทริคนี้จึงไม่มีผลต่อความน่าจะเป็นของผลการวัดแต่อย่างใด แต่มันทำให้อัลกอริธึมควอนตัมหาหนึ่งในสี่คำตอบที่ถูกต้องเจอจากการเช็ค (พลิก) เพียงหนึ่งครั้งเท่านั้น! เริ่มต้นด้วยทิศที่มีโอกาสได้คำตอบทุกคำตอบเท่าๆกันหมดคือ 1/4 ทิศนี้ทำมุม 60 องศากับคำตอบ s (solution) เพราะว่าโคไซน์กำลังสองของ 60 องศาเท่ากับ 1/4

จากนั้นก็เช็คคำตอบเพื่อพลิกมัน

แล้วก็พลิกอีกครั้งผ่านทิศตั้งต้นก็จะได้คำตอบที่ถูกต้องด้วยความน่าจะเป็น 100%

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

ในมุมมองหนึ่ง สิ่งที่อัลกอริธึมควอนตัมทำจึงเป็นเพียงการขยับลูกศรไปมา ซึ่งพูดเหมือนง่ายแต่เป็นความท้าทายมาก ถ้าอยากรู้ว่าการควบคุมสถานะควอนตัมนั้นทำกันในแลบได้อย่างไรก็สามารถอ่านบทความที่เขียนและเรียบเรียงโดยนักศึกษาและนักวิทยาศาสตร์ไทยท่านอื่นๆ ได้ใน รูป รส กลิ่น เสียง สัมผัส ไอทีควอนตัม (๓): “คอมพิวเตอร์เชิงควอนตัม” ครับ

อ้างอิง

  • Cristopher Moore และ Stephen Mertens, “Quantum Computation” ใน The Nature of Computation, Cambridge University Press (2011).

  • Scott Aaronson, “Crypto” ใน Quantum Computing Since Democritus, Cambridge University Press (2013).


  1. มาจากตัวอักษรแรกของชื่อผู้ค้นพบ Ron Rivest, Adi Shamir, และ Leonard Adleman

  2. ถ้าสมมติว่าคอมพิวเตอร์ควอนตัมมีความเร็ว CPU พอๆกับของคอมพิวเตอร์ปัจจุบัน

  3. Thomas Monz et al., “Realization of a scalable Shor algorithmScience 351 1068 (2016).

  4. สำหรับผู้รู้ทฤษฎีควอนตัม ที่พูดไปไม่ใช่ความจริงทั้งหมดเพราะมุมนี้สามารถเป็นจำนวนเชิงซ้อนได้! แต่ทุกมุมในบทความนี้เป็นจำนวนจริง

  5. จริงๆคือ \(\pi/4\) คูณรากที่สองของจำนวนคำตอบที่เป็นไปได้



Archives by date, By category, By tag.