บทนำ

ในบทเรียนแรกของคอร์สนี้ เราจะกำหนดกรอบอัลกอริทึมอย่างง่าย — ที่รู้จักในชื่อ query model — และสำรวจข้อได้เปรียบที่คอมพิวเตอร์ควอนตัมมอบให้ภายในกรอบนี้

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

หลังจากแนะนำ query model เองแล้ว เราจะพูดถึงอัลกอริทึมควอนตัมตัวแรกที่ค้นพบ ซึ่งคือ อัลกอริทึม Deutsch พร้อมกับส่วนขยายของอัลกอริทึม Deutsch ที่รู้จักในชื่อ อัลกอริทึม Deutsch-Jozsa อัลกอริทึมเหล่านี้แสดงให้เห็นข้อได้เปรียบเชิงปริมาณที่วัดได้ของควอนตัมเหนือคอมพิวเตอร์แบบคลาสสิก ภายในบริบทของ query model จากนั้นเราจะพูดถึงอัลกอริทึมควอนตัมที่รู้จักในชื่อ อัลกอริทึม Simon ซึ่งมอบข้อได้เปรียบที่แข็งแกร่งและน่าพอใจมากกว่าของควอนตัมเหนือการคำนวณแบบคลาสสิก ด้วยเหตุผลที่จะอธิบายเมื่อไปถึงหัวข้อนั้น

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

ในวิดีโอต่อไปนี้ John Watrous จะอธิบายเนื้อหาของบทเรียนนี้เรื่อง quantum query algorithms ให้คุณฟังทีละขั้น หรือจะเปิด วิดีโอ YouTube สำหรับบทเรียนนี้ในหน้าต่างแยกก็ได้ ดาวน์โหลดสไลด์ สำหรับบทเรียนนี้