Coherence in Property Testing: Quantum-Classical Separations
- Dr. Pei Wu, Weizmann Institute of Science
- Time: 2024-07-17 14:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
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 {0,1}^n for large n. A central classical result is that to verify the support size of an unknown distribution requires O(2^n/n) (Valiant&Valiant, STOC11) . In fact, to distinguish vastly different support sizes of flat distributions is hard: even given $2^{n/16}$ samples, no tester can distinguish between flat distributions of support size 2^{n/8} from 2^{n/4} with probability better than 2^{-\Theta(n)}.
In the quantum setting, quantum states can be in a coherent superposition of many states of {0,1}^n, 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, \ket{\phi_S} = 1/\sqrt{|S|} \sum_{i \in S} \ket{i}$. We show that coherence alone is not enough to improve the testability of support size, (1) Even given 2^{n/16} copies, no tester can distinguish between subset states of size 2^{n/8} from 2^{n/4} with probability better than 2^{-\Theta(n)}. In fact, we obtain a more general result showing that subset states are indistinguisable 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.
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 theretical computer sicence. He will start as an assistant professor at Pennsylvania State University, Fall 2024.