ผลที่ตามมาของ $MIP^\ast=RE$ เกี่ยวกับ Quantum Algorithms
หลักฐาน (รอการตรวจสอบโดยเพื่อน) ของ $MIP^\ast=RE$ในการพิมพ์ล่วงหน้านี้ได้รับการยกย่องว่าเป็นความก้าวหน้าครั้งสำคัญ ความสำคัญของผลลัพธ์นี้ได้รับการกล่าวถึงโดย Henry Yuen (หนึ่งในผู้เขียน) ในบล็อกโพสต์นี้ Scott Aaronson ยังแสดงความหมายที่สำคัญบางประการในโพสต์บล็อกนี้
สำหรับเกมที่ไม่ใช่เกมท้องถิ่น ($G$) กำหนดขีดสุดของความน่าจะเป็นแห่งความสำเร็จสำหรับกลยุทธ์ผลิตภัณฑ์เทนเซอร์แบบไม่สัมพันธ์กันเป็น $\omega^\ast(G)$และขีดสุดของความน่าจะเป็นแห่งความสำเร็จสำหรับกลยุทธ์ตัวดำเนินการเดินทางเชิงสัมพันธ์ (QFT) เป็น $\omega^{co}(G)$. เนื่องจาก QM แบบไม่สัมพันธ์กันเป็นกรณีพิเศษของ QFT จึงเป็นที่ชัดเจนว่ากลยุทธ์ที่ใช้ตัวดำเนินการในการเดินทางที่ดีที่สุดนั้นดีพอ ๆ กับกลยุทธ์ที่ใช้ผลิตภัณฑ์เทนเซอร์ที่เหมาะสมที่สุด$\omega^\ast(G) \le \omega^{co}(G)$.
ความเข้าใจของฉันเกี่ยวกับโพสต์ของ Yuen นั้นเป็นผลมาจาก $MIP^\ast=RE$ คือเกมที่ไม่ใช่เกมในท้องถิ่นนั้นมีอยู่ $\omega^\ast(G) < \omega^{co}(G)$. เขากล่าวโดยเฉพาะ
จะต้องมีเกม $G$ดังนั้นซึ่งค่าควอนตัมจะแตกต่างจากค่าตัวดำเนินการการเดินทาง แต่นี่หมายความว่าปัญหาของ Tsirelson มีคำตอบเชิงลบดังนั้นการคาดเดาการฝังของ Connes จึงเป็นเท็จ
ฉันเข้าใจว่านี่หมายความว่ามีปัญหาระดับหนึ่งที่อัลกอริทึมที่ใช้เทคนิคจาก QFT (ตัวดำเนินการเดินทาง) มีโอกาสประสบความสำเร็จสูงกว่าอัลกอริทึมที่ใช้เทคนิคจาก QM ที่ไม่สัมพันธ์กัน (ผลิตภัณฑ์เทนเซอร์, พิธีการทางวงจรควอนตัม)
ส่วนแรกของคำถามของฉันคือสมมติว่าข้อพิสูจน์นี้หมายถึง :
- ทำ $MIP^\ast=RE$ หมายความว่ามีชุดของปัญหาที่สามารถแก้ไขได้อย่างมีประสิทธิภาพมากขึ้นโดยใช้รูปแบบทางคณิตศาสตร์ของ QFT (ตัวดำเนินการการเดินทาง) แทนที่จะเป็นพิธีการ QM แบบไม่สัมพันธ์กัน (วงจรควอนตัมธรรมดา)?
เว้นแต่ว่าฉันจะตีความผิดดูเหมือนว่าสิ่งนี้จะเกิดขึ้นโดยตรงจากคำพูดของ Yuen หากเป็นเช่นนั้นเป็นไปได้ไหมว่ามีเกมที่ไม่ใช่เกมในพื้นที่ซึ่งมีอยู่$\omega^\ast(G) < 0.5$ และ $\omega^{co}(G) > 0.5$เหรอ? โดยเฉพาะส่วนที่สองของคำถามของฉันคือ:
- ทำ $MIP^\ast=RE$ หมายความว่ามี (หรืออาจเป็น) ชุดของปัญหาที่สามารถแก้ไขได้โดยใช้ตัวดำเนินการเดินทางที่ไม่สามารถแก้ไขได้โดยใช้วงจรควอนตัมหรือความเป็นไปได้นี้ถูกเปิดเผยโดยความเป็นสากลของแบบจำลองวงจรควอนตัมหรือไม่?
แก้ไข: Henry Yuen ได้สร้างMIP * Wikiสำหรับผู้ที่สนใจในการทำความเข้าใจคลาสความซับซ้อนนี้ให้ดีขึ้นหรือไฟล์$MIP^\ast = RE$ ผลลัพธ์.
คำตอบ
ฉันไม่รู้ว่าผลลัพธ์ MIP * = RE หรือไม่และโดยเฉพาะอย่างยิ่งการอ้างว่ามีเกมที่ไม่ใช่คนในพื้นที่ $G$ ที่ไหน $\omega^*(G) \neq \omega^{co}(G)$มีผลกระทบของอัลกอริทึมสำหรับคอมพิวเตอร์ควอนตัม มีสองสิ่งที่จะพูดที่นี่
ผลลัพธ์ MIP * = RE เป็นปัญหาเกี่ยวกับปัญหาการคำนวณที่สามารถตรวจสอบได้โดยใช้เกมที่ไม่ใช่คนในพื้นที่ซึ่งตรงข้ามกับสิ่งที่สามารถแก้ไขได้โดยเกมที่ไม่ใช่คนในพื้นที่ (ฉันไม่แน่ใจว่าจะหมายความว่าอย่างไร!) ความแตกต่างระหว่างการตรวจสอบและการแก้ปัญหาเป็นเพราะสิ่งต่อไปนี้: ในเกมที่ไม่ใช่คนท้องถิ่นเราคิดว่าอลิซและบ็อบรู้คำตอบของปัญหาอย่างน่าอัศจรรย์ (ดังนั้นเราจึงถือว่าพวกเขาสามารถแก้ปัญหาการคำนวณได้ทันที) ความท้าทายของพวกเขาไม่ใช่การแก้ปัญหา แต่ต้องพิสูจน์ในการตรวจสอบเวลาแบบพหุนามแบบคลาสสิกพวกเขารู้คำตอบ การรู้คำตอบของบางสิ่งไม่ได้หมายความว่าคุณจะสามารถโน้มน้าวคำตอบของคนอื่นได้ Alice และ Bob สามารถใช้ความสัมพันธ์จากกรอบงานผลิตภัณฑ์เทนเซอร์หรือเฟรมเวิร์กตัวดำเนินการการเดินทางส่งผลต่อสิ่งที่พวกเขาสามารถพิสูจน์กับผู้ตรวจสอบได้หรือไม่ MIP * = RE แสดงให้เห็นว่าด้วยความสัมพันธ์ของผลิตภัณฑ์เทนเซอร์อลิซและบ็อบสามารถพิสูจน์ได้ว่าพวกเขารู้จัก Turing Machine ในที่สุดก็หยุดลง นี่เป็นสิ่งที่ไม่สามารถทำได้หากอลิซและบ็อบแบ่งปันความสัมพันธ์ของผู้ให้บริการการเดินทาง ดังนั้นโมเดลตัวดำเนินการในการเดินทางจึงแตกต่างจากรุ่นผลิตภัณฑ์เทนเซอร์
สิ่งที่สองที่ฉันอยากจะพูดถึงคือแยกกันเป็นคำถามที่น่าสนใจว่าเราสามารถกำหนดรูปแบบของการคำนวณควอนตัมที่พูดถึงตัวดำเนินการเดินทางและระบบมิติที่ไม่มีที่สิ้นสุดได้หรือไม่ ดูเหมือนว่า Cleve และคณะได้พยายามสร้างแบบจำลองสำหรับสิ่งนี้สิ่งที่พวกเขาเรียกว่า C * -circuit model:https://arxiv.org/pdf/1811.12575.pdf. คุณอาจพบว่าสิ่งนี้น่าสนใจ