สามสิบปีต่อมา การเร่งความเร็วสำหรับควอนตัมแฟคตอริ่ง | นิตยสารควอนต้า

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

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

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

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

มาร์ติน เอเคโรซึ่งเป็นผู้เข้ารหัสลับของหน่วยงานรักษาความปลอดภัยการสื่อสารแห่งชาติของสวีเดน ตกลงกันว่ารายงานของ Regev นั้นน่าสนใจ แต่เตือนว่าการเอาชนะความทันสมัยในทางปฏิบัติจะต้องมีการเพิ่มประสิทธิภาพเพิ่มเติม “อัลกอริธึมดั้งเดิมของ Shor นั้นมีประสิทธิภาพอย่างน่าประหลาดใจอยู่แล้ว ดังนั้นจึงไม่ใช่เรื่องเล็กน้อยที่จะต้องปรับปรุงครั้งใหญ่” เขาเขียนในอีเมล

Regev พัฒนาอัลกอริทึมใหม่ของเขาโดยเพิ่มอัลกอริทึมของ Shor ด้วยเทคนิคจากสาขาการเข้ารหัสที่เกี่ยวข้องกับเรขาคณิตมิติสูง

“ผมคิดว่าอัลกอริทึมใดๆ ก็ตามที่ทำงานกับโครงร่างพื้นฐานนี้จะต้องสูญสิ้น” ชอร์ นักคณิตศาสตร์ประยุกต์ที่ปัจจุบันอยู่ที่สถาบันเทคโนโลยีแมสซาชูเซตส์กล่าว “แต่ฉันคิดผิด”

การหาปัจจัย

คอมพิวเตอร์ควอนตัมได้รับพลังมาจากวิธีการประมวลผลข้อมูลอันแปลกประหลาด คอมพิวเตอร์แบบคลาสสิกใช้บิต ซึ่งแต่ละสถานะจะต้องอยู่ในสถานะใดสถานะหนึ่งจากสองสถานะซึ่งมีป้ายกำกับ 0 และ 1 เสมอ ส่วนควอนตัมบิตหรือ “คิวบิต” ยังสามารถอยู่ในการรวมกันของสถานะ 0 และ 1 ของสถานะนั้นได้ ซึ่งเป็นปรากฏการณ์ที่เรียกว่าการซ้อนทับ นอกจากนี้ยังเป็นไปได้ที่จะเกลี้ยกล่อมหลาย qubits ให้อยู่ในสถานะการซ้อนทับแบบรวม: การซ้อนทับแบบ XNUMX qubit มีองค์ประกอบสี่ส่วนที่สามารถดำเนินการคำนวณที่แตกต่างกันได้พร้อม ๆ กัน และจำนวนของส่วนประกอบดังกล่าวจะเพิ่มขึ้นแบบทวีคูณเมื่อจำนวน qubit เพิ่มขึ้น ซึ่งช่วยให้คอมพิวเตอร์ควอนตัมสามารถคำนวณแบบเอ็กซ์โพเนนเชียลหลายรายการพร้อมกันได้อย่างมีประสิทธิภาพ

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

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

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

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

ในคอมพิวเตอร์แบบคลาสสิก นี่อาจเป็นวิธีที่ช้ามากในการแยกตัวประกอบจำนวนมาก — ช้ากว่าการพยายามทุกตัวที่เป็นไปได้ด้วยซ้ำ แต่วิธีการของชอร์ช่วยเร่งกระบวนการให้เร็วขึ้นแบบทวีคูณ ทำให้คาบการหาเวลาเป็นวิธีที่เหมาะสมที่สุดในการสร้างอัลกอริธึมแฟคตอริ่งควอนตัมที่รวดเร็ว

อัลกอริธึมของ Shor เป็นหนึ่งในผลลัพธ์สำคัญในช่วงแรกๆ ที่เปลี่ยนการคำนวณควอนตัมจากสาขาย่อยที่คลุมเครือของวิทยาการคอมพิวเตอร์ทางทฤษฎีมาเป็นผู้นำในทุกวันนี้ แต่การนำอัลกอริธึมไปปฏิบัติจริงนั้นเป็นงานที่น่ากังวล เนื่องจากคอมพิวเตอร์ควอนตัมมักเสี่ยงต่อข้อผิดพลาดอย่างฉาวโฉ่ นอกจากคิวบิตที่จำเป็นในการคำนวณแล้ว ยังต้องการให้ผู้อื่นอีกมากมายทำ งานพิเศษ เพื่อป้องกันไม่ให้พวกเขาล้มเหลว ก กระดาษที่ผ่านมา โดยEkeråและนักวิจัยของ Google เครก กิดนีย์ ประมาณการว่าการใช้อัลกอริทึมของ Shor เพื่อแยกตัวประกอบตัวเลขมาตรฐานความปลอดภัย 2,048 บิต (ยาวประมาณ 600 หลัก) จะต้องใช้คอมพิวเตอร์ควอนตัมที่มี 20 ล้านคิวบิต เครื่องจักรที่ล้ำสมัยในปัจจุบันมีเพียงไม่กี่ร้อยเครื่องเท่านั้น

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

หากเป็นเช่นนั้น Regev กล่าวว่า "เราควรรู้ให้เร็วที่สุดก่อนที่จะสายเกินไป"

หายไปในต้นไม้

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

“ถ้าเป็นป่าร้อยมิติ มันก็ซับซ้อนกว่าป่าสองมิติมาก” เกร็ก คูเปอร์เบิร์กเป็นนักคณิตศาสตร์จากมหาวิทยาลัยแคลิฟอร์เนีย เดวิส

Regev เริ่มศึกษาวิทยาการเข้ารหัสลับแบบ Lattice ในฐานะ Postdoc โดยเริ่มแรกในฐานะผู้โจมตี เขาต้องการทดสอบความเครียดกับแนวทางใหม่โดยค้นหาจุดอ่อนที่คอมพิวเตอร์ควอนตัมสามารถใช้ประโยชน์ได้ แต่เขาไม่สามารถก้าวหน้าไปได้ และในไม่ช้าเขาก็สงสัยว่ามีเหตุผลที่ลึกซึ้งกว่านี้หรือไม่ ในปี พ.ศ. 2005 เขาค้นพบวิธีที่จะจัดการกับการโจมตีที่ล้มเหลวเหล่านั้นให้เป็นก รูปแบบของการเข้ารหัสแบบ Lattice เหนือกว่ารุ่นอื่นๆ ทั้งหมด

“โอเดดเก่งมากกับตาข่าย” คูเปอร์เบิร์กกล่าว

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

“ถ้าคุณเป็นคนที่ทำตาข่ายเหมือนฉัน คุณจะคิดว่า 'โอเค มีตาข่ายเกิดขึ้นที่นี่'” Regev กล่าว “แต่ฉันไม่ชัดเจนว่าจะใช้สิ่งนั้นได้อย่างไร” เป็นเวลาหลายปีที่เขาเล่นกับแนวคิดอื่นๆ สำหรับอัลกอริธึมแฟคตอริ่งควอนตัมใหม่ๆ แต่เขาไม่เคยได้ที่ไหนเลย ฤดูหนาวที่แล้วเขากลับมาที่ปัญหาอีกครั้งและแก้ไขเพื่อปักหมุดความเชื่อมโยงที่น่าดึงดูดระหว่างการแยกตัวประกอบและการเข้ารหัสแบบ Lattice ครั้งนี้เขาพบกับความสำเร็จ

มิติพิเศษ

Regev รู้ว่าเขาจำเป็นต้องเริ่มต้นด้วยการสรุปฟังก์ชันคาบที่เป็นหัวใจสำคัญของอัลกอริทึมของ Shor จากมิติหนึ่งไปยังหลายมิติ ในอัลกอริทึมของ Shor ฟังก์ชันนั้นเกี่ยวข้องกับการคูณตัวเลขสุ่มซ้ำๆ ที่เรียกว่า gด้วยตัวเอง แต่คาบของฟังก์ชันนี้ — จำนวนครั้งที่คุณต้องคูณด้วย g ก่อนที่เอาต์พุตของฟังก์ชันจะเริ่มทำซ้ำ อาจมีขนาดใหญ่มากและนั่นหมายความว่าคอมพิวเตอร์ควอนตัมจะต้องคูณตัวเลขจำนวนมากในองค์ประกอบบางส่วนของการซ้อนทับที่ใช้คำนวณฟังก์ชันคาบ การคูณจำนวนมากเหล่านั้นเป็นส่วนที่มีค่าใช้จ่ายด้านการคำนวณมากที่สุดในอัลกอริทึมของ Shor

ฟังก์ชันสองมิติที่คล้ายคลึงกันจะใช้ตัวเลขคู่หนึ่งแทน g₁ และ g₂. มันเกี่ยวข้องกับการคูณ g₁ ด้วยตัวเองหลายๆ ครั้ง แล้วคูณด้วยซ้ำๆ g₂. คาบของฟังก์ชันนี้ก็เป็นแบบสองมิติเช่นกัน ซึ่งกำหนดโดยจำนวน g₁ การคูณและ g₂ การคูณที่รวมกันทำให้เอาต์พุตของฟังก์ชันเริ่มทำซ้ำ มีการผสมผสานที่แตกต่างกันมากมาย g₁ และ g₂ การคูณที่จะได้ผล

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

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

“นั่นสร้างความแตกต่างให้กับโลก” กล่าว วิโนดไวกุลธน, นักเข้ารหัสลับที่ MIT

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

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

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

เขียนใน ทราย

การปรับปรุงนั้นลึกซึ้ง จำนวนขั้นตอนเชิงตรรกะเบื้องต้นในส่วนควอนตัมของอัลกอริทึมของ Regev นั้นเป็นสัดส่วนกับ n^1.5 เมื่อแยกตัวประกอบ n- บิตจำนวนแทนที่จะเป็น n² เช่นเดียวกับในอัลกอริทึมของ Shor อัลกอริธึมจะทำซ้ำส่วนควอนตัมนั้นหลายสิบครั้งและรวมผลลัพธ์เพื่อสร้างโครงตาข่ายที่มีมิติสูง ซึ่งสามารถอนุมานระยะเวลาและแยกตัวประกอบของจำนวนได้ ดังนั้นอัลกอริทึมโดยรวมอาจไม่ทำงานเร็วขึ้น แต่การเร่งส่วนควอนตัมโดยการลดจำนวนขั้นตอนที่จำเป็นอาจทำให้นำไปปฏิบัติได้ง่ายขึ้น

แน่นอนว่า เวลาที่ใช้ในการรันอัลกอริธึมควอนตัมเป็นเพียงหนึ่งในข้อควรพิจารณาหลายประการ สิ่งสำคัญไม่แพ้กันคือจำนวนคิวบิตที่ต้องการ ซึ่งคล้ายคลึงกับหน่วยความจำที่จำเป็นในการจัดเก็บค่ากลางระหว่างการคำนวณแบบคลาสสิกทั่วไป จำนวนคิวบิตที่อัลกอริทึมของ Shor ต้องใช้ในการแยกตัวประกอบ n- จำนวนบิตเป็นสัดส่วนกับ nในขณะที่อัลกอริทึมของ Regev ในรูปแบบดั้งเดิมต้องใช้จำนวนคิวบิตตามสัดส่วน n^1.5 — ความแตกต่างอย่างมากสำหรับตัวเลข 2,048 บิต

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

“Qubit ของเราพยายามที่จะแตกสลายอยู่ตลอดเวลา และเรากำลังพยายามหยุดยั้งพวกมันไม่ให้แตกสลาย” Gidney กล่าว “มันเหมือนกับว่าคุณกำลังพยายามเขียนบนทรายแล้วลมก็พัดปลิวไป” นั่นหมายความว่า qubit พิเศษที่อัลกอริทึมของ Regev ต้องการอาจเป็นข้อเสียเปรียบที่สำคัญ

แต่รายงานของ Regev ไม่ใช่จุดสิ้นสุดของเรื่องราว เมื่อสองสัปดาห์ที่แล้ว Vaikuntanathan และนักศึกษาระดับบัณฑิตศึกษา Seyoon Ragavan ค้นพบวิธีลดการใช้หน่วยความจำของอัลกอริทึม ตัวแปรของพวกเขา ของอัลกอริทึมของ Regev เช่นเดียวกับอัลกอริทึมดั้งเดิมของ Shor ต้องใช้จำนวนคิวบิตตามสัดส่วน n มากกว่า n^1.5. Ekerå เขียนในอีเมลว่างานนี้ "ทำให้เราเข้าใกล้การนำไปปฏิบัติมากขึ้นซึ่งจะมีประสิทธิภาพมากขึ้นในทางปฏิบัติ"

บทเรียนที่กว้างขึ้นของอัลกอริธึมใหม่ของ Regev นอกเหนือจากผลกระทบจากแฟคตอริ่งก็คือ นักวิจัยด้านควอนตัมคอมพิวติ้งควรเปิดรับความประหลาดใจอยู่เสมอ แม้จะอยู่ในปัญหาที่ได้รับการศึกษามานานหลายทศวรรษก็ตาม

“อัลกอริธึมรูปแบบนี้ของฉันไม่ถูกค้นพบมาเป็นเวลา 30 ปีแล้ว และเกิดขึ้นอย่างไม่คาดคิด” Shor กล่าว “ยังคงมีอัลกอริธึมควอนตัมอื่นๆ อีกมากให้พบ”

หมายเหตุบรรณาธิการ: Oded Regev ได้รับเงินทุนจาก มูลนิธิไซมอนส์ซึ่งให้ทุนแก่นิตยสารอิสระด้านบรรณาธิการเล่มนี้ด้วย การตัดสินใจระดมทุนของมูลนิธิ Simons ไม่มีอิทธิพลต่อการรายงานข่าวของเรา รายละเอียดเพิ่มเติมคือ สามารถใช้ได้ที่นี่.

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