Variations on classical and quantum extractors
Open accessThe DOI matches its Crossref record; 20 of the 21 references it cites were found in a registry or an index.
Abstract
Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Operational Meaning of Min- and Max-Entropy
Konig, R., Renner, R., & Schaffner, C. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2025545 · Cited by 659 · cited 2×
“We then discuss an extension of this when the input source is correlated to another quantum system R, and we require the output to be to uniform and independent of R provided that the quantum conditional min-entropy Hmin(NIR)p = -log F(N, R)p is large enough (F(N, R)p denotes the maximal achievable singlet fraction [1…”
BackgroundNisan, N., & Zuckerman, D. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0004 · Cited by 634 · cited 1×
“CLASSICAL M IN-ENTROPY EXTRACTORS The definition of a (strong) extractor is due to Nisan and Zuckerman [20].”
BackgroundEvenly distributed unitaries: On the structure of unitary designs
Gross, D., Audenaert, K., & Eisert, J. (2007) · Journal of Mathematical Physics · doi:10.1063/1.2716992 · Cited by 358 · cited 1×
“Many efficient constructions of unitary 2-designs are known [6], [14], and in ann-qubit space, such unitaries can typically be computed by circuits of size O(n(2)).”
BackgroundRandomizing Quantum States: Constructions and Applications
Hayden, P., Leung, D., Shor, P. W., & Winter, A. (2004) · Communications in Mathematical Physics · doi:10.1007/s00220-004-1087-6 · Cited by 345 · cited 1×
“studied quantum state randomization, which corresponds to weak (0, ε)-quantum extractors with the input size equal to the output size [16].”
BackgroundLeftover Hashing Against Quantum Side Information
Tomamichel, M., Schaffner, C., Smith, A., & Renner, R. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158473 · Cited by 303 · cited 2×
“(11) It was shown by König and Terhal that extractors with one bit output are quantum-proof [19, Theorem 1], and in general it is known by now that many extractor constructions are quantum-proof [17], [19], [23], [25], [27] or suffer at most from a decent parameter loss [7].”
BackgroundVadhan, S. P. (2012) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000010 · Cited by 226 · cited 1×
“(10) However, for applications we usually want explicit extract ors and starting with Trevisan’s breakthrough result [28] ther e a e now many constructions that almost achieve the bounds above (see [29] and references therein).”
BackgroundBounds for Dispersers, Extractors, and Depth-Two Superconcentrators
Radhakrishnan, J., & Ta-Shma, A. (2000) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480197329508 · Cited by 223 · cited 1×
“It turns out that a probabilistic construction using random functions achieves these bounds up to constants: there exists a (k, c) extractor with m = k -210g(1/c) -0(1), and d = log(n - k) + 210g(1/c) + 0(1) [22], [24].”
BackgroundTrevisan's Extractor in the Presence of Quantum Side Information
De, A., Portmann, C., Vidick, T., & Renner, R. (2012) · SIAM Journal on Computing · doi:10.1137/100813683 · Cited by 161 · cited 1×
“(11) It was shown by König and Terhal that extractors with one bit output are quantum-proof [19, Theorem 1], and in general it is known by now that many extractor constructions are quantum-proof [17], [19], [23], [25], [27] or suffer at most from a decent parameter loss [7].”
BackgroundExpanders, randomness, or time versus space
Sipser, M. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90035-9 · Cited by 127 · cited 1×
“(10) However, for applications we usually want explicit extractors and starting with Trevisan’s breakthrough result [28] there a e now many constructions that almost achieve the bounds above (see [29] and references therein).”
BackgroundGavinsky, D., Kempe, J., Kerenidis, I., Raz, R., & de Wolf, R. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250866 · Cited by 126 · cited 1×
“[13] gave an example of a valid (though contrived) extractor that completely fails in the presence of quantum s ide information.”
Background
Research works printed but not linked: 9
- dupuis, 2010, One-shot Decoupiing
- dupuis, 2012, A Decoupling Approach to Classical Data Transmission over Quantum Channels
- renner, 2005, Security of quantum key distribution
- szehr, 2011, Decoupling Theorems
- ta-shma, 2013, Extractors against classical and quantum adversaries, Tutorial QCrypt
- 10.4086/toc.2010.v006a003 · doi:10.4086/toc.2010.v006a003
- dupuis, 2009, The DecoupUng Approach to Quantum Information Theory
- berta, 2013, Identifying the information gain of a quantum measurement
- berta, 2013, An equality between entanglement and uncertainty
Cited by
Quantum Machine Learning for 6G Communication Networks: State-of-the-Art and Vision for the Future
Nawaz, S. J., Sharma, S. K., Wyne, S., Patwary, M. N., & Asaduzzaman, M. (2019) · IEEE Access · doi:10.1109/access.2019.2909490 · Cited by 658
“bits [158].”
Mitigating 5G security challenges for next-gen industry using quantum computing
Mangla, C., Rani, S., Qureshi, N. M. F., & Singh, A. D. (2022) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2022.07.009 · Cited by 69
“The objective is to change the source of biased and correlated bits into uniform bits Berta et al. (2014).”
Privacy Amplification and Decoupling Without Smoothing
Dupuis, F. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3301812 · Cited by 48
“One easy way to prove this condition for a given family of channels is to use the following lemma, which makes no reference to a purifying system E (see also [31]): Lemma 5: Let t R hA Ñ C : h P H u with distribution p be a family of channels that satisfies for any ρ A P L p A q .”
BackgroundQuantum-Proof Randomness Extractors via Operator Space Theory
Berta, M., Fawzi, O., & Scholz, V. B. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2627531 · Cited by 12
“, spectral extractors [4]), and hence that the l1-normalization condition on the input is crucial for studying to what extent extractors are quantum-proof.”
BackgroundSelf-citationHigher Dimension Quantum Entanglement Generators
Smith, K. N., & Thornton, M. A. (2019) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/3345501 · Cited by 5
“In addition to generalized quantum computing, systems and methods have been devised that are of a more specialized nature such as quantum cryptography and key distribution (QKD) [3, 22], sublinear complexity searching [13], true random number generators (TRNG) based upon quantum sources [4], quantum radar [16], quantu…”
Metadata
- Authors
- Berta, M., Fawzi, O., Scholz, V., & Szehr, O.
- Affiliations
- California Institute of Technology (US)
- ETH Zurich (CH)
- Technical University of Munich (DE)
- Venue
- 2014 IEEE International Symposium on Information Theory
- Publisher
- IEEE
- Published
- 2014-06
- Pages
- 1474-1478
- OpenAlex
- W1985937803
- Cited by
- 10
- References
- 21
- Citations by year
- 2023: 2 · 2022: 2 · 2019: 2 · 2018: 1 · 2016: 1 · 2014: 2
- FWCI
- 0.59
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- IEEE International Symposium on Information Theory (ISIT) (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Spiral (Imperial College London) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Keywords
- randomness extractors, quantum side information, decoupling, quantum correlations, seed length, min-entropy, second largest eigenvalue
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Variations on classical and quantum extractors. https://app.cochat.ai/papers/10.1109/isit.2014.6875078
- The paper
- Berta, M., Fawzi, O., Scholz, V., & Szehr, O. (2014). Variations on classical and quantum extractors. 2014 IEEE International Symposium on Information Theory. https://doi.org/10.1109/isit.2014.6875078
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.