ฟิสิกส์ควอนตัมนำไปสู่การถอดรหัสอัลกอริทึมทั่วไปอย่างไร

พื้นที่ การเพิ่มขึ้นของการคำนวณควอนตัม และมัน ผลกระทบ สำหรับมาตรฐานการเข้ารหัสที่เป็นที่รู้จักกันดีในปัจจุบัน แต่ทำไมคอมพิวเตอร์ควอนตัมจึงควรเชี่ยวชาญเป็นพิเศษในการทำลายการเข้ารหัส คำตอบคือการเล่นกลทางคณิตศาสตร์ที่เรียกว่า อัลกอริทึมของแคระแกร็น. คำถามที่ยังคงทิ้งไว้คือ อะไรที่ทำให้อัลกอริทึมนี้ทำให้คอมพิวเตอร์ควอนตัมสามารถถอดรหัสการเข้ารหัสได้ดีขึ้นมาก ใน วิดีโอนี้, ใช้ YouTube นาทีฟิสิกส์ อธิบายในรูปแบบการ์ตูนกระดานไวท์บอร์ดแบบดั้งเดิมของเขา

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

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

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

มหาอำนาจของการทับซ้อน

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

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

อย่างไรก็ตาม Peter Shor คือ ยังคงเจริญรุ่งเรืองและหากคุณสนใจที่จะเจาะลึกว่าเขาทำลายอินเทอร์เน็ตได้อย่างไร นี่เป็นอีกวิดีโอหนึ่งที่ตัวเขาเอง อธิบายว่าเขาคิดออกอย่างไร ผลงานชิ้นเอกของเขาในบาร์นี้