การแยก BQP และ PH

Question

ฉันกำลังอ่านบทความ Quanta ที่นี่ซึ่งแสดงให้เห็นว่ามีปัญหาที่ทำให้เกิด "การแยก oracle ระหว่าง BQP และ PH" พูดง่ายๆก็คือมีปัญหาที่คอมพิวเตอร์ควอนตัมสามารถแก้ปัญหาได้โดยมีการโทรไปยัง oracle น้อยกว่าที่คอมพิวเตอร์แบบเดิมทำได้ (แม้ในขอบเขตที่ P = NP)

เหตุใดจึงเป็นผลลัพธ์ที่แข็งแกร่งกว่าอัลกอริทึม Deutsch-Jozsa ที่รู้จักกันดีในการตัดสินใจว่าฟังก์ชันคงที่หรือสมดุล ในกรณีนั้นคอมพิวเตอร์คลาสสิกก็ต้องทำ$O(n)$เรียกไปยัง oracle (ฟังก์ชัน) ในขณะที่คอมพิวเตอร์ควอนตัมสามารถทำได้ด้วยแบบสอบถามเดียว สิ่งนี้ไม่ได้พิสูจน์ว่าคอมพิวเตอร์ควอนตัมแตกต่างจากคอมพิวเตอร์คลาสสิกใด ๆ ที่เป็นไปได้แม้ว่า P = NP?

Answer 1

ปัญหา Deutsch-Josza ให้การแยก oracle ระหว่าง $\mathsf{EQP}$ (เวลาควอนตัม - พหุนามที่แน่นอน) และ $\mathsf{P}$แต่ไม่มีข้อสรุปเกี่ยวกับการเพิ่มการสุ่มเพื่อให้ได้อัลกอริทึมแบบคลาสสิกที่มีประสิทธิภาพ

ตัวอย่างเช่นปัญหา Deutsch-Josza เป็นเรื่องเล็กน้อยใน $\mathsf{BPP}$. เราสามารถโทรหา oracle ได้เป็นจำนวนน้อย หากคุณเคยเห็นผลลัพธ์ที่แตกต่างกันสองผลลัพธ์คุณจะรู้ว่าออราเคิลมีความสมดุล แต่ถ้าคุณเห็นผลลัพธ์เดียวกันเสมอคุณสามารถสรุปได้ว่าออราเคิลคงที่โดยมีความเป็นไปได้สูง

นอกจากนี้ยังมีการคาดเดาการลดทอนที่สมเหตุสมผลว่า $\mathsf{BPP}$ เท่ากับ $\mathsf{P}$. ดังนั้นปัญหา Deutsch-Josza จึงเข้ามา$\mathsf{P}$, โมดูโลเช่นการคาดเดาการลดขนาด

อย่างไรก็ตาม "ปัญหาสำหรับความสัมพันธ์" ที่พิจารณาในกระดาษ Raz-Tal และที่กล่าวถึงในบทความ Quanta ให้การแยกออรัลระหว่าง $\mathsf{BQP}$ และ $\mathsf{PH}$. ปัญหาความสัมพันธ์นี้ไม่น่าจะเกิดขึ้นใน$\mathsf{BPP}$.

ตัวอย่างเช่นคุณไม่สามารถเรียกใช้ oracle ด้วยคอมพิวเตอร์แบบคลาสสิกในเวลาพหุนามได้ด้วยความเป็นไปได้สูงจากนั้นใช้สิ่งที่คล้ายกับ Chernoff ที่ผูกไว้กับผลลัพธ์เพื่อพิจารณาว่าการแจกแจงที่กำหนดนั้นเป็นการแจกแจงแบบสม่ำเสมอหรือการแจกแจงแบบ forrelation