Quantum Interactive Proofs: Bridging Complexity Theory and Physics

报告人：季铮锋，清华大学计算机科学与技术系

主办单位：清华大学高等研究院

发布单位：高研院

报告地点：科学馆104

报告时间：2024-10-30 16:00

简介：This talk explores the connections between complexity theory, computation, and physics, with quantum interactive proofs as the focal point. We will begin with classical concepts in computational complexity, such as the Cook-Levin theorem on NP-completeness, Shamir's IP=PSPACE result, and the significance of the PCP theorem. From there, we will transition into the quantum realm, where notions like QMA, QIP, and MIP* extend the classical framework. These quantum complexity classes not only present new challenges for complexity theory but also offer insights into physical phenomena such as entanglement and nonlocality.

We will highlight how key topics in physics, including the EPR paradox, Bell inequalities, and the uncertainty principle, can be seamlessly integrated with foundational concepts in theoretical computer science, leading to understanding of the classes QIP and MIP*. The talk will conclude with open problems at the intersection of physics and interactive proofs, such as the Quantum PCP conjecture and various extensions of QMA that have significant physical implications.