Speaker: Dr. Pei Wu, Weizmann Institute of Science

Time: 14:00 p.m., July 17, 2024, GMT+8

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.

Source: Center on Frontiers of Computing Studies, PKU