กลับไปหน้าบทความ

อ่าน 1 นาที

เวลาพหุนามควอนตัมที่แม่นยำ

ทฤษฎีความซับซ้อนของควอนตัม/ต้นขั้ววิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี

ในทฤษฎีความซับซ้อนของการคำนวณเวลาพหุนามควอนตัมที่แม่นยำ ( EQPหรือบางครั้งเรียกว่าQP )

เวลาพหุนามควอนตัมที่แม่นยำ

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

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

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Exact_quantum_polynomial_time&oldid=1141428076 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ เวลาพหุนามควอนตัมที่แม่นยำ

ในทฤษฎีความซับซ้อนของการคำนวณเวลาพหุนามควอนตัมที่แม่นยำ ( EQPหรือบางครั้งเรียกว่าQP )