บทนำ

อัลกอริทึม Grover เป็นอัลกอริทึมควอนตัมสำหรับปัญหา unstructured search ที่มอบการปรับปรุง quadratic เหนืออัลกอริทึมแบบคลาสสิก หมายความว่าอัลกอริทึม Grover ต้องการการดำเนินการในอันดับ รากที่สอง ของจำนวนการดำเนินการที่ต้องใช้ในการแก้ unstructured search แบบคลาสสิก — ซึ่งเทียบเท่ากับการกล่าวว่าอัลกอริทึมแบบคลาสสิกสำหรับ unstructured search ต้องมีต้นทุนอย่างน้อยในอันดับ กำลังสอง ของต้นทุนของอัลกอริทึม Grover

อัลกอริทึม Grover พร้อมกับส่วนขยายและแนวทางพื้นฐาน ปรากฏว่านำไปใช้ได้กว้างขวาง นำไปสู่ข้อได้เปรียบ quadratic สำหรับงานคำนวณที่น่าสนใจหลากหลายอย่างที่อาจดูไม่เหมือนปัญหา unstructured search ในตอนแรก

แม้การนำไปใช้ในวงกว้างของเทคนิคการค้นหาของ Grover จะน่าสนใจ แต่ควรยอมรับตั้งแต่ต้นบทเรียนว่าข้อได้เปรียบ quadratic ที่มันมอบให้ดูเหมือนจะไม่นำไปสู่ข้อได้เปรียบเชิงปฏิบัติของควอนตัมเหนือการคำนวณแบบคลาสสิกในเร็ว ๆ นี้ ฮาร์ดแวร์การคำนวณแบบคลาสสิกก้าวหน้ากว่าฮาร์ดแวร์การคำนวณควอนตัมมากนัก — และข้อได้เปรียบ quadratic ของควอนตัมเหนือคลาสสิกที่อัลกอริทึม Grover มอบให้ย่อมถูกลบล้างด้วยความเร็วสัญญาณนาฬิกาอันน่าตะลึงของคอมพิวเตอร์คลาสสิกสมัยใหม่สำหรับปัญหา unstructured search ใด ๆ ที่พอจะรันได้จริงในอนาคตอันใกล้

อย่างไรก็ตาม เมื่อเทคโนโลยีการคำนวณควอนตัมพัฒนาขึ้น อัลกอริทึม Grover อาจมีศักยภาพ แน่นอน อัลกอริทึมแบบคลาสสิกที่สำคัญและมีผลกระทบมากที่สุดบางตัวที่เคยค้นพบ รวมถึง fast Fourier transform และการเรียงลำดับแบบเร็ว (เช่น quicksort และ merge sort) มอบข้อได้เปรียบน้อยกว่า quadratic เล็กน้อยเหนือแนวทางแบบ naive สำหรับปัญหาที่มันแก้ ความแตกต่างหลักที่นี่แน่นอนคือต้องการเทคโนโลยีใหม่ทั้งหมด (หมายถึงการคำนวณควอนตัม) เพื่อรันอัลกอริทึม Grover แม้เทคโนโลยีนี้ยังอยู่ในระยะเริ่มต้นมากเมื่อเทียบกับการคำนวณแบบคลาสสิก เราไม่ควรรีบด่วนประเมินศักยภาพของความก้าวหน้าทางเทคโนโลยีต่ำเกินไป ซึ่งอาจทำให้ข้อได้เปรียบ quadratic ของควอนตัมเหนือคลาสสิกนำไปสู่ประโยชน์เชิงปฏิบัติที่จับต้องได้ในสักวัน

วิดีโอบทเรียน

ในวิดีโอต่อไปนี้ John Watrous พาคุณผ่านเนื้อหาในบทเรียนนี้เกี่ยวกับอัลกอริทึม Grover หรือจะเปิด วิดีโอ YouTube สำหรับบทเรียนนี้ในหน้าต่างแยกก็ได้ ดาวน์โหลดสไลด์ สำหรับบทเรียนนี้