中文
Email
QCloud
Log in
BAQIS Quantum Science Forum 26: The Complexity of Bell Inequalities
2020/12/11
Time: 10:30-11:30
Speaker：Zhengfeng Ji，Professor，University of Technology Sydney
Host: Dong Liu，Department of Physics， Tsinghua University
Abstract:
In this talk, we study Bell inequalities from a computational complexity perspective and discuss how understanding the complexity of Bell inequalities help resolve Tsirelson's problem in physics and Connes' embedding problem in mathematics. We study Bell inequalities using a model called nonlocal games, which allows us to borrow many interesting techniques developed in computational complexity theory. Our main result is that approximating the value of a nonlocal game, or equivalently computing the maximum violation of Bell inequality, is as hard as the Halting problem of Turing machines. At the core of its proof is a recursive gap-preserving serving compression lemma for a family of nonlocal games. The compression lemma builds upon many recent ideas from the study of nonlocal games which we will briefly review in the talk. The talk bases on two recent papers on the topic MIP*=RE (arXiv:2001.04383) and Quantum soundness of the classical low individual degree test (arXiv:2009.12982).
Zhengfeng Ji is currently a professor in the Centre for Quantum Software and Information, School of Computer Science, University of Technology Sydney. He obtained his Ph.D. from Tsinghua University in 2007 under the supervision of Prof Mingsheng Ying. Before joining UTS, he was a postdoctoral research fellow at the Perimeter Institute for Theoretical Physics and the Institue for Quantum Computing, University of Waterloo. His recent research focuses on the quantum algorithm and complexity theory, quantum/post-quantum cryptography, and quantum computer science in general.