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.”
BackgroundHypercontractivity in Noncommutative LpSpaces
Olkiewicz, R., & Zegarliński, B. (1999) · Journal of Functional Analysis · doi:10.1006/jfan.1998.3342 · Cited by 92 · cited 1×
“For ρNR ∈ S(HNR) the quantum conditional min-entropy is defined as [18] Hmin(N |R)ρ = − log max ENR≥0 trN [ENR]=1R tr [ρNRENR] (4) and the classical-quantum version simplifies to Hmin(N |R)ρ = − log pguess(N |R)ρ, wherepguess(N |R)ρ is the maximal probability of decodingN from measurements on R.”
BackgroundConstruction of extractors using pseudo-random generators (extended abstract)
Trevisan, L. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301289 · Cited by 73 · 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).”
BackgroundSmall Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption
Ambainis, A., & Smith, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27821-4_23 · Cited by 71 · cited 1×
“See also the subsequent literature [1], [2], [8].”
BackgroundThe Bounded-Storage Model in the Presence of a Quantum Adversary
Konig, R. T., & Terhal, B. M. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.913245 · Cited by 65 · 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].”
BackgroundSampling of Min-Entropy Relative to Quantum Knowledge
Konig, R., & Renner, R. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2146730 · Cited by 64 · 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].”
BackgroundQuantum to Classical Randomness Extractors
Berta, M., Fawzi, O., & Wehner, S. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2291780 · Cited by 59 · cited 2×
“Decoupling quantum extractors where first introduced for mally in [6] and are extremely useful in quantum coding theory (see, e.”
BackgroundMethodSelf-citationOn Almost Randomizing Channels with a Short Kraus Decomposition
Aubrun, G. (2009) · Communications in Mathematical Physics · doi:10.1007/s00220-008-0695-y · Cited by 44 · cited 1×
“See also the subsequent literature [1], [2], [8].”
BackgroundApproximate Randomization of Quantum States With Fewer Bits of Key
Dickinson, P. A., & Nayak, A. (2006) · AIP conference proceedings · doi:10.1063/1.2400876 · Cited by 32 · cited 1×
“See also the subsequent literature [1], [2], [8].”
BackgroundEfficient Quantum Tensor Product Expanders and k-Designs
Harrow, A. W., & Low, R. A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03685-9_41 · Cited by 32 · cited 2×
“[15] A. Harrow and R. Low.”
BackgroundFawzi, O., Hayden, P. M., & Sen, P. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993738 · Cited by 17
Self-citation
Research works printed but not linked: 11
- [10] F. Dupuis, M. Berta, J. Wullschleger, and R. Renner. One-shot decoupling. 2010. -
- [11] F. Dupuis, O. Szehr, and M. Tomamichel. A decoupling approach to classical data transmission over quantum channels. 2012. -
- [23] R. Renner. Security of Quantum Key Distribution . PhD thesis, ETH Zurich, 2005. -
- [25] O. Szehr. Decoupling theorems. Master's thesis, ETH Zurich, 2011. -
- [26] A. Ta-Shma. Extractors against classical and quantum adversaries. Tutorial QCrypt , 2013. -
- 10.4086/toc.2010.v006a003 · doi:10.4086/toc.2010.v006a003
- [3] A. Ben-Aroya, O. Schwartz, and A. Ta-Shma. Quantum expanders: Motivation and construction. Theory of Computing , 6(3):47-79, 2010. -
- dupuis, 2009, The DecoupUng Approach to Quantum Information Theory
- [5] M. Berta, J. M. Renes, and M. M. Wilde. Identifying the information gain of a quantum measurement. 2013. -
- [4] M. Berta, P. Coles, and S. Wehner. An equality between entanglement and uncertainty. 2013. -
- [9] F. Dupuis. The Decoupling Approach to Quantum Information Theory . PhD thesis, Universit´ e de Montr´ eal, 2009. -
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
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.