เหตุใดคอมพิวเตอร์ควอนตัมจึงยังไม่สามารถแยกตัวประกอบ 21 ได้

 (algassert.com)
1 คะแนน โดย GN⁺ 2025-09-01 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • หลังจากแยกตัวประกอบ 15 ด้วยคอมพิวเตอร์ควอนตัมได้ใน ปี 2001 ก็มีการอธิบายว่าทำไมจึงดูเหมือนไม่มีความคืบหน้าต่อจากนั้น
  • วงจรสำหรับแยกตัวประกอบ 21 ต้องใช้ เกตพัวพันมากกว่าการแยกตัวประกอบ 15 ถึง 100 เท่า
  • ความต่างนี้เกิดจากความซับซ้อนของ การคูณโมดูลาร์แบบมีเงื่อนไข และการปรับให้เหมาะแบบพิเศษที่ใช้ได้กับ 15 เท่านั้น
  • การแก้ไขข้อผิดพลาดควอนตัม และข้อจำกัดของฮาร์ดแวร์ก็ยิ่งเพิ่มกำแพงก่อนจะไปถึงการแยกตัวประกอบ 21
  • การรายงานการแยกตัวประกอบ 21 จนถึงตอนนี้ ส่วนใหญ่เป็นกรณีที่ใช้ลูกเล่นโดยไม่ได้ทำการคูณจริงในความหมายที่แท้จริง

เหตุใดคอมพิวเตอร์ควอนตัมจึงยังไม่สามารถแยกตัวประกอบ 21 ได้

เหตุผลที่ยังไม่เห็นการแยกตัวประกอบ 21 หลังจากการแยกตัวประกอบ 15

  • มีการทดลองแยกตัวประกอบ 15 ด้วยคอมพิวเตอร์ควอนตัมในปี 2001
  • แม้จะถึงปี 2025 แล้ว ก็ยังไม่มีกรณีความสำเร็จของ การแยกตัวประกอบ 21
  • จุดนี้ทำให้เกิดความเข้าใจแพร่หลายว่าคอมพิวเตอร์ควอนตัมไม่มีความก้าวหน้าเลย
  • แต่เมื่อเทียบวงจรสำหรับแยกตัวประกอบ 15 กับ 21 จริง ๆ แล้วมี เหตุผลที่น่าทึ่งกว่านั้นมาก

ความแตกต่างเชิงโครงสร้างระหว่างวงจรแยกตัวประกอบ 15 และ 21

  • วงจรแยกตัวประกอบ 15 สร้างได้ด้วย เกตควอนตัม 21 ตัว (เกตพัวพัน 21 ตัว) เท่านั้น
    • ประกอบด้วยเกตพัวพัน 6 ตัวสำหรับคิวบิตแต่ละตัว (เกต CNOT และ CPHASE) และ
    • เกต Toffoli 2 ตัว (แต่ละตัวแยกย่อยเป็นเกตพัวพัน 6 ตัว) รวมเป็นเกตพัวพัน 21 ตัว
  • วงจรแยกตัวประกอบ 21 ต้องใช้ CNOT 191 ตัว, Toffoli 369 ตัว, รวมเกตพัวพัน 2405 ตัว
    • เป็นภาระเกตพัวพันมากกว่าการแยกตัวประกอบ 15 ถึง 115 เท่า
    • ขนาดวงจรไม่ได้เพิ่มเพียง 25% หรือ 2 เท่า แต่ แพงขึ้นเกิน 100 เท่า
  • แม้คำนึงถึงระดับการปรับแต่งวงจรแล้ว ความต่างระดับ 500 เท่า ก็ยังดูเป็นไปได้จริง

เหตุใดจึงเกิดความต่างมหาศาลเช่นนี้

  • ใน วงจรแยกตัวประกอบควอนตัม (อัลกอริทึมของ Shor) ต้นทุนหลักคือ การคูณโมดูลาร์แบบมีเงื่อนไข
    • สำหรับจำนวน N ที่มี n บิต ต้องทำการคูณโมดูลาร์กับตัวสะสมแบบมีเงื่อนไขหลายครั้ง
    • ในกรณีของ 15 จากการคูณแบบมีเงื่อนไข 8 ครั้ง มีถึง 6 ครั้งที่จัดการได้เป็น การคูณด้วย 1 (ไม่ต้องทำอะไรเลย)
      • การคูณครั้งแรกทำได้แทบจะ ฟรี เพราะอินพุตเป็น 1
      • ครั้งที่สอง (อีกหนึ่งครั้งที่เหลือ) ก็จัดการได้อย่างประหยัดด้วย CSWAP สองครั้ง
      • ผลคือมีเพียง 2 ครั้งเท่านั้นที่ต้องจ่ายต้นทุนจริง
      • โครงสร้างนี้เป็นคุณสมบัติพิเศษที่มีเฉพาะกับ 15 เพราะมีการคูณที่ใกล้เคียง 1 อยู่หลายครั้ง จึงมีภาระต่ำมาก
  • แต่ในกรณีของ 21 การคูณทั้งหมดไม่ใช่ 1 และมีค่าหลากหลาย จึงทำให้ทุกการคูณมีต้นทุน
    • การคูณทั้ง 8 ครั้งล้วนมีต้นทุน ทำให้ไม่ได้เพิ่มเพียง 4~5 เท่า แต่เพิ่มเป็น 20~100 เท่า
    • การคูณด้วย 4 หรือ 16 ไม่สามารถทำเป็นโครงสร้างแบบ CSWAP (conditional swap) ได้
    • ความซับซ้อนของการคูณแตกต่างกันในแต่ละครั้ง และปรับให้เหมาะได้ยาก

ข้อจำกัดเชิงปฏิบัติของฮาร์ดแวร์และการแก้ไขข้อผิดพลาด

  • การแยกตัวประกอบ 15 ในอดีต (ปี 2001) ทำบน คอมพิวเตอร์ควอนตัมแบบ NMR ซึ่งมีข้อจำกัดด้านการขยายระบบมาก
  • ยิ่งไปกว่านั้น ความจำเป็นของ การแก้ไขข้อผิดพลาดควอนตัม ก็เพิ่มขึ้นด้วย
    • หากจำนวนเกตมากขึ้น 100 เท่า อัตราความผิดพลาดก็ต้องต่ำลง 100 เท่าด้วย
    • ในทางปฏิบัติอาจต้องเพิ่มจำนวน qubit ถึง 100 เท่า ทำให้ต้นทุนรวมอาจพุ่งขึ้นถึง 10,000 เท่า

ข้อถกเถียงเรื่องความพยายามแยกตัวประกอบและผลลัพธ์ที่คลาดเคลื่อน

  • ช่วงหลังมีบางงานวิจัยอ้างว่าประสบความสำเร็จในการแยกตัวประกอบ 21 ด้วยคอมพิวเตอร์ควอนตัม แต่
    • ในความเป็นจริง มักเป็นกรณีที่ละขั้นตอนการคูณของอัลกอริทึมออกไป หรือทำให้วงจรง่ายลงเพราะรู้ผลลัพธ์ล่วงหน้า
    • หากไม่ได้ทำการคูณจริง ก็ไม่อาจถือว่าเป็นการแยกตัวประกอบได้
    • เป็นผลลัพธ์ที่มองข้ามความต่างเชิงแก่นแท้ระหว่างการ "ค้นหารอบ" กับการแยกตัวประกอบ
  • บางงานถึงกับใช้ลูกเล่นอย่างชัดเจน และยังมีบทความเชิงเสียดสีออกมาวิจารณ์งานเหล่านั้นด้วย
    • มีบทความล้อเลียนหลายชิ้น เช่น การทดลองทำซ้ำสถิติแชมป์การแยกตัวประกอบ
    • ยังมี benchmark อย่าง Variational factoring โผล่ออกมาเรื่อย ๆ แม้ไม่มีหลักฐานว่าขยายสเกลได้จริง

อะไรคือดัชนีวัดความก้าวหน้าที่เหมาะสมของคอมพิวเตอร์ควอนตัม

  • ณ เวลานี้ การแยกตัวประกอบไม่ใช่ benchmark หลักของความก้าวหน้าคอมพิวเตอร์ควอนตัม
    • เมื่อเกิน 15 ไปแล้ว ต้นทุนจะพุ่งสูงจนยากต่อการตรวจสอบเชิงปฏิบัติ
  • สิ่งที่ควรจับตามากกว่าคือ การนำการแก้ไขข้อผิดพลาดควอนตัมมาใช้ (เช่น การปรับปรุง surface code) หรือ
    • การเปลี่ยนแปลงสถาปัตยกรรมฮาร์ดแวร์เพื่อแก้ปัญหาการขยายสเกล (เช่น การสับเปลี่ยนอะตอมเป็นกลางอย่างต่อเนื่อง)
    • ซึ่งเป็นจุดสังเกตที่สำคัญกว่าซึ่งแสดงถึงความก้าวหน้าที่แท้จริง

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-09-01
ความเห็นจาก Hacker News

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

  • สงสัยว่าหากจะแฟกเตอร์จำนวนที่มีความหมายในเชิงคริปโตจริง ๆ ต้องใช้ quantum gate กี่ตัว และอยากรู้ว่ามีเส้นทางที่เป็นรูปธรรมไหมสำหรับความเป็นไปได้ที่จะมีควอนตัมคอมพิวเตอร์ที่ใช้งานได้ภายในศตวรรษนี้

    • ยกตัวอย่างได้จากค่าประมาณใน Table 5 ของงานวิจัยที่ระบุว่าการแฟกเตอร์ RSA 2048 บิตต้องใช้ Toffoli gate ราว 7 พันล้านตัว (ลิงก์งานวิจัย) วิธีไปให้ถึงการคำนวณระดับหลายพันล้านครั้งก็คือ quantum error correction และงานวิจัยระบุว่า distance 25 surface code ก็เพียงพอแล้ว ในกรณีนี้จะขยายจาก logical qubit 1,400 ตัวไปเป็น noisy qubit จริงประมาณ 1 ล้านตัว แนะนำให้ดูบรรยายของ Samuel Jacques ที่ PQCrypto ด้วย (YouTube) ผมเป็นผู้เขียนบล็อกนี้และผู้ร่วมเขียนงานวิจัยที่เกี่ยวข้อง
    • มี 2 เหตุผลที่คำถามนี้ตอบยาก อย่างแรกคือไม่มีเส้นแบ่งชัดเจนว่าอะไรเรียกว่า "มีความหมายในเชิงคริปโต" อย่างที่สองคือโครงสร้างของ QC ที่จะทำการคำนวณนี้ได้จริงยังไม่เป็นที่ทราบชัด เหมือนกับการพยายามประเมินจำนวน traditional logic gate ที่ต้องใช้เพื่อสร้าง neural network ในปี 1985 ถึงอย่างนั้นก็ดูแน่ชัดว่าต้องใช้เกตมากกว่าหลายล้านตัว ประการที่สาม มี trade-off ระหว่างอัตราความผิดพลาดของ primitive qubit ที่ต่ำลงกับจำนวน gate ที่ต้องใช้เพื่อสร้าง virtual qubit ที่แก้ไขข้อผิดพลาดได้อย่างน่าเชื่อถือ ตอนนี้ยังไม่รู้ว่าอัตราความผิดพลาดของ primitive qubit จะลดลงได้ไกลแค่ไหน หากควอนตัมคอมพิวเตอร์พัฒนาแบบเดียวกับคอมพิวเตอร์ในช่วง 75 ปีที่ผ่านมา ก็คาดว่าแถว ๆ ปี 2100 คริปโตแบบเดิมจะไร้ประสิทธิภาพโดยสิ้นเชิง แต่จนกว่าจะมีนวัตกรรมครั้งใหญ่อย่าง transistor ก็ยังคาดการณ์ได้ยาก ความก้าวหน้าทางเทคโนโลยีมักดูเป็นไปไม่ได้เสมอ จนกว่าจะมีใครหาวิธีทำเป็นคนแรก (คำอธิบาย UNIVAC I)
    • ดูทวีตที่เกี่ยวข้องล่าสุดได้เช่นกัน (ลิงก์ทวีต) จากมุมมองคนทั่วไป เส้นทางนี้ดูถูกบดบังอยู่หลังนวัตกรรมด้านวัสดุศาสตร์ครั้งใหญ่หลายรอบ
    • สำหรับ RSA 4096 โดยคร่าว ๆ ต้องใช้ 10^7 qubit ที่อัตราความผิดพลาด 10^-4 ทุกวันนี้เพียงแค่ราว 100 qubit ก็สามารถทำการคำนวณเคมีควอนตัมที่มีประโยชน์ได้แล้ว และเมื่ออัลกอริทึม post-quantum ค่อย ๆ ถูกใช้อย่างแพร่หลาย แรงจูงใจในการสร้างควอนตัมคอมพิวเตอร์เพื่อถอดรหัสก็ลดลง ผมคิดว่า quantum computing จะพัฒนาได้เร็วกว่าในทิศทางที่ไม่เกี่ยวกับคริปโต
    • ตัวเลขล่าสุดคือที่อัตราความผิดพลาด 1e-4 ต้องใช้ qubit ประมาณ 1 ล้านตัว (ลิงก์งานวิจัย) จำนวน gate จะวัดต่างกันไปตามการปฏิบัติการจริงในระดับโค้ด และหากอิง "สัญญาณนาฬิกา" 1MHz (code cycle time) เวลาคำนวณทั้งหมดจะอยู่ที่ประมาณ 1 สัปดาห์ เมตริกที่ยากกว่าจำนวน qubit คือการทำเวลาให้ได้จริง อาศัยผลคล้ายเวทมนตร์ของ quantum error correction (ยิ่งอัตราความผิดพลาดต่ำ จำนวน qubit ก็ยิ่งลดลงมาก) ทำให้เมื่อคุณภาพ qubit ดีขึ้นอีกขั้น จำนวน qubit ที่ต้องใช้จะลดฮวบ ในทางกลับกัน หากต้องกระจายการคำนวณไปหลายระบบ สถานการณ์จะแย่ลงมาก

  • งานวิจัย 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' น่าสนใจดี (อ่านงานวิจัย)

  • สนใจขนาดวงจรและความเป็นไปได้ในการสร้างจริงของการแฟกเตอร์ตัวเลขที่มีความหมายในเชิงคริปโตอย่าง RSA1024

    • ค่าประเมินต้นทุนของ RSA1024 ไม่ได้มาจากการขยายแบบง่าย ๆ จากตัวเลขเล็ก ๆ (เช่น 4 บิต) แต่คำนวณจากการออกแบบวงจรที่ตรงกับขนาดจริง กล่าวคือได้สะท้อนปัญหาความไม่ต่อเนื่องที่กล่าวถึงในบทความนี้ไว้โดยนัยแล้ว ดังนั้นโพสต์นี้จึงไม่มีผลต่อค่าประเมินต้นทุนเดิม
    • (หมายเหตุ: การ optimize วงจรแฟกเตอร์ 21 น่าจะนำไปใช้ยากเมื่อแฟกเตอร์ตัวเลขขนาดใหญ่ ต้นทุนที่มากกว่าวงจรแฟกเตอร์ 15 ถึง 500 เท่าอาจสมจริงกว่า แน่นอนว่าแม้ overhead 100 เท่าก็เพียงพอจะอธิบายประเด็นได้แล้ว ขอขอบคุณ Noah Shutty เป็นพิเศษที่ช่วยทำการค้นหาด้วยคอมพิวเตอร์ราคาแพงเพื่อ optimize วงจรนี้)
    • ออกนอกประเด็นไปนิด แต่ก็สงสัยว่านักวิทยาการเข้ารหัสมั่นใจหรือไม่ว่าแม้ในศูนย์ข้อมูลขนาดมหึมาสมัยนี้ การแฟกเตอร์ RSA1024 ก็ยังแทบเป็นไปไม่ได้ในทางปฏิบัติ ณ ตอนนี้แม้อัลกอริทึมที่เร็วที่สุดก็ยังแฟกเตอร์ไม่ได้ในเวลาที่ใช้งานจริง แต่อยากรู้ว่ามีฉันทามติหรือไม่ว่าอัลกอริทึมนี้จะไม่ถูกพัฒนาแบบก้าวกระโดดในเร็ว ๆ นี้

  • สงสัยว่าสักวันหนึ่งควอนตัมคอมพิวเตอร์จะเล็งไปที่ post-quantum RSA ได้หรือไม่ (งานวิจัยที่เกี่ยวข้อง) มีมุมมองหนึ่งว่า RSA ปกติ (การสร้างคีย์ การเข้ารหัส การถอดรหัส) ได้เปรียบแบบไม่สมมาตรต่อ Shor algorithm ดังนั้นถ้าใช้คีย์ให้ใหญ่พอก็อาจเพียงพอ คล้ายกับผลแบบ Merkle puzzle โดยเพิ่มเงื่อนไขว่าผู้โจมตีต้องใช้ควอนตัมคอมพิวเตอร์เท่านั้น ผมเคยสร้าง RSA public key ระดับ gigabit มาก่อน (ไฟล์คีย์) ฟอร์แมตคือ: จำนวนไบต์ของคีย์แบบ little-endian 4 ไบต์ ตามด้วยคีย์ และค่า reciprocal ของคีย์ (mod ด้วย 256^bytes) public exponent คือ 3

    • Post-Quantum RSA เป็นมุกที่ djb ทำไว้เพื่อตอบคำถามแนว "ถ้าใช้คีย์ใหญ่ ๆ ก็ปลอดภัยไม่ใช่เหรอ" มันถูกออกแบบให้การเข้ารหัสหนึ่งครั้งใช้เวลา 100 ชั่วโมงกับคีย์ขนาด 1TB และเจาะไม่ได้แม้ใช้ควอนตัมคอมพิวเตอร์

  • เห็นพิมพ์ผิดเป็น "error corection" แล้วขำมาก

  • เข้าใจส่วนที่ว่า "ต้นทุนวงจรมากกว่า factor-15 อยู่ 500 เท่า" ได้ยาก ผู้เขียนยกกรณี 115 เท่ามาแล้ว เลยสงสัยว่าการ optimize เพิ่มเติมจะทำให้ผลลัพธ์แย่ลงได้อย่างไร

    • มันหมายความว่างาน optimize มหาศาลที่ทุ่มลงไปกับการสร้างวงจรแฟกเตอร์ตัวเลขขนาดเล็กนั้น ในทางปฏิบัติทำไม่ได้สำหรับตัวเลขขนาดใหญ่ กล่าวอีกอย่างคือโดยทั่วไปเมื่อขนาดตัวเลขที่ต้องแฟกเตอร์เพิ่มขึ้น ก็เป็นธรรมชาติที่จะต้องใช้จำนวน gate เพิ่มราว 500 เท่า (ไม่ใช่น้อยแบบ 115 เท่า)
    • ในสเกลใหญ่ ผลของการ optimize จะลดลง และคงไม่ได้ประโยชน์มากแบบวงจรสำหรับ N=21
    • การทำ implementation ขั้นต่ำมีความเปราะบางและรับประกันความน่าเชื่อถือได้ยาก การพัฒนาวงจรเชิงใช้งานจริงต้องอาศัยงานวิจัยจำนวนมากเพื่อให้ได้ qubit ที่เสถียร และยังมีการพูดถึงแนวคิดอย่าง "decoherence time" ด้วย ดังนั้นจำนวน qubit จึงหลีกเลี่ยงไม่ได้ที่จะพุ่งสูงมาก
    • 115 เท่าเป็นผลจากการ optimize อย่างหนักมาก (ซึ่งไม่สมจริง)

  • ประเด็นหลักของโพสต์นี้ทำให้สงสัยว่าความต้องการวงจรแบบ Big-O สำหรับการแฟกเตอร์ของ Schorr เป็นแบบซูเปอร์พหุนามหรือไม่

    • จากเนื้อหา gate cost มาจากการทำ modular multiplication จำนวน O(n) ครั้งเป็นหลัก และแต่ละครั้งสามารถทำได้ด้วย O(n^2) gate ดังนั้นโดยรวมแม้ในกรณีแย่ที่สุดก็ดูจะอยู่ราว ๆ ความซับซ้อนระดับกำลังสาม

  • เหตุผลที่นำเทคโนโลยีคริปโตแบบ PQ (post-quantum) มาใช้ ไม่ใช่เพราะมั่นใจเสมอไปว่า QC จะมาในเร็ว ๆ นี้ แต่เพราะยังไม่แน่ชัดว่า QC จะมาถึงเมื่อไรตามความเร็วของการพัฒนาเทคโนโลยี เป้าหมายของเทคโนโลยีคริปโตคือการหาวิธีที่แทบจะแตกไม่ได้แม้ในทางทฤษฎี และถ้ามีเส้นทางโจมตีได้ในทางทฤษฎี ก็ย่อมมีความเป็นไปได้ทางกายภาพด้วย จึงต้องเตรียมรับมือ ECC และ RSA มีเส้นทางเชิงทฤษฎีของการโจมตีที่เป็นที่รู้กันแล้ว จึงถือว่าโจมตีได้แม้ยังไม่มีอุปกรณ์จริง เพราะฉะนั้นการเตรียมตัวไว้ล่วงหน้าก่อนมี QC จึงเป็นมุมมองที่สมเหตุสมผลมาก ในทางกลับกัน SHA2, AES, ChaCha เป็นต้น ยังไม่เห็นเส้นทางโจมตีที่ใช้งานได้จริง จึงยังไม่มีแผนต้องเปลี่ยนทันที การเข้ารหัสไม่ใช่การใช้งานเพียงอย่างเดียว หรือแม้แต่การใช้งานที่สำคัญที่สุดของ QC ยังมีความหวังว่าจะเกิดนวัตกรรมที่เรายังไม่รู้ในด้านต่าง ๆ เช่น ระบบกายภาพ การพับตัวของโปรตีน หรือ machine learning

    • สงสัยว่าในด้านอย่างการพับตัวของโปรตีนจะยังพัฒนาได้อีกไหมในอนาคต (แม้หลัง AlphaFold แล้ว) (บทความอ้างอิง)

    • สำหรับ symmetric-key cryptography (AES, ChaCha, SHA-2) การโจมตีด้วยควอนตัมโดยหลักแล้วมีผลเหมือนลดความยาวคีย์ลงครึ่งหนึ่ง (คล้ายกรณี 3DES กับ 2DES) ในทางปฏิบัติจะบอกว่าลดครึ่งเดียวเป๊ะ ๆ ไม่ได้ เพราะประสิทธิภาพของควอนตัมคอมพิวเตอร์จริงอาจไม่เท่ากันหรือไม่อยู่ระดับเดียวกัน แต่เปลี่ยนไปใช้ AES-256 ก็พอแล้วจึงไม่มีปัญหา จุดที่ต้องโฟกัสจริง ๆ คือ Key Exchange เพราะ Key Exchange ใช้สำหรับตกลงคีย์ร่วมกันโดยที่ทั้งสองฝ่ายไม่ต้องเปิดเผย secret key ออกมาตรง ๆ ถ้ามี Quantum Computer ก็จะสามารถอ่านบทสนทนาเก่าที่ถูกบันทึกไว้ได้ ต่อให้เจาะอัลกอริทึมลายเซ็นได้ ก็ย้อนกลับไปเซ็นในอดีตไม่ได้ แต่ถ้า Key Exchange ถูกเจาะ บทสนทนาเก่าทั้งหมดจะถูกเปิดเผยทันที ดังนั้นการหาตัวแทนที่ปลอดภัยสำหรับ Key Exchange จึงเป็นเรื่องเร่งด่วน