บทนำ

อัลกอริทึมควอนตัมมอบข้อได้เปรียบที่พิสูจน์ได้เหนืออัลกอริทึมแบบคลาสสิกในแบบจำลอง query ของการคำนวณ แต่จะเป็นอย่างไรกับแบบจำลองการคำนวณที่เป็นมาตรฐานกว่า ซึ่ง inputs ของปัญหาถูกให้มาอย่างชัดเจนแทนที่จะอยู่ในรูปของ oracle หรือ black box? คำถามนี้ตอบยากกว่ามาก และเพื่อแก้ไขมัน เราต้องสร้างรากฐานที่มั่นคงก่อนเพื่อเป็นฐานการสืบสวน นี่คือวัตถุประสงค์หลักของบทเรียนนี้

เราจะเริ่มด้วยการพูดถึง ต้นทุนเชิงคำนวณ (computational cost) สำหรับทั้งการคำนวณแบบคลาสสิกและควอนตัม และวิธีวัดมัน นี่เป็นแนวคิดทั่วไปที่สามารถนำไปใช้กับปัญหาคำนวณหลากหลาย — แต่เพื่อให้เรียบง่าย เราจะตรวจสอบมันผ่านมุมมองของ ทฤษฎีจำนวนเชิงคำนวณ (computational number theory) ซึ่งแก้ไขงานคำนวณที่น่าจะคุ้นเคยกับผู้อ่านส่วนใหญ่ รวมถึงเลขคณิตพื้นฐาน การคำนวณ greatest common divisors และการแยกตัวประกอบจำนวนเต็ม แม้ทฤษฎีจำนวนเชิงคำนวณจะเป็นโดเมนการนำไปใช้ที่แคบ แต่ปัญหาเหล่านี้ก็ช่วยอธิบายประเด็นพื้นฐานได้ดี (และพวกมันยังมีความสัมพันธ์สูงกับบทเรียนถัดไปนี้ด้วย)

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

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

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

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