静5青年讲座 | Coherence in Property Testing

Coherence in Property Testing: Quantum-Classical Separations

报告人

Dr. Pei Wu

Weizmann Institute of Science

时  间

2024年7月17日 星期三 2:00pm

地  点

静园五院204

Host

姜少峰 助理教授

 Abstract

Property testing is a fundamental task both classically and quantumly. There is a wealth of results investigating property testing of classical probability distributions, where a tester is given samples of a distribution typically over a large domain, say  for large n. A central classical result is that to verify the support size of an unknown distribution requires  (Valiant&Valiant, STOC11) . In fact, to distinguish vastly different support sizes of flat distributions is hard: even given  samples, no tester can distinguish between flat distributions of support size  from  with probability better than  .

In the quantum setting, quantum states can be in a coherent superposition of many states of  , in particular, allowing a more global description of probability distributions. One can then ask how much coherence helps property testing. A natural way to encode a flat distribution is via subset states,   . We show that coherence alone is not enough to improve the testability of support size, (1) Even given  copies, no tester can distinguish between subset states of size  from  with probability better than  . In fact, we obtain a more general result showing that subset states are indistinguishable from Haar random states provided the support size is not too small nor too large. This also provides new constructions of pseudorandom (PRS) and pseudoentangled states. 

Given that standard property testing fails badly here, we enhance these models by allowing multiple provers. In particular, we show that  even interacting with multiple AM provers, classical property testing still fails, (2) Even given  samples from a classical distributions and interacting with  AM provers in  rounds, no classical tester can estimate the support size up to factors  with probability better than  . We obtain this classical lower bound via a curious reduction to fast mixing of high-dimensional expanders.

In contrast, we show that coherent subset state proofs suffice to improve testability exponentially, (3) With just polynomially many copies and subset state proofs, a tester can, with high probability, approximate the support size of a subset state of arbitrary size, or detect that the certificates are malicious. Our results show some of the power and limitations of coherence in property testing for a natural property and establish quantum-classical separations that are exponential in various parameters. 

Biography

Pei Wu obtained his PhD from UCLA. He is currently is a postdoc research fellow at the Weizmann Institute of Science. His research interest lies in theoretical computer science. He will start as an assistant professor at Pennsylvania State University, Fall 2024.

往 期 讲 座

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”查看海报