Quantum soundness of the tensor code test
Organizer
Speaker
Zhengfeng Ji
Time
Friday, January 7, 2022 9:30 AM - 12:15 PM
Venue
JCY-1
Online
Tencent 953 7541 0477
(2024)
Abstract
Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. The quantum soundness of tensor code test is an essential component of the MIP* = RE theorem as it naturally generalize the low indivitual degree test. In this talk, we will discuss the proof ideas behind the quantum soundness analysis, its use in the MIP* = RE proof, and several interesting related open problems.
Speaker Intro
Zhengfeng Ji is currently a professor in the Department of Computer Science and Technology, Tsinghua University. His research studies quantum computing from a computer science perspective, recently focusing on the quantum algorithm and complexity theory, quantum cryptography, and quantum software.