CoChat

Variations on classical and quantum extractors

Open access
Berta, Mario, Fawzi, Omar, Scholz, Volkher, Szehr, Oleg · 2014 · 2014 IEEE International Symposium on Information Theory

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/isit.2014.6875078

Cites

20 of 20 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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…”
    Background
  • Randomness is Linear in Space

    Nisan, 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].”
    Background
  • Evenly 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)).”
    Background
  • Randomizing 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].”
    Background
  • Leftover 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].”
    Background
  • Pseudorandomness

    Vadhan, 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).”
    Background
  • Bounds 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].”
    Background
  • Trevisan'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].”
    Background
  • Expanders, 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).”
    Background
  • Exponential separations for one-way quantum communication complexity, with applications to cryptography

    Gavinsky, 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

Show all 20 references

Research works printed but not linked: 9

  1. dupuis, 2010, One-shot Decoupiing
  2. dupuis, 2012, A Decoupling Approach to Classical Data Transmission over Quantum Channels
  3. renner, 2005, Security of quantum key distribution
  4. szehr, 2011, Decoupling Theorems
  5. ta-shma, 2013, Extractors against classical and quantum adversaries, Tutorial QCrypt
  6. 10.4086/toc.2010.v006a003 · doi:10.4086/toc.2010.v006a003
  7. dupuis, 2009, The DecoupUng Approach to Quantum Information Theory
  8. berta, 2013, Identifying the information gain of a quantum measurement
  9. berta, 2013, An equality between entanglement and uncertainty

Cited by

See all 10

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
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.