Pith. sign in

REVIEW 5 minor 1 cited by

Classical messages plus a shared GHZ state solve a multi-sender Hidden Matching task with only log n bits each, while any high-success protocol without preshared entanglement needs polynomial communication from at least one sender—even if q

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

GHZ entanglement gives an exponential classical-communication advantage over unassisted quantum communication for multipartite Hidden Matching, and separates entangled from unentangled quantum side-information for a two-source extractor.

T0 review reviewed 2026-07-31 challenge →

load-bearing objection Clean multipartite exponential separation (GHZ classical vs unentangled quantum) plus a matching entangled/unentangled gap for two-source bounded storage; proofs look solid within the stated partial-matching model.

arxiv 2607.27957 v1 pith:S5W5DXFC submitted 2026-07-30 quant-ph

Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography

Ananya Chakraborty , Manik Banik , Ronald de Wolf This is my paper
classification quant-ph
keywords multipartite entanglementcommunication complexityHidden MatchingGHZ statequantum side-informationrandomness extractorsbounded-storage cryptographyhypercontractivity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper shows that multipartite entanglement can do something quantum communication alone cannot: it turns a multi-sender one-way communication task into a logarithmic classical protocol. Several senders each hold an n-bit string; a receiver holding a matching must report one edge together with the parity of the corresponding bits across all senders. A shared Greenberger–Horne–Zeilinger state lets each sender send only log n classical bits and still succeed. Without any preshared entanglement, even unrestricted quantum messages and shared randomness still force at least one sender to send on the order of square-root of n qubits. The same gap becomes a cryptographic statement: a natural two-source randomness extractor built from the task stays secure against two separate polynomial-size quantum memories, yet fails against two memories that share only a little entanglement. A sympathetic reader cares because the result separates multipartite entanglement from mere quantum channels and shows that entanglement can exponentially strengthen quantum side-information in bounded-storage cryptography.

Core claim

A shared GHZ state among m senders and one receiver solves multipartite Hidden Matching with O(log n) classical bits from each sender, while any bounded-error protocol without preshared entanglement requires Ω(√n) qubits from at least one sender—even when quantum communication and shared randomness are allowed. The induced two-source Hidden Matching extractor is therefore secure against two unentangled O(√(ε n))-qubit side-information states, yet insecure against two entangled log n-qubit states.

What carries the argument

Multipartite (Boolean) Hidden Matching together with the GHZ phase-encoding protocol: each sender applies local phase flips to a shared GHZ state, measures in the Fourier basis, and sends the outcome; the receiver recovers the global parity string and measures it against the matching. The matching lower bound and extractor security rest on a matrix-valued Fourier / hypercontractive argument (Theorem 4) that bounds how much two unentangled q-qubit memories can correlate with the extractor output.

Load-bearing premise

The polynomial lower bound and the extractor security proof only hold when the receiver’s seed is a partial (one-quarter) matching; the same Fourier bound fails for perfect matchings, because local parities would already determine the global output parity.

What would settle it

Exhibit a high-success one-way quantum protocol for two-sender Boolean Hidden Matching on 1/4-matchings in which every sender sends o(√n) qubits and no entanglement is shared, or show that two unentangled o(√n)-qubit memories already break the two-source extractor for constant error.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Classical communication assisted by multipartite entanglement can be exponentially stronger than quantum communication without entanglement on natural multi-party tasks.
  • Compromising the two-source Hidden Matching extractor needs polynomial-size unentangled quantum memory per source, but only logarithmic entangled memory.
  • Security proofs against unentangled quantum side-information need not extend to even modest shared entanglement between the adversaries’ memories.
  • For three or more senders, pairwise EPR entanglement among senders may still leave a polynomial communication lower bound, while genuine multipartite entanglement collapses it to logarithmic.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same GHZ encoding pattern should lift other bipartite relational problems that admit logarithmic quantum protocols into multipartite separations between entanglement-assisted classical and unassisted quantum communication.
  • Networked quantum cryptography that assumes only unentangled adversarial storage may be exponentially weaker once those adversaries are allowed a small shared entangled seed.
  • Interactive or noisy variants of the task could test whether the exponential gap survives beyond the strict one-way simultaneous-message model used here.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper introduces multipartite Hidden Matching (mHM_n) and its Boolean variant mBHM_n. A shared (m+1)-partite GHZ state yields a classical one-way protocol with O(log n) bits per sender (Theorem 1). Without preshared entanglement, any bounded-error protocol requires Ω(√n) qubits from at least one sender even with quantum messages and shared randomness (Theorem 2). The same Fourier analysis yields a two-source seeded extractor Ext_2(x1,x2,M)=M(x1⊕x2) that is secure against two unentangled O(√(ε n))-qubit side-information states but insecure against two entangled log n-qubit states (Theorem 3). The load-bearing analytic step is Theorem 4 (Appendix A), which expands product quantum side-information in the Fourier basis, splits degrees via the Ben-Aroya–Regev–de Wolf hypercontractive inequality and the matching-probability lemma of [35], and obtains EM[‖Δ_M‖_tvd]≤O(q²/n) for 1/4-matchings.

Significance. If correct, the work supplies the first exponential separation in which multipartite entanglement plus classical communication strictly outperforms unrestricted quantum communication without entanglement, and simultaneously the first exponential separation between entangled and unentangled quantum side-information for a multi-source extractor. Both results rest on explicit protocols and standard external inequalities (matrix hypercontractivity, Chor–Goldreich flat decompositions) rather than circular definitions. The constructions are proof-of-principle rather than parameter-optimal, yet they cleanly identify multipartite entanglement as a resource that cannot be simulated by quantum messages alone.

minor comments (5)
  1. [Theorem 1 and §II] The manuscript repeatedly writes “log 2 n” and “log2 n”; standardize to log_2 n throughout (Theorem 1, proof of Theorem 1, and the GHZ-state dimension statements).
  2. [Proof of Theorem 1] In the proof of Theorem 1 the Fourier-basis measurement outcomes are denoted both ⃗o and or; a single consistent notation would improve readability.
  3. [Appendix A] Appendix A, display after Eq. (A1): the factor 2^{2n}/(|A|·|B|) is carried through several lines; a short remark that it equals 2^{2c} when |A|,|B|≥2^{n-c} would make the subsequent bounds easier to track.
  4. [§IV Discussion] The open question posed in §IV about pairwise EPR pairs for m≥3 is interesting; a one-sentence pointer to why the present simulation argument fails for that model would help the reader.
  5. [References] Reference [15] appears with a 2026 date; confirm the bibliographic entry is final before publication.

Circularity Check

0 steps flagged

No circularity: exponential separation follows from an explicit GHZ protocol plus an independent Fourier/hypercontractive lower bound, not from definitions or fitted inputs.

full rationale

The upper bound (Theorem 1) is a constructive multipartite GHZ protocol that encodes local phase strings into a shared state and recovers a matching parity with O(log n) classical bits per sender; success is verified by direct calculation, not by defining the figure of merit to equal the bound. The matching lower bound (Theorem 2) and extractor security (Theorem 3(1)) are derived in Appendix A as corollaries of Theorem 4, which bounds the average trace distance of the two-source Hidden-Matching output from uniform when each source is accompanied by an unentangled q-qubit state. That proof expands the matrix-valued Fourier coefficients of the side-information maps, applies the external hypercontractive inequality of Ben-Aroya–Regev–de Wolf and the matching-probability estimate of Gavinsky et al., and splits small/large degree; none of these steps redefine the communication cost or extractor error in terms of the claimed Ω(√n) quantity. Bipartite HM lower bounds are imported only as black-box reductions (Lemma 1) or as the known one-source extractor template being generalized; they are not uniqueness theorems that force the multipartite claim by construction. The restriction to 1/4-matchings is stated explicitly and used consistently on both sides of the separation, so it is a modeling choice rather than a circular fit. Entangled insecurity (Theorem 3(2)) is an explicit attack, not a fitted prediction. No self-definitional loop, fitted-input-as-prediction, or load-bearing self-citation chain is present.

Axiom & Free-Parameter Ledger

3 free parameters · 5 axioms · 2 invented entities

Load-bearing content is standard quantum communication complexity plus cited analytic inequalities. No physical constants are fitted. Hand-chosen scales are the matching density 1/4 (inherited from [35]), error 1/3, and sufficiently small constants C,K in the O(√(ε n)) memory bound so that O(q²/n) is below the target TV distance. Invented objects are problem/extractor definitions, not new physical entities.

free parameters (3)
  • Matching density α=1/4 = 1/4
    Fixed to n/4 edges so the Boolean promise and Fourier lower bound match the bipartite template of [35]; authors note the perfect-matching case breaks Theorem 4.
  • Constant C (or K) in q=C√(ε n) = sufficiently small positive constant
    Chosen small enough that the O(q²/n) TV bound is ≤ε and the communication lower bound is Ω(√n); existence only, not numerically optimized.
  • Bounded-error threshold = 1/3
    Standard 1/3 error (and 1/4 error in the GHZ Boolean protocol via random completion of the matching).
axioms (5)
  • standard math Matrix-valued hypercontractive inequality for Fourier coefficients of functions to density matrices (Ben-Aroya–Regev–de Wolf).
    Invoked as Eq. (A2) to bound degree-k Fourier mass of q-qubit encodings in the proof of Theorem 4.
  • standard math Matching probability lemma: Pr_M[∃u MT u = v] ≤ (ek/(2n))^{k/2} for even-weight v (from Gavinsky et al. / [35]).
    Used to average ‖Δ_M‖ over random 1/4-matchings in Eq. (A1).
  • standard math Chor–Goldreich: every min-entropy ≥ n−c distribution is a convex combination of flat distributions on sets of size ≥ 2^{n−c}.
    Lifts Theorem 4 from flat sources A,B to general weak sources for extractor security.
  • domain assumption One-way SMP model: senders may not communicate with each other; receiver gets one message from each; no entanglement among senders in the Q∥,GSR lower bound.
    Defines the complexity classes C∥,GEnt and Q∥,GSR; sender-sender GHZ is treated separately and yields an efficient quantum protocol.
  • ad hoc to paper n is a power of 2 (for Fourier basis over Z_n and log n qubit registers).
    Stated for simplicity in the model section; standard and removable by padding.
invented entities (2)
  • Multipartite Hidden Matching mHM_n and Boolean mBHM_n no independent evidence
    purpose: Communication tasks that witness the multipartite entanglement vs quantum-communication separation.
    Relational/decision extensions of bipartite HM/BHM to m senders and one receiver; definitions, not physical postulates.
  • Two-source Hidden Matching extractor Ext2(x1,x2,M)=M(x1⊕x2) no independent evidence
    purpose: Seeded two-source extractor exhibiting entangled vs unentangled quantum side-information separation.
    Proof-of-principle construction parallel to the one-source HM extractor; parameters not claimed optimal.

reviewed 2026-07-31 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography." pith.science (2026). https://pith.science/paper/S5W5DXFC

@misc{pith2026260727957,
  author       = {Pith},
  title        = {Pith review of: Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S5W5DXFC}},
  note         = {Machine review of arXiv:2607.27957}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We establish an exponential communication advantage enabled by multipartite quantum entanglement. Building on the bipartite Hidden Matching problem, we introduce a communication task involving multiple spatially separated senders and a single receiver. We show that a shared Greenberger-Horne-Zeilinger state enables completion of this task using only logarithmically many bits of classical communication from each sender. In contrast, without preshared entanglement, any protocol achieving high success probability requires polynomial communication from at least one sender, even when \emph{quantum} communication is allowed. Thus, classical communication assisted by multipartite entanglement can be exponentially more powerful than quantum communication without preshared entanglement. As a cryptographic application, we construct a seeded two-source randomness extractor and establish an exponential separation between entangled and unentangled quantum side-information. Specifically, compromising the extractor with two unentangled quantum states storing information about the two sources, respectively, requires polynomial-size memory, whereas exponentially smaller quantum memory suffices in the presence of a small amount of shared entanglement.

Figures

Figures reproduced from arXiv: 2607.27957 by Ananya Chakraborty, Manik Banik, Ronald de Wolf.

Figure 1
Figure 1. Figure 1: Multipartite Hidden Matching task (mHMn). It involves m spatially separated senders (Alices), where the rth Alice receives a string x r ∈ {0, 1} n . Bob receives a perfect matching M ∈ Mn/2 on [n]. His goal is to output a triple [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Multipartite Hidden Matching extractor. Two in￾dependent weak random sources x 1 and x 2 , together with a uniformly random public seed M, are processed by the mul￾tipartite Hidden Matching extractor to produce an extracted key z = Ext2(x 1 , x 2 , M), that is statistically close to uniform. Adversaries with unentangled memory require polynomial-size quantum side-information to attack the protocol. In cont… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A lower bound on the classical simulation cost of star-network correlations

    quant-ph 2026-08 accept novelty 6.0

    A star-network exclusion game is won perfectly with quantum d-level messages, but classically needs a message of at least n^{d-1} symbols, so no fixed-size classical qubit description can simulate joint measurements o...

Reference graph

Works this paper leans on

57 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Schrödinger, Discussion of Probability Relations between Separated Systems, Math

    E. Schrödinger, Discussion of Probability Relations between Separated Systems, Math. Proc. Camb. Philos. Soc.31, 555–563 (1935)

    1935

  2. [2]

    Einstein, B

    A. Einstein, B. Podolsky, and N. Rosen, Can Quantum- Mechanical Description of Physical Reality Be Considered Complete?, Phys. Rev.47, 777 (1935)

    1935

  3. [3]

    Bohr, Can Quantum-Mechanical Description of Phys- ical Reality be Considered Complete?, Phys

    N. Bohr, Can Quantum-Mechanical Description of Phys- ical Reality be Considered Complete?, Phys. Rev.48, 696 (1935)

    1935

  4. [4]

    Schrödinger, Probability relations between separated systems, Math

    E. Schrödinger, Probability relations between separated systems, Math. Proc. Camb. Philos. Soc.32, 446–452 (1936)

    1936

  5. [5]

    J. S. Bell, On the Einstein Podolsky Rosen paradox, Physics Physique Fizika1, 195 (1964)

    1964

  6. [6]

    J. S. Bell, On the Problem of Hidden Variables in Quantum Mechanics, Rev. Mod. Phys.38, 447 (1966)

    1966

  7. [7]

    C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM J. Comput.26, 1510 (1997)

    1997

  8. [8]

    Steane, Quantum computing, Rep

    A. Steane, Quantum computing, Rep. Prog. Phys.61, 117–173 (1998)

    1998

  9. [9]

    C. H. Bennett and D. P. DiVincenzo, Quantum information and computation, Nature404, 247–255 (2000)

    2000

  10. [10]

    Gisin, G

    N. Gisin, G. Ribordy , W. Tittel, and H. Zbinden, Quantum cryptography , Rev. Mod. Phys.74, 145 (2002)

    2002

  11. [11]

    Gisin and R

    N. Gisin and R. Thew, Quantum communication, Nature Photonics1, 165–171 (2007)

    2007

  12. [12]

    Horodecki, P

    R. Horodecki, P. Horodecki, M. Horodecki, and K. Horo- decki, Quantum entanglement, Rev. Mod. Phys.81, 865 (2009)

    2009

  13. [13]

    Buhrman, R

    H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Nonloc- ality and communication complexity , Rev. Mod. Phys.82, 665 (2010)

    2010

  14. [14]

    A. M. Childs and W. van Dam, Quantum algorithms for algebraic problems, Rev. Mod. Phys.82, 1 (2010)

    2010

  15. [15]

    Huang, S

    H.-Y. Huang, S. Choi, J. R. McClean, and J. Preskill, Vast World of Quantum Advantage, Phys. Rev. X16, 030501 (2026)

    2026

  16. [16]

    M. M. Wilde,Quantum Information Theory, 2nd ed. (Cam- bridge University Press, Cambridge, 2017)

    2017

  17. [17]

    Svetlichny, Distinguishing three-body from two-body nonseparability by a Bell-type inequality , Phys

    G. Svetlichny, Distinguishing three-body from two-body nonseparability by a Bell-type inequality , Phys. Rev. D35, 3066 (1987)

    1987

  18. [18]

    Bouwmeester, J.-W

    D. Bouwmeester, J.-W. Pan, M. Daniell, H. Weinfurter, and A. Zeilinger, Observation of Three-Photon Greenberger- Horne-Zeilinger Entanglement, Phys. Rev. Lett.82, 1345 (1999)

    1999

  19. [19]

    W. Dür, G. Vidal, and J. I. Cirac, Three qubits can be en- tangled in two inequivalent ways, Phys. Rev. A62, 062314 (2000)

    2000

  20. [20]

    M. F. Riedel, P. Böhi, Y. Li, T. W. Hänsch, A. Sinatra, and P. Treutlein, Atom-chip-based generation of entanglement for quantum metrology , Nature464, 1170–1173 (2010)

    2010

  21. [21]

    Wang et al., 18-Qubit Entanglement with Six Photons’ Three Degrees of Freedom, Phys

    X.-L. Wang et al., 18-Qubit Entanglement with Six Photons’ Three Degrees of Freedom, Phys. Rev. Lett.120, 260502 (2018)

    2018

  22. [22]

    Figgatt, A

    C. Figgatt, A. Ostrander, N. M. Linke, K. A. Landsman, D. Zhu, D. Maslov, and C. Monroe, Parallel entangling op- erations on a universal ion-trap quantum computer, Nature 572, 368–372 (2019)

    2019

  23. [23]

    Omran et al., Generation and manipulation of Schrödinger cat states in Rydberg atom arrays, Science 365, 570–574 (2019)

    A. Omran et al., Generation and manipulation of Schrödinger cat states in Rydberg atom arrays, Science 365, 570–574 (2019)

    2019

  24. [24]

    G. J. Mooney , G. A. L. White, C. D. Hill, and L. C. L. Hollen- berg, Generation and verification of 27-qubit Greenberger- Horne-Zeilinger states in a superconducting quantum com- puter, J. Phys. Commun.5, 095004 (2021)

    2021

  25. [25]

    A. C.-C. Yao, Some complexity questions related to dis- tributive computing (preliminary report), inProc. 11th Annu. ACM Symp. Theory Comput., STOC ’79 (ACM Press,

  26. [26]

    Kushilevitz and N

    E. Kushilevitz and N. Nisan,Communication Complexity (Cambridge University Press, 1996)

    1996

  27. [27]

    A. C.-C. Yao, Quantum circuit complexity, inProc. 1993 IEEE 34th Annu. Found. Computer Sc., SFCS-93 (IEEE,

    1993

  28. [28]

    Cleve and H

    R. Cleve and H. Buhrman, Substituting quantum entangle- ment for communication, Phys. Rev. A56, 1201 (1997)

    1997

  29. [29]

    de Wolf, Quantum communication and complexity, Theor

    R. de Wolf, Quantum communication and complexity, Theor. Comput. Sci.287, 337–353 (2002). 7

    2002

  30. [30]

    Brassard, Quantum Communication Complexity , Found

    G. Brassard, Quantum Communication Complexity , Found. Phys.33, 1593–1616 (2003)

    2003

  31. [31]

    Buhrman, R

    H. Buhrman, R. Cleve, and A. Wigderson, Quantum vs. classical communication and computation, inProc. 13th Annu. ACM Symp. Theory Comput., STOC ’98 (ACM Press,

  32. [32]

    Raz, Exponential separation of quantum and classical communication complexity , inProc

    R. Raz, Exponential separation of quantum and classical communication complexity , inProc. 31st Annu. ACM Symp. Theory Comput., STOC99 (ACM, 1999) p. 358–367

    1999

  33. [33]

    Buhrman, R

    H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Quantum Fingerprinting, Phys. Rev. Lett.87, 167902 (2001)

    2001

  34. [34]

    Bar-Yossef, T

    Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis, Exponential separation of quantum and classical one-way communic- ation complexity, inProc. 36th Annu. ACM Symp. Theory Comput., STOC04 (ACM, 2004) p. 128–137

    2004

  35. [35]

    Gavinsky , J

    D. Gavinsky , J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf, Exponential separations for one-way quantum communica- tion complexity , with applications to cryptography , inProc. 39th Annu. ACM Symp. Theory Comput., STOC07 (ACM,

  36. [36]

    Kumar, I

    N. Kumar, I. Kerenidis, and E. Diamanti, Experimental demonstration of quantum advantage for one-way com- munication complexity surpassing best-known classical protocol, Nat. Commun.10, 4152 (2019)

    2019

  37. [37]

    D. M. Greenberger, M. A. Horne, A. Shimony, and A. Zeilinger, Bell’s theorem without inequalities, Am. J. Phys.58, 1131–1143 (1990)

    1990

  38. [38]

    N. D. Mermin, Quantum mysteries revisited, Am. J. Phys. 58, 731–734 (1990)

    1990

  39. [39]

    J.-W. Pan, D. Bouwmeester, M. Daniell, H. Weinfurter, and A. Zeilinger, Experimental test of quantum nonlocality in three-photon Greenberger–Horne–Zeilinger entanglement, Nature403, 515–519 (2000)

    2000

  40. [40]

    Gavinsky , J

    D. Gavinsky , J. Kempe, O. Regev, and R. de Wolf, Bounded- error quantum state identification and exponential separa- tions in communication complexity, inProc. 38th Annu. ACM Symp. Theory Comput., STOC06 (ACM, 2006) p. 594–603

    2006

  41. [41]

    Damgård, S

    I. Damgård, S. Fehr, L. Salvail, and C. Schaffner, Cryp- tography In the Bounded Quantum-Storage Model, in 46th Ann. IEEE Symp. Found. Comput. Sc.(IEEE, 2005) p. 449–458

    2005

  42. [42]

    Babai and P

    L. Babai and P. Kimmel, Randomized simultaneous mes- sages: solution of a problem of Yao in communication complexity , inProc. Computational Complexity 12th Annu. IEEE Conference, CCC-97 (IEEE Comput. Soc, 1997) p. 239–246

    1997

  43. [43]

    Buhrman, O

    H. Buhrman, O. Regev, G. Scarpa, and R. de Wolf, Near- Optimal and Explicit Bell Inequality Violations, Theory Comput.8, 623–645 (2012)

    2012

  44. [44]

    Shaltiel, Recent Developments in Explicit Constructions of Extractors, inCurrent Trends in Theoretical Computer Science: The Challenge of the New Century, Vol

    R. Shaltiel, Recent Developments in Explicit Constructions of Extractors, inCurrent Trends in Theoretical Computer Science: The Challenge of the New Century, Vol. 1, edited by G. P˘aun, G. Rozenberg, and A. Salomaa (World Scientific, Singapore, 2004) Chap. 13, pp. 189–228, Expanded ver- sion of the survey published inBulletin of the EATCS, 77:67– 95, 2002

    2004

  45. [45]

    C. H. Bennett, G. Brassard, and J.-M. Robert, Privacy Amplification by Public Discussion, SIAM J. Comput.17, 210–229 (1988)

    1988

  46. [46]

    Impagliazzo, L

    R. Impagliazzo, L. A. Levin, and M. Luby , Pseudo-random generation from one-way functions, inProc. 21st Annu. ACM Symp. Theory Comput., STOC ’89 (ACM Press, 1989) p. 12–24

    1989

  47. [47]

    König, U

    R. König, U. Maurer, and R. Renner, On the Power of Quantum Memory , IEEE Tran. Inf. Theory51, 2391–2401 (2005)

    2005

  48. [48]

    J. Kahn, G. Kalai, and N. Linial, The Influence of Variables on Boolean Functions, inProc. 29th Annu. Symp. Found. Computer Sc.(IEEE Computer Society , 1988) pp. 68–80

    1988

  49. [49]

    A. De, C. Portmann, T. Vidick, and R. Renner, Trevisan’s Extractor in the Presence of Quantum Side Information, SIAM J. Comput.41, 915 (2012)

    2012

  50. [50]

    Ben-Aroya and A

    A. Ben-Aroya and A. Ta-Shma, Better short-seed quantum- proof extractors, Theor. Comput. Sci.419, 17 (2012)

    2012

  51. [51]

    Barak, R

    B. Barak, R. Impagliazzo, and A. Wigderson, Extracting Randomness Using Few Independent Sources, SIAM J. Comput.36, 1095–1118 (2006)

    2006

  52. [52]

    Barak, A

    B. Barak, A. Rao, R. Shaltiel, and A. Wigderson, 2- source dispersers for no(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction, Ann. Math.176, 1483–1544 (2012)

    2012

  53. [53]

    Chattopadhyay and D

    E. Chattopadhyay and D. Zuckerman, Explicit two-source extractors and resilient functions, Ann. Math.189, 653 (2019)

    2019

  54. [54]

    Kasher and J

    R. Kasher and J. Kempe, Two-Source Extractors Se- cure Against Quantum Adversaries, Theory Comput.8, 461–486 (2012)

    2012

  55. [55]

    Ben-Aroya, O

    A. Ben-Aroya, O. Regev, and R. de Wolf, A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs, in2008 49th Annu. IEEE Symp. Found. Computer Sc.(IEEE, 2008) p. 477–486

    2008

  56. [56]

    hypercontractive

    B. Chor and O. Goldreich, Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity , SIAM J. Comput.17, 230–261 (1988). Appendix A: Proof of Theorem 2 & Theorem 3 We begin by proving a more general theorem and then will argue that Theorems 2 and 3 follow as special cases. Consider the function Z:{0, 1} n × {0, 1}n ×M n/4 → ...

    1988

  57. [2007]

    516–525, Available at: arXiv.quant-ph/0611209

    p. 516–525, Available at: arXiv.quant-ph/0611209

    Pith/arXiv arXiv

This paper was first reviewed by grok-4.5 on July 31, 2026.