อัลกอริทึมควอนตัมคืออะไร?

ควอนตัมอัลกอริธึมคือชุดคำสั่งคอมพิวเตอร์สำหรับการวิเคราะห์ปัญหาที่ไม่ได้ขึ้นอยู่กับการคำนวณทางคณิตศาสตร์หรือความน่าจะเป็นแบบดั้งเดิม แต่ใช้ลักษณะที่เป็นเอกลักษณ์ของควอนตัมความเป็นจริงซึ่งข้อมูลเพียงบิตเดียวสามารถเป็นตัวแทนของสองค่าได้ ศูนย์ในตรรกะไบนารี ในความหมายที่เข้มงวดที่สุดขั้นตอนวิธีควอนตัมต้องใช้คอมพิวเตอร์ควอนตัมเพื่อทำงานซึ่งไม่ได้อยู่ในรูปแบบใด ๆ ที่ผลิตในปี 2011 วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีอย่างไรก็ตามอย่างน้อยได้สร้าง analogues กับการคำนวณอัลกอริทึมควอนตัมที่แท้จริง ในฐานะอัลกอริทึม Deutsch, Shor และ Grover

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

อัลกอริทึมควอนตัมของชอร์และโกรเวอร์ทำหน้าที่คล้ายกัน แต่ได้รับการออกแบบมาสำหรับการประมวลผลคอมพิวเตอร์เฉพาะประเภท อัลกอริทึม Shor ใช้สำหรับการคำนวณทางคณิตศาสตร์และอัลกอริทึม Grover สำหรับการค้นหาข้อมูลที่มีความหมายในรายการคอมพิวเตอร์หรือฐานข้อมูลที่ไม่มีโครงสร้างที่ชัดเจน แม้ว่าอัลกอริทึมทั้งสองจะทำงานในระบบคอมพิวเตอร์แบบคลาสสิคที่ใช้การประมวลผลมาตรฐาน แต่การออกแบบของพวกเขานั้นได้รับการพิสูจน์แล้วว่าเหนือกว่าอัลกอริธึมพื้นฐานที่น่าจะเป็นแบบคลาสสิกสำหรับงานประเภทเดียวกัน อัลกอริธึมของชอร์นั้นเร็วกว่าแบบเอ็กซ์โปเนนเชียลและโกรเวอร์เร็วกว่ากำลังสองหรือเร็วกว่าวิธีการคำนวณมาตรฐานทั่วไป อัลกอริทึม Shor ควอนตัมนั้นตั้งชื่อตาม Peter Shor ศาสตราจารย์คณิตศาสตร์ชาวอเมริกันผู้พัฒนามันขึ้นในปี 1994 และอัลกอริทึม Quantum ของ Grover นั้นตั้งชื่อตาม Lov Grover นักวิทยาศาสตร์คอมพิวเตอร์ชาวอเมริกันอินเดียที่พัฒนามันในปี 1996

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