Name
Abstract | ||
|---|---|---|
We give the first construction of a family of quantum-proof extractors that has optimal seedlength dependence O(log(n/ǫ)) on the input length n and error ǫ. Our extractors support anymin-entropy k = Ω(log n + log1+α(1/ǫ)) and extract m = (1 − α)k bits that are ǫ-close to uniform,for any desired constant α u003e 0. Previous constructions had a quadratically worse seed length orwere restricted to very large input min-entropy or very few output bits.Our result is based on a generic reduction showing that any strong classical condenser is automaticallyquantum-proof, with comparable parameters. The existence of such a reduction forextractors is a long-standing open question; here we give an affirmative answer for condensers.Once this reduction is established, to obtain our quantum-proof extractors one only needs to considerhigh entropy sources. We construct quantum-proof extractors with the desired parametersfor such sources by extending a classical approach to extractor construction, based on the use ofblock-sources and sampling, to the quantum setting.Our extractors can be used to obtain improved protocols for device-independent randomnessexpansion and for privacy amplification. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Quantum Physics | Quantum,Binary logarithm,Discrete mathematics,Quadratic growth,Extractor,Sampling (statistics),Entropy (information theory),Mathematics,Randomness |
DocType | Volume | Citations |
Journal | abs/1605.04194 | 0 |
PageRank | References | Authors |
0.34 | 30 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kai-Min Chung | 1 | 656 | 55.74 |
| Gil Cohen | 2 | 0 | 0.34 |
| Thomas Vidick | 3 | 377 | 31.69 |
| Xiaodi Wu | 4 | 0 | 1.69 |