Introduction
Sampling estimates the average of a function from its values at a small number of points. Independent samples give sharp concentration bounds, but require fresh random bits for every evaluation. A randomness-efficient sampler seeks the same accuracy and confidence using samples generated from a much shorter random string. A challenge is to reduce the randomness without substantially increasing the number of samples.
From scalar to matrix sampling. For 0 < ε , δ ≤ 1 / 2 0 < \varepsilon, \delta\le1/2 0 < ε , δ ≤ 1/2 f : { 0 , 1 } m → [ 0 , 1 ] f : \{0,1\}^{m} \to[0,1] f : { 0 , 1 } m → [ 0 , 1 ] ε \varepsilon ε δ \delta δ O ( ε − 2 log ( 1 / δ ) ) O(\varepsilon^{-2}\log(1/\delta)) O ( ε − 2 log ( 1/ δ )) m m m [8 , 21 ] .1
Definition 1.1 (Averaging samplers [8 ] ). Let Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m \operatorname{Samp} : \{0,1\}^{r} \times[t] \to\{0,1\}^{m} Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m [ t ] = { 1 , … , t } [t] = \{1,\ldots,t\} [ t ] = { 1 , … , t } R R R { 0 , 1 } r \{0,1\}^{r} { 0 , 1 } r Z Z Z { 0 , 1 } m \{0,1\}^{m} { 0 , 1 } m Samp \operatorname{Samp} Samp ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) f : { 0 , 1 } m → [ 0 , 1 ] f : \{0,1\}^{m} \to[0,1] f : { 0 , 1 } m → [ 0 , 1 ]
Pr R [ ∣ 1 t ∑ i = 1 t f ( Samp ( R , i ) ) − E Z f ( Z ) ∣ > ε ] ≤ δ . \Pr_{R}\left[\left|\frac{1}{t}\sum_{i=1}^{t}f(\operatorname{Samp}(R,i))-\mathbb{E}_{Z}f(Z)\right|>\varepsilon\right]\leq\delta. R Pr [ t 1 i = 1 ∑ t f ( Samp ( R , i )) − E Z f ( Z ) > ε ] ≤ δ . The main parameters here are the randomness complexity r r r t t t [11 , 1 , 27 , 18 , 25 , 8 ] . Goldreich’s survey [21 ] gives an account of these methods and distinguishes averaging samplers from general samplers, such as median-of-averages constructions [7 ] , that may use a different estimator; see also Canetti, Even, and Goldreich [9 ] for lower bounds. Zuckerman [Zuc97] and Reingold, Vadhan, and Wigderson [42 ] used the connection to extractors to approach optimal randomness complexity. More recently, for δ < ε \delta< \varepsilon δ < ε m + O ( log ( 1 / δ ) ) m + O(\log(1/\delta)) m + O ( log ( 1/ δ )) O α ( ( ε − 2 log ( 1 / δ ) ) 1 + α ) O_{\alpha}((\varepsilon^{-2}\log(1/\delta))^{1+\alpha}) O α (( ε − 2 log ( 1/ δ ) ) 1 + α ) α > 0 \alpha> 0 α > 0
There is a matrix analogue of the sampling task for estimating scalar functions. Specifically the matrix analogue asks us to estimate the mean of a function f : { 0 , 1 } m → C D × D f : \{0,1\}^{m} \to\mathbb{C}^{D\times D} f : { 0 , 1 } m → C D × D ∥ f ( z ) ∥ ≤ 1 \|f(z)\| \leq1 ∥ f ( z ) ∥ ≤ 1 ∥ A ∥ = max ∥ v ∥ 2 = 1 ∥ A v ∥ 2 \|A\| = \max_{\|v\|_{2}=1}\|Av\|_{2} ∥ A ∥ = max ∥ v ∥ 2 = 1 ∥ A v ∥ 2 O ( ε − 2 log ( 2 D / δ ) ) O(\varepsilon^{-2}\log(2D/\delta)) O ( ε − 2 log ( 2 D / δ )) [2 , 49 ] . Such bounds are basic tools in spectral graph theory, numerical linear algebra, and quantum information. Their derandomization motivates the study of matrix (averaging) samplers [WX08, GLSS18, XZ25].
Definition 1.2 (Matrix (Averaging) samplers [XZ25]). Let Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m \operatorname{Samp} : \{0,1\}^{r} \times[t] \to\{0,1\}^{m} Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m R R R { 0 , 1 } r \{0,1\}^{r} { 0 , 1 } r Z Z Z { 0 , 1 } m \{0,1\}^{m} { 0 , 1 } m
The map Samp \operatorname{Samp} Samp D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) f : { 0 , 1 } m → C D × D f : \{0,1\}^{m} \to\mathbb{C}^{D\times D} f : { 0 , 1 } m → C D × D ∥ f ( z ) ∥ ≤ 1 \|f(z)\| \leq1 ∥ f ( z ) ∥ ≤ 1 z z z
Pr R [ ∥ 1 t ∑ i = 1 t f ( Samp ( R , i ) ) − E Z f ( Z ) ∥ > ε ] ≤ δ . \Pr_{R}\left[\left\|\frac{1}{t}\sum_{i=1}^{t}f(\operatorname{Samp}(R,i))-\mathbb{E}_{Z}f(Z)\right\|>\varepsilon\right]\leq\delta. R Pr [ t 1 i = 1 ∑ t f ( Samp ( R , i )) − E Z f ( Z ) > ε ] ≤ δ . The map Samp \operatorname{Samp} Samp D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) f 1 , … , f t : { 0 , 1 } m → C D × D f_{1},\ldots,f_{t} : \{0,1\}^{m} \to\mathbb{C}^{D\times D} f 1 , … , f t : { 0 , 1 } m → C D × D ∥ f i ( z ) ∥ ≤ 1 \|f_i(z)\| \leq1 ∥ f i ( z ) ∥ ≤ 1 i , z i,z i , z
Pr R [ ∥ 1 t ∑ i = 1 t ( f i ( Samp ( R , i ) ) − E Z f i ( Z ) ) ∥ > ε ] ≤ δ . \Pr_{R}\left[\left\|\frac{1}{t}\sum_{i=1}^{t}\left(f_i(\operatorname{Samp}(R,i))-\mathbb{E}_{Z}f_i(Z)\right)\right\|>\varepsilon\right]\leq\delta. R Pr [ t 1 i = 1 ∑ t ( f i ( Samp ( R , i )) − E Z f i ( Z ) ) > ε ] ≤ δ . We sometimes use the term ordinary matrix sampler to distinguish a matrix sampler from a strong matrix sampler.
We call Samp \operatorname{Samp} Samp R ↦ ( Samp ( R , 1 ) , … , Samp ( R , t ) ) R \mapsto(\operatorname{Samp}(R,1),\ldots,\operatorname{Samp}(R,t)) R ↦ ( Samp ( R , 1 ) , … , Samp ( R , t )) r + m t r+mt r + m t
The matrix problem has developed along two complementary lines. Garg, Lee, Song, and Srivastava [20 ] established a matrix Chernoff bound for expander walks, resolving the conjecture arising from the work of Wigderson and Xiao [WX08]. Subsequent extensions cover finite Markov chains [36 ] and time-dependent matrix observables on general state spaces [33 ] . Song’s recent work [45 ] sharpens the Hoeffding and Bernstein constants, including in the expander-walk setting. For a stationary walk on a fixed-degree expander with constant absolute spectral gap, these bounds give sample count t = O ( ε − 2 log ( 2 D / δ ) ) t = O(\varepsilon^{-2}\log(2D/\delta)) t = O ( ε − 2 log ( 2 D / δ )) m + Θ ( t ) m+\Theta(t) m + Θ ( t ) ε − 2 \varepsilon^{-2} ε − 2
The other line seeks to reduce this overhead directly. Applying a scalar sampler entry by entry gives good randomness complexity, but introduces a polynomial dependence on D D D δ ≤ ε \delta\le\varepsilon δ ≤ ε O ( log ( D / δ ) ) O(\log(D/\delta)) O ( log ( D / δ )) D D D
Randomness extraction and quantum side information. As shown by Zuckerman [Zuc97], there is a correspondence between averaging samplers and randomness extractors. A seeded extractor converts a weak random source into nearly uniform bits with the help of a short independent random seed. We measure the randomness of a source X X X H ∞ ( X ) = − log 2 max x Pr [ X = x ] H_\infty(X)=-\log_2\max_x\Pr[X=x] H ∞ ( X ) = − log 2 max x Pr [ X = x ] U j U_j U j j j j Δ ( P , Q ) = 1 2 ∑ z ∣ P ( z ) − Q ( z ) ∣ \Delta(P,Q)=\frac{1}{2}\sum_z\lvert P(z)-Q(z)\rvert Δ ( P , Q ) = 2 1 ∑ z ∣ P ( z ) − Q ( z )∣
Definition 1.3 (Seeded extractors [35 ] ). A function Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m ( k , η ) (k,\eta) ( k , η ) X X X { 0 , 1 } n \{0,1\}^n { 0 , 1 } n H ∞ ( X ) ≥ k H_\infty(X)\ge k H ∞ ( X ) ≥ k Y ∼ U d Y\sim U_d Y ∼ U d
Δ ( Ext ( X , Y ) , U m ) ≤ η . \Delta(\operatorname{Ext}(X,Y),U_m)\le\eta. Δ ( Ext ( X , Y ) , U m ) ≤ η . The map Ext \operatorname{Ext} Ext strong if, for every X X X H ∞ ( X ) ≥ k H_\infty(X)\ge k H ∞ ( X ) ≥ k
Δ ( ( Ext ( X , Y ) , Y ) , U m + d ) ≤ η . \Delta((\operatorname{Ext}(X,Y),Y),U_{m+d})\le\eta. Δ (( Ext ( X , Y ) , Y ) , U m + d ) ≤ η . The classical goal is to maximize the output while minimizing the seed length, subject to the lower bounds of Radhakrishnan and Ta-Shma [41 ] . Universal hashing achieves entropy loss O ( log ( 1 / η ) ) O(\log(1/\eta)) O ( log ( 1/ η )) [5 , 26 , 27 ] . Trevisan [48 ] connected extraction to pseudorandom generators and error-correcting codes. Lu, Reingold, Vadhan, and Wigderson [32 ] obtained parameters optimal up to constant factors for constant error. Guruswami, Umans, and Vadhan [22 ] gave a condenser-based construction with seed length O ( log ( n / η ) ) O(\log(n/\eta)) O ( log ( n / η )) ( 1 − γ ) k (1-\gamma)k ( 1 − γ ) k γ > 0 \gamma>0 γ > 0
Further developments include hashing and block-source methods [10 , 35 WZ99, 46 , 24 ] , error reduction and improving output length [38 , 39 ] , mergers and condensers [34 , 40 TSUZ07, TSU06, 17 DKS13, TSU12, 31 ] , and extraction in low-depth circuit classes [GWW15, CJL18, CWV24]. The surveys of Shaltiel [43 ] and Vadhan [Vad12] provide background on classical extractors and their connections to pseudorandomness.
For sampling, the relevant connection is particularly simple to describe: for a fixed source string x x x y y y Ext ( x , y ) \operatorname{Ext}(x,y) Ext ( x , y ) d d d 2 d 2^d 2 d
What type of randomness extractor corresponds to a matrix sampler?
On the other hand, quantum side information changes the extraction problem. In randomness extraction, the extracted string must be nearly uniform even to an adversary who has partial information about the source [5 , 4 ] . If this information is stored in a quantum system, security must hold against measurements of that system [37 , 51 ] . Although the extractor itself is a classical function, classical security does not in general imply quantum security [19 ] .
We describe the source X X X E E E ρ X E \rho_{XE} ρ X E H ∞ ( X ) H_\infty(X) H ∞ ( X ) dim E \dim E dim E X X X E E E H min ( X ∣ E ) = − log 2 p g u e s s ( X ∣ E ) H_{\min}(X \mid E)=-\log_2 p_{\mathrm{guess}}(X \mid E) H m i n ( X ∣ E ) = − log 2 p guess ( X ∣ E ) p g u e s s ( X ∣ E ) p_{\mathrm{guess}}(X \mid E) p guess ( X ∣ E ) X X X E E E [29 ] . We measure error in trace distance, Δ ( ρ , σ ) = 1 2 ∥ ρ − σ ∥ 1 \Delta(\rho,\sigma)=\frac{1}{2}\lVert\rho-\sigma\rVert_1 Δ ( ρ , σ ) = 2 1 ∥ ρ − σ ∥ 1 τ j = 2 − j I 2 j \tau_j=2^{-j}I_{2^j} τ j = 2 − j I 2 j j j j
Definition 1.4 (Quantum-proof extractors [15 ] ). A function Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m weak quantum-proof ( k , η ) (k,\eta) ( k , η ) ρ X E \rho_{XE} ρ X E X ∈ { 0 , 1 } n X\in\{0,1\}^n X ∈ { 0 , 1 } n H min ( X ∣ E ) ≥ k H_{\min}(X\mid E)\ge k H m i n ( X ∣ E ) ≥ k Y ∼ U d Y\sim U_d Y ∼ U d
Δ ( ρ Ext ( X , Y ) E , τ m ⊗ ρ E ) ≤ η . (1) \Delta(\rho_{\operatorname{Ext}(X,Y)E},\tau_m\otimes\rho_E)\le\eta. \tag*{(1)} Δ ( ρ Ext ( X , Y ) E , τ m ⊗ ρ E ) ≤ η . (1) The map Ext \operatorname{Ext} Ext strong if, for every cq state ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ≥ k H_{\min}(X\mid E)\ge k H m i n ( X ∣ E ) ≥ k
Δ ( ρ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ E ) ≤ η . (2) \Delta(\rho_{\operatorname{Ext}(X,Y)YE},\tau_m\otimes\tau_d\otimes\rho_E)\le\eta. \tag*{(2)} Δ ( ρ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ E ) ≤ η . (2) We call Ext \operatorname{Ext} Ext weak b b b ( k , η ) (k,\eta) ( k , η ) ρ X E \rho_{XE} ρ X E H ∞ ( X ) ≥ k H_\infty(X)\ge k H ∞ ( X ) ≥ k dim E ≤ 2 b \dim E\le2^b dim E ≤ 2 b strong version requires (1.2) instead [16 Definition 2.3] .
Several classical constructions are known to remain secure in this setting. König and Terhal [30 ] established quantum security for strong one-bit extractors, with a loss in parameters. Ta-Shma [50 ] and De and Vidick [16 ] developed short-seed constructions against bounded quantum storage based on Trevisan’s approach. De, Portmann, Vidick, and Renner [15 ] extended this approach to conditional min-entropy. At inverse-polynomial error, their constructions give entropy loss O ( log n ) O(\log n) O ( log n ) [6 ] provided an operator-space perspective, formulating classical and quantum-proof extraction through bounded and completely bounded norm conditions.
In light of the classical correspondence [Zuc97] between averaging samplers and extractors, it is also natural to ask for a sampling interpretation of quantum-proof extractors. Such interpretation would need to reflect the adversary’s access to side information and, for strong extractors, to the public seed. This motivates the structural question:
What type of sampler corresponds to a quantum-proof extractor?
Improving constructions. Alongside these structural questions, the parameter tradeoffs described above motivate the search for better explicit constructions. For matrix samplers, the challenge is to reduce the randomness overhead while keeping the sample complexity close to that of independent sampling, with mild dependence on the matrix dimension. For quantum-proof extractors, the challenge is to shorten the seed while retaining a large output over a wide range of entropy and error parameters. These are simultaneous requirements: improving one resource at the expense of another need not improve the overall tradeoff. This leads to a third question:
Our Results
Our first result establishes a correspondence between quantum-proof extractors and matrix samplers.
Theorem 1.5 (Quantum extractor–matrix sampler correspondence). Let F : { 0 , 1 } n × [ t ] → { 0 , 1 } m F : \{0,1\}^{n} \times[t] \to\{0,1\}^{m} F : { 0 , 1 } n × [ t ] → { 0 , 1 } m D ≥ 1 D \ge1 D ≥ 1 0 < δ , ε < 1 0 < \delta, \varepsilon< 1 0 < δ , ε < 1
If F F F log ( 2 D ) \log(2D) log ( 2 D ) ( n − log ( 1 / δ ) , ε / 2 ) (n-\log(1/\delta), \varepsilon/2) ( n − log ( 1/ δ ) , ε /2 ) F F F D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε )
Suppose F F F D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) 0 ≤ a ≤ n 0 \le a \le n 0 ≤ a ≤ n F F F ( log D ) (\log D) ( log D ) ( n − a , ε / 2 + 2 a δ ) (n-a,\varepsilon/2+2^{a}\delta) ( n − a , ε /2 + 2 a δ )
Every strong (resp. weak) quantum-proof ( k , η ) (k,\eta) ( k , η ) b b b ( k + b , η ) (k+b,\eta) ( k + b , η ) (15) . Therefore, a strong (resp. weak) quantum-proof ( n − log ( 2 D / δ ) , ε / 2 ) (n-\log(2D/\delta),\varepsilon/2) ( n − log ( 2 D / δ ) , ε /2 ) F : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m F : \{0,1\}^{n} \times\{0,1\}^{d} \to\{0,1\}^{m} F : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m
Strong matrix samplers For matrix samplers, we attain the following explicit construction which has optimal random seed length and simultaneously has the sample complexity being at most the ( 1 + α ) (1+\alpha) ( 1 + α ) α \alpha α
Theorem 1.6 (Strong matrix sampling). For every constant α > 0 \alpha> 0 α > 0 m m m D ≥ 1 D \ge1 D ≥ 1 0 < δ ≤ ε ≤ 1 / 2 0 < \delta\le\varepsilon\le1/2 0 < δ ≤ ε ≤ 1/2 D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m \operatorname{Samp} : \{0,1\}^{r} \times[t] \to\{0,1\}^{m} Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m
r = m + O α ( Λ ) , t = O α ( Λ 1 + α ε − 2 − α log ( Λ / ε ) ) (3) r = m + O_{\alpha}(\Lambda), \qquad t = O_{\alpha}\left(\frac{\Lambda^{1+\alpha}\varepsilon^{-2-\alpha}}{\log(\Lambda/\varepsilon)}\right) \tag*{(3)} r = m + O α ( Λ ) , t = O α ( log ( Λ/ ε ) Λ 1 + α ε − 2 − α ) (3) where Λ = log 2 ( 2 D / δ ) \Lambda= \log_{2}(2D/\delta) Λ = log 2 ( 2 D / δ ) x ∈ { 0 , 1 } r x \in\{0,1\}^{r} x ∈ { 0 , 1 } r i ∈ [ t ] i \in[t] i ∈ [ t ] Samp ( x , i ) \operatorname{Samp}(x,i) Samp ( x , i ) x x x i i i m + Λ + log ( 1 / ε ) m+\Lambda+\log(1/\varepsilon) m + Λ + log ( 1/ ε )
Compared with Xun and Zuckerman [XZ25, Theorem 3 and Remark 9], Theorem 1.6 removes the extra log log D \log\log D log log D D D D D D D O ( log ( D / δ ) ) 1 + α O(\log(D/\delta))^{1+\alpha} O ( log ( D / δ ) ) 1 + α Table 1 for detailed parameter comparison with previous works.
Table 1. Matrix samplers on { 0 , 1 } m \{0,1\}^m { 0 , 1 } m 0 < δ ≤ ε ≤ 1 / 2 0<\delta\le\varepsilon\le1/2 0 < δ ≤ ε ≤ 1/2 α , γ > 0 \alpha,\gamma>0 α , γ > 0
The Quantum-proof extractor for constructing our matrix sampler Our matrix sampler is attained via constructing the following quantum-proof extractor and deploying our correspondence between quantum-proof extractors and matrix samplers.
Theorem 1.7. For every constant α > 0 \alpha> 0 α > 0 n ≥ 1 n \ge1 n ≥ 1 0 ≤ k ≤ n 0 \le k \le n 0 ≤ k ≤ n 0 < η ≤ 1 / 2 0 < \eta\le1/2 0 < η ≤ 1/2 ( k , η ) (k,\eta) ( k , η ) Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext} : \{0,1\}^{n} \times\{0,1\}^{d} \to\{0,1\}^{m} Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m a = n − k a=n-k a = n − k
d ≤ ( 1 + α ) log a + ( 2 + α ) log ( 1 / η ) + O α ( 1 ) , (4) d \le(1+\alpha)\log a + (2+\alpha)\log(1/\eta) + O_{\alpha}(1), \tag*{(4)} d ≤ ( 1 + α ) log a + ( 2 + α ) log ( 1/ η ) + O α ( 1 ) , (4) m ≥ n − O α ( a + log ( 1 / η ) ) . (5) m \ge n - O_{\alpha}(a+\log(1/\eta)). \tag*{(5)} m ≥ n − O α ( a + log ( 1/ η )) . (5) The map Ext \operatorname{Ext} Ext
Notice that this theorem is used for constructing matrix samplers and the range of k k k k n \frac{k}{n} n k
Quantum-proof extractor for any constant entropy rate We also obtain optimal up to constant factor explicit quantum-proof extractors for any constant entropy rate and exponentially small error, improving previous constructions.
Theorem 1.8. For any constant 0 < μ < 1 0<\mu<1 0 < μ < 1 c μ > 0 c_\mu>0 c μ > 0 n n n μ n ≤ k ≤ n \mu n\le k\le n μ n ≤ k ≤ n 0 < η ≤ 1 / 2 0<\eta\le1/2 0 < η ≤ 1/2 log ( n / η ) ≤ c μ n \log(n/\eta)\le c_\mu n log ( n / η ) ≤ c μ n ( k , η ) (k,\eta) ( k , η ) Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m
d = O μ ( log ( n / η ) ) , m = Ω μ ( n ) . (6) d=O_\mu(\log(n/\eta)),\qquad m=\Omega_\mu(n). \tag*{(6)} d = O μ ( log ( n / η )) , m = Ω μ ( n ) . (6) The map Ext \operatorname{Ext} Ext
Notice that the error can be η ≥ 2 − c μ ′ n \eta\ge2^{-c'_\mu n} η ≥ 2 − c μ ′ n c μ ′ > 0 c'_\mu>0 c μ ′ > 0 ( 1 − θ ) k (1-\theta)k ( 1 − θ ) k θ \theta θ Corollary 5.4 ), with a constant factor blow-up for the seed length. The work of Ben-Aroya and Ta-Shma [BATS12, Theorem 1.3] achieves the same seed and output lengths as ours, up to constant factors. They require the conditional min-entropy k ≥ ( 1 2 + β ) n k\ge(\frac{1}{2}+\beta)n k ≥ ( 2 1 + β ) n β > 0 \beta>0 β > 0 Table 2 .
Table 2. Strong extractors secure against quantum side information, for sources on { 0 , 1 } n \{0,1\}^n { 0 , 1 } n 0 < η ≤ 1 / 2 0<\eta\le1/2 0 < η ≤ 1/2 [50 ] , 0 < β < 1 0<\beta<1 0 < β < 1 0 < γ < ( 1 − β ) / 15 0<\gamma<(1-\beta)/15 0 < γ < ( 1 − β ) /15 [16 ] , γ , c , ν > 0 \gamma,c,\nu>0 γ , c , ν > 0 0 < α < 1 0<\alpha<1 0 < α < 1 [15 Corollary 5.6] , 0 < γ < ν ≤ 1 0<\gamma<\nu\le1 0 < γ < ν ≤ 1 c > 0 c>0 c > 0 0 < β < 1 / 2 0<\beta<1/2 0 < β < 1/2 0 < μ < 1 0<\mu<1 0 < μ < 1 α > 0 \alpha>0 α > 0 1 ≤ a ≤ n 1\le a\le n 1 ≤ a ≤ n c μ ′ > 0 c'_\mu>0 c μ ′ > 0 n n n
Technical Overview
The quantum extractor–matrix sampler correspondence. Let F : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m F:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m F : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m ( n − Λ , ε / 2 ) (n-\Lambda,\varepsilon/2) ( n − Λ , ε /2 ) Λ = log ( 2 D / δ ) \Lambda=\log(2D/\delta) Λ = log ( 2 D / δ ) f y : { 0 , 1 } m → C D × D f_y:\{0,1\}^m\to\mathbb{C}^{D\times D} f y : { 0 , 1 } m → C D × D ∥ f y ( z ) ∥ ≤ 1 \lVert f_y(z)\rVert\le1 ∥ f y ( z )∥ ≤ 1
A x = E y f y ( F ( x , y ) ) − E y , z f y ( z ) , A_x=\mathbb{E}_y f_y(F(x,y))-\mathbb{E}_{y,z}f_y(z), A x = E y f y ( F ( x , y )) − E y , z f y ( z ) , where y ∈ { 0 , 1 } d y\in\{0,1\}^d y ∈ { 0 , 1 } d z ∈ { 0 , 1 } m z\in\{0,1\}^m z ∈ { 0 , 1 } m B = { x : ∥ A x ∥ > ε } \mathcal{B}=\{x:\lVert A_x\rVert>\varepsilon\} B = { x : ∥ A x ∥ > ε } δ 2 n \delta2^n δ 2 n
Write H ( A ) = ( 0 A A ∗ 0 ) \mathcal{H}(A)=\begin{pmatrix} 0 & A \\ A^* & 0 \end{pmatrix} H ( A ) = ( 0 A ∗ A 0 ) A A A x ∈ B x\in\mathcal{B} x ∈ B v x v_x v x H ( A x ) \mathcal{H}(A_x) H ( A x ) ∥ A x ∥ \lVert A_x\rVert ∥ A x ∥ X X X B \mathcal{B} B X = x X=x X = x E E E ∣ v x ⟩ ⟨ v x ∣ |v_x\rangle\langle v_x| ∣ v x ⟩ ⟨ v x ∣ ρ X E \rho_{XE} ρ X E dim E = 2 D \dim E=2D dim E = 2 D
H min ( X ∣ E ) ρ ≥ log ∣ B ∣ − log ( 2 D ) > n − Λ , H_{\min}(X\mid E)_\rho\ge\log|\mathcal{B}|-\log(2D)>n-\Lambda, H m i n ( X ∣ E ) ρ ≥ log ∣ B ∣ − log ( 2 D ) > n − Λ , so the source meets the extractor’s entropy requirement.
For each seed i ∈ [ t ] i\in[t] i ∈ [ t ] z ∈ { 0 , 1 } m z\in\{0,1\}^m z ∈ { 0 , 1 } m M i , z = ( I 2 D + H ( f i ( z ) ) ) / 2 M_{i,z}=(I_{2D}+\mathcal{H}(f_i(z)))/2 M i , z = ( I 2 D + H ( f i ( z ))) /2 0 ⪯ M i , z ⪯ I 2 D 0\preceq M_{i,z}\preceq I_{2D} 0 ⪯ M i , z ⪯ I 2 D
M = ∑ z ∈ { 0 , 1 } m ∑ i = 1 t ∣ z ⟩ ⟨ z ∣ ⊗ ∣ i ⟩ ⟨ i ∣ ⊗ M i , z M=\sum_{z\in\{0,1\}^m}\sum_{i=1}^t |z\rangle\langle z|\otimes|i\rangle\langle i|\otimes M_{i,z} M = z ∈ { 0 , 1 } m ∑ i = 1 ∑ t ∣ z ⟩ ⟨ z ∣ ⊗ ∣ i ⟩ ⟨ i ∣ ⊗ M i , z defines a POVM { M , I − M } \{M,I-M\} { M , I − M } M M M ρ F ( X , I ) I E \rho_{F(X,I)IE} ρ F ( X , I ) I E τ m ⊗ ρ I E \tau_m\otimes\rho_{IE} τ m ⊗ ρ I E ε / 2 \varepsilon/2 ε /2
Conversely, suppose F F F D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) ρ X E \rho_{XE} ρ X E H ∞ ( X ) ρ ≥ n − a H_\infty(X)_\rho\ge n-a H ∞ ( X ) ρ ≥ n − a dim E ≤ D \dim E\le D dim E ≤ D E E E 0 ⪯ M y , z ⪯ I 0\preceq M_{y,z}\preceq I 0 ⪯ M y , z ⪯ I E E E f y ( z ) = 2 M y , z − I f_y(z)=2M_{y,z}-I f y ( z ) = 2 M y , z − I ∥ f y ( z ) ∥ ≤ 1 \|f_y(z)\|\le1 ∥ f y ( z ) ∥ ≤ 1 ε / 2 \varepsilon/2 ε /2 δ 2 n \delta2^n δ 2 n 2 a − n 2^{a-n} 2 a − n 2 a δ 2^a\delta 2 a δ X X X ε / 2 + 2 a δ \varepsilon/2+2^a\delta ε /2 + 2 a δ
A quantum-proof extractor with linear output. Fix a constant 0 < μ ≤ 1 0<\mu\le1 0 < μ ≤ 1 h = log ( n / η ) h=\log(n/\eta) h = log ( n / η ) h ≤ c μ n h\le c_\mu n h ≤ c μ n c μ > 0 c_\mu>0 c μ > 0 [39 ] to obtain an explicit strong quantum-proof ( μ n , η ) (\mu n,\eta) ( μ n , η ) d = O μ ( h log 2 ( n / h ) ) d=O_\mu(h\log^2(n/h)) d = O μ ( h log 2 ( n / h )) m = Ω μ ( n ) m=\Omega_\mu(n) m = Ω μ ( n ) Lemma 4.5 ).
We first construct a strong quantum-proof extractor that produces a single block of Θ ( h ) \Theta(h) Θ ( h ) λ = Θ ( h ) \lambda=\Theta(h) λ = Θ ( h ) ℓ = Θ ( log ( n / h ) ) \ell=\Theta(\log(n/h)) ℓ = Θ ( log ( n / h )) m 0 = Θ ( λ ) m_0=\Theta(\lambda) m 0 = Θ ( λ ) n ≤ λ 2 n\le\lambda^2 n ≤ λ 2 m 0 ≤ λ m_0\le\lambda m 0 ≤ λ x ∼ X x \sim X x ∼ X x x x p x p_x p x F 2 \mathbb{F}_2 F 2 ℓ \ell ℓ F ( x , u ) = p x ( u ) F(x,u)=p_x(u) F ( x , u ) = p x ( u ) { h w : F 2 λ → { 0 , 1 } m 0 } w ∈ F 2 λ \{h_w:\mathbb{F}_2^\lambda\to\{0,1\}^{m_0}\}_{w\in\mathbb{F}_2^\lambda} { h w : F 2 λ → { 0 , 1 } m 0 } w ∈ F 2 λ U ∈ F 2 λ U\in\mathbb{F}_{2^\lambda} U ∈ F 2 λ W ∈ F 2 λ W\in\mathbb{F}_2^\lambda W ∈ F 2 λ h W ( F ( X , U ) ) h_W(F(X,U)) h W ( F ( X , U ))
The collision bound of [51 Lemma 5] and the quantum leftover hash lemma [37 Theorem 5.5.1] give Lemma 4.1 . Applying the lemma to F , h W F,h_W F , h W m 0 m_0 m 0 λ ( ℓ + 1 ) = O ( h log ( n / h ) ) \lambda(\ell+1)=O(h\log(n/h)) λ ( ℓ + 1 ) = O ( h log ( n / h ))
1 2 2 m 0 ( 2 − k + ℓ 2 − λ ) (7) \frac{1}{2}\sqrt{2^{m_0}(2^{-k}+\ell2^{-\lambda})} \tag*{(7)} 2 1 2 m 0 ( 2 − k + ℓ 2 − λ ) (7) for every source ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ρ ≥ k H_{\min}(X\mid E)_\rho\ge k H m i n ( X ∣ E ) ρ ≥ k
To obtain linear output, we use a weak design to generate the evaluation points for M M M ( ℓ , ϱ ) (\ell,\varrho) ( ℓ , ϱ ) S 1 , … , S M ⊆ [ v ] S_1,\ldots,S_M\subseteq[v] S 1 , … , S M ⊆ [ v ] ∣ S i ∣ = ℓ |S_i|=\ell ∣ S i ∣ = ℓ ∑ j < i 2 ∣ S i ∩ S j ∣ ≤ ϱ M \sum_{j<i}2^{|S_i\cap S_j|}\le\varrho M ∑ j < i 2 ∣ S i ∩ S j ∣ ≤ ϱM i i i ϱ = 2 \varrho=2 ϱ = 2 ℓ = Θ ( log ( n / h ) ) \ell=\Theta(\log(n/h)) ℓ = Θ ( log ( n / h )) v = O ( ℓ 2 ) v=O(\ell^2) v = O ( ℓ 2 ) [39 Lemma 15] . Choose M = Θ μ ( n / λ ) M=\Theta_\mu(n/\lambda) M = Θ μ ( n / λ ) λ ϱ M ≤ μ n / 4 \lambda\varrho M\le\mu n/4 λ ϱM ≤ μ n /4 Y ∈ F 2 λ Y\in\mathbb{F}_2^\lambda Y ∈ F 2 λ Z i = h W ( F ( X , Y ∣ S i ) ) Z_i=h_W(F(X,Y|_{S_i})) Z i = h W ( F ( X , Y ∣ S i ))
Fix an output block Z i Z_i Z i Z i Z_i Z i Z 1 , … , Z i − 1 Z_1,\ldots,Z_{i-1} Z 1 , … , Z i − 1 E E E Y ∣ [ v ] ∖ S i Y|_{[v]\setminus S_i} Y ∣ [ v ] ∖ S i j < i j<i j < i p X ( Y ∣ S j ) p_X(Y|_{S_j}) p X ( Y ∣ S j ) S i ∩ S j S_i\cap S_j S i ∩ S j j < i j<i j < i A i A_i A i ( A i , Y , W ) (A_i,Y,W) ( A i , Y , W ) Z 1 , … , Z i − 1 Z_1,\ldots,Z_{i-1} Z 1 , … , Z i − 1
Each restricted polynomial has at most 2 ∣ S i ∩ S j ∣ 2^{|S_i\cap S_j|} 2 ∣ S i ∩ S j ∣ λ \lambda λ H min ( X ∣ E ) ρ ≥ k H_{\min}(X\mid E)_\rho\ge k H m i n ( X ∣ E ) ρ ≥ k
∣ A i ∣ ≤ λ ∑ j < i 2 ∣ S i ∩ S j ∣ ≤ λ ϱ M , H min ( X ∣ A i E ) ρ ≥ k − λ ϱ M . |A_i|\le\lambda\sum_{j<i}2^{|S_i\cap S_j|}\le\lambda\varrho M,\qquad H_{\min}(X\mid A_iE)_\rho\ge k-\lambda\varrho M. ∣ A i ∣ ≤ λ j < i ∑ 2 ∣ S i ∩ S j ∣ ≤ λ ϱM , H m i n ( X ∣ A i E ) ρ ≥ k − λ ϱM . The advice A i A_i A i X X X S i S_i S i Y ∣ S i Y|_{S_i} Y ∣ S i W W W X A i E XA_iE X A i E X X X Y ∣ S i , W Y|_{S_i},W Y ∣ S i , W A i E A_iE A i E k = μ n k=\mu n k = μ n 3 μ n / 4 3\mu n/4 3 μ n /4 λ \lambda λ m 0 m_0 m 0 Z i Z_i Z i η / M \eta/M η / M A i , Y , W , E A_i,Y,W,E A i , Y , W , E A i , Y , W A_i,Y,W A i , Y , W Z i Z_i Z i η / M \eta/M η / M Z 1 , … , Z i − 1 , Y , W , E Z_1,\ldots,Z_{i-1},Y,W,E Z 1 , … , Z i − 1 , Y , W , E
We can therefore replace the output by uniform blocks, block by block in the order Z M , … , Z 1 Z_M,\ldots,Z_1 Z M , … , Z 1 η / M \eta/M η / M η \eta η M m 0 = Ω μ ( n ) Mm_0=\Omega_\mu(n) M m 0 = Ω μ ( n ) λ ( v + 1 ) = O ( h log 2 ( n / h ) ) \lambda(v+1)=O(h\log^2(n/h)) λ ( v + 1 ) = O ( h log 2 ( n / h ))
Reducing the seed length. We next construct an extractor G G G O μ ( h ) O_\mu(h) O μ ( h ) O μ ( h log 2 ( n / h ) ) O_\mu(h\log^2(n/h)) O μ ( h log 2 ( n / h )) ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ρ ≥ μ n H_{\min}(X\mid E)_\rho\ge\mu n H m i n ( X ∣ E ) ρ ≥ μ n Lemma 5.1 ), a common public seed R R R B 0 , … , B T − 1 B_0,\ldots,B_{T-1} B 0 , … , B T − 1 R R R O μ ( h ) O_\mu(h) O μ ( h ) Θ μ ( n h ) \Theta_\mu(\sqrt{nh}) Θ μ ( nh )
To grow the seed, we use the short-seed extractor of Lemma 5.2 . To obtain m m m η / ( 2 T ) \eta/(2T) η / ( 2 T ) m + O ( log ( T / η ) ) m+O(\log(T/\eta)) m + O ( log ( T / η )) 2 m + O ( h ) 2m+O(h) 2 m + O ( h ) O μ ( h ) O_\mu(h) O μ ( h ) Z 0 Z_0 Z 0 Z j Z_j Z j Z j + 1 Z_{j+1} Z j + 1 j = 0 , … , T − 1 j=0,\ldots,T-1 j = 0 , … , T − 1 H j H_j H j ∣ Z j ∣ |Z_j| ∣ Z j ∣ ⌊ ∣ Z j ∣ / 4 ⌋ \lfloor|Z_j|/4\rfloor ⌊ ∣ Z j ∣/4 ⌋ H j H_j H j B T − 1 − j B_{T-1-j} B T − 1 − j ∘ \circ ∘
Z j + 1 = Z j ∘ H j ( B T − 1 − j , Z j ) . (8) Z_{j+1}=Z_j\circ H_j(B_{T-1-j},Z_j). \tag*{(8)} Z j + 1 = Z j ∘ H j ( B T − 1 − j , Z j ) . (8) Each application of (8) increases the seed length by a constant factor, so T = O ( log log ( n / h ) ) T = O(\log\log(n/h)) T = O ( log log ( n / h )) ( R , Z 0 ) (R, Z_0) ( R , Z 0 ) Z T = Z 0 ∘ W Z_T = Z_0 \circ W Z T = Z 0 ∘ W G G G W W W O μ ( h log 2 ( n / h ) ) O_\mu(h\log^2(n/h)) O μ ( h log 2 ( n / h ))
The reverse order ensures that each block retains entropy given all blocks still to be processed. Write B < i = ( B 0 , … , B i − 1 ) B_{<i} = (B_0,\ldots,B_{i-1}) B < i = ( B 0 , … , B i − 1 ) B i B_i B i R E RE R E H min τ H_{\min}^{\tau} H m i n τ (18) ). Revealing B < i B_{<i} B < i ∑ q < i ∣ B q ∣ \sum_{q<i}|B_q| ∑ q < i ∣ B q ∣
H min τ ( B i ∣ B < i R E ) ρ ≥ c μ ∣ B i ∣ , (9) H_{\min}^{\tau}(B_i \mid B_{<i}RE)_\rho\ge c_\mu|B_i|, \tag*{(9)} H m i n τ ( B i ∣ B < i R E ) ρ ≥ c μ ∣ B i ∣ , (9) where c μ > 0 c_\mu> 0 c μ > 0 τ = η / ( 8 T ) \tau= \eta/(8T) τ = η / ( 8 T ) Ω μ ( n h ) \Omega_\mu(\sqrt{nh}) Ω μ ( nh ) n / h n/h n / h
We show by induction that, after j j j (8) , Z j Z_j Z j j η / T j\eta/T j η / T R E RE R E B < T − j B_{<T-j} B < T − j Z 0 Z_0 Z 0 j < T j < T j < T i = T − 1 − j i = T - 1 - j i = T − 1 − j Z j Z_j Z j V j V_j V j B i B < i R E B_iB_{<i}RE B i B < i R E j η / T j\eta/T j η / T (8) cannot increase the distance. By (9) , the block B i B_i B i H j H_j H j B < i R E B_{<i}RE B < i R E V j ∘ H j ( B i , V j ) V_j \circ H_j(B_i,V_j) V j ∘ H j ( B i , V j ) η / T \eta/T η / T B < i R E B_{<i}RE B < i R E ( j + 1 ) η / T (j+1)\eta/T ( j + 1 ) η / T Z j + 1 Z_{j+1} Z j + 1
Taking j = T j = T j = T Z T Z_T Z T η \eta η R E RE R E Z T = Z 0 ∘ W Z_T = Z_0 \circ W Z T = Z 0 ∘ W W W W η \eta η R , Z 0 , E R, Z_0, E R , Z 0 , E
Finally, combine G G G F l i n F_{\mathrm{lin}} F lin A A A S ( A ) ⊆ [ n ] S(A) \subseteq[n] S ( A ) ⊆ [ n ] B = X S ( A ) B = X_{S(A)} B = X S ( A ) C = X [ n ] ∖ S ( A ) C = X_{[n]\setminus S(A)} C = X [ n ] ∖ S ( A ) Y Y Y
F l i n ( B , G ( C , Y ) ) . F_{\mathrm{lin}}(B,G(C,Y)). F lin ( B , G ( C , Y )) . Entropy sampling gives B B B A E AE A E (16) gives C C C B A E BAE B A E G ( C , Y ) G(C,Y) G ( C , Y ) B A Y E BAYE B A Y E F l i n F_{\mathrm{lin}} F lin F l i n F_{\mathrm{lin}} F lin B B B Ω μ ( n ) \Omega_\mu(n) Ω μ ( n ) η \eta η O μ ( h ) O_\mu(h) O μ ( h )
Extraction with small output loss. We combine our constant-rate extractor with a quantum-proof version of the Goldreich–Wigderson extractor. For sources of conditional min-entropy n − a n-a n − a O ( a + log ( 1 / η ) ) O(a+\log(1/\eta)) O ( a + log ( 1/ η )) [24 Theorem 4.2 and Lemma 4.3] , together with the lifting theorem of Berta, Fawzi, and Scholz [6 ] , gives a quantum-proof extractor H H H O ( a + log ( 1 / η ) ) O(a+\log(1/\eta)) O ( a + log ( 1/ η ))
Split the source into a block B B B C 0 ( a + log ( 1 / η ) ) C_0(a+\log(1/\eta)) C 0 ( a + log ( 1/ η )) Z Z Z C 0 C_0 C 0 F F F B B B Y Y Y
H ( Z , F ( B , Y ) ) . H(Z,F(B,Y)). H ( Z , F ( B , Y )) . Equation (16) gives H min ( B ∣ Z E ) ρ ≥ ∣ B ∣ − a H_{\min}(B\mid ZE)_\rho\ge|B|-a H m i n ( B ∣ Z E ) ρ ≥ ∣ B ∣ − a H min ( Z ∣ E ′ ) ρ ≥ ∣ Z ∣ − a H_{\min}(Z\mid E')_\rho\ge|Z|-a H m i n ( Z ∣ E ′ ) ρ ≥ ∣ Z ∣ − a B B B Z E ZE Z E F ( B , Y ) F(B,Y) F ( B , Y ) Z Y E ZYE Z Y E H ( Z , F ( B , Y ) ) H(Z,F(B,Y)) H ( Z , F ( B , Y )) η \eta η Y E YE Y E Y Y Y O ( log a + log ( 1 / η ) ) O(\log a+\log(1/\eta)) O ( log a + log ( 1/ η )) B B B O ( a + log ( 1 / η ) ) O(a+\log(1/\eta)) O ( a + log ( 1/ η ))
Refining the extractor’s seed length. To shorten the public seed further, split the source into an n n n X X X s s s Z Z Z Ext 0 : { 0 , 1 } n × { 0 , 1 } d 0 → { 0 , 1 } m \operatorname{Ext}_0:\{0,1\}^n \times\{0,1\}^{d_0} \to\{0,1\}^m Ext 0 : { 0 , 1 } n × { 0 , 1 } d 0 → { 0 , 1 } m X X X d 0 = O ( log a + log ( 1 / η ) ) d_0 = O(\log a+\log(1/\eta)) d 0 = O ( log a + log ( 1/ η )) η 0 = η / 2 \eta_0 = \eta/2 η 0 = η /2 Z Z Z Ext 0 \operatorname{Ext}_0 Ext 0
Fix integers ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 t ≥ ℓ t \ge\ell t ≥ ℓ z z z ( 2 ℓ − 1 ) (2\ell- 1) ( 2 ℓ − 1 ) p z p_z p z p z p_z p z u 1 , … , u t u_1,\ldots,u_t u 1 , … , u t d 0 d_0 d 0 G ( z , 1 ) , … , G ( z , t ) G(z,1),\ldots,G(z,t) G ( z , 1 ) , … , G ( z , t ) G : { 0 , 1 } s × [ t ] → { 0 , 1 } d 0 G:\{0,1\}^s \times[t] \to\{0,1\}^{d_0} G : { 0 , 1 } s × [ t ] → { 0 , 1 } d 0 s = O ( ℓ ( d 0 + log t ) ) s = O(\ell(d_0+\log t)) s = O ( ℓ ( d 0 + log t )) G ( U s , 1 ) , … , G ( U s , t ) G(U_s,1),\ldots,G(U_s,t) G ( U s , 1 ) , … , G ( U s , t ) 2 ℓ 2\ell 2 ℓ J J J [ t ] [t] [ t ] X Z E XZE X Z E
V = Ext ( ( X , Z ) ; J ) = Ext 0 ( X ; G ( Z , J ) ) . V = \operatorname{Ext}((X,Z);J) = \operatorname{Ext}_0(X;G(Z,J)). V = Ext (( X , Z ) ; J ) = Ext 0 ( X ; G ( Z , J )) . The candidate seed G ( Z , J ) G(Z,J) G ( Z , J ) X X X E E E Ext 0 ( X ; G ( Z , J ) ) \operatorname{Ext}_0(X;G(Z,J)) Ext 0 ( X ; G ( Z , J )) Ext 0 ( X ; U ) \operatorname{Ext}_0(X;U) Ext 0 ( X ; U ) U U U d 0 d_0 d 0 X Z E J XZEJ X Z E J ρ V J E \rho_{VJE} ρ V J E σ V J E \sigma_{VJE} σ V J E V V V m m m H min ( X Z ∣ E ) ≥ n + s − a H_{\min}(XZ \mid E) \ge n+s-a H m i n ( X Z ∣ E ) ≥ n + s − a H min ( X ∣ E ) ≥ n − a H_{\min}(X \mid E) \ge n-a H m i n ( X ∣ E ) ≥ n − a Ext 0 \operatorname{Ext}_0 Ext 0
Δ ( σ V J E , τ m ⊗ ρ J E ) ≤ η 0 . (10) \Delta(\sigma_{VJE},\tau_m \otimes\rho_{JE}) \le\eta_0. \tag*{(10)} Δ ( σ V J E , τ m ⊗ ρ J E ) ≤ η 0 . (10) A 2 ℓ 2\ell 2 ℓ U U U G ( Z , J ) G(Z,J) G ( Z , J ) Theorem 6.4 ):
Δ ( ρ V J E , σ V J E ) ≤ 2 a / ( 2 ℓ ) 3 ℓ t . (11) \Delta(\rho_{VJE},\sigma_{VJE}) \le2^{a/(2\ell)}\sqrt{\frac{3\ell}{t}}. \tag*{(11)} Δ ( ρ V J E , σ V J E ) ≤ 2 a / ( 2 ℓ ) t 3 ℓ . (11) For t = Θ ( η − 2 ℓ 2 a / ℓ ) t = \Theta(\eta^{-2}\ell2^{a/\ell}) t = Θ ( η − 2 ℓ 2 a / ℓ ) (10) and (11) give Δ ( ρ V J E , τ m ⊗ ρ J E ) ≤ η \Delta(\rho_{VJE},\tau_m \otimes\rho_{JE}) \le\eta Δ ( ρ V J E , τ m ⊗ ρ J E ) ≤ η
d = log t ≤ 2 log ( 1 / η ) + log ℓ + a ℓ + O ( 1 ) . d = \log t \le2\log(1/\eta) + \log\ell+ \frac{a}{\ell} + O(1). d = log t ≤ 2 log ( 1/ η ) + log ℓ + ℓ a + O ( 1 ) . Increasing ℓ \ell ℓ a / ℓ a/\ell a / ℓ s s s d ≤ ( 1 + α ) log a + ( 2 + α ) log ( 1 / η ) + O α ( 1 ) d \le(1+\alpha)\log a + (2+\alpha)\log(1/\eta) + O_\alpha(1) d ≤ ( 1 + α ) log a + ( 2 + α ) log ( 1/ η ) + O α ( 1 ) O α ( a + log ( 1 / η ) ) O_\alpha(a+\log(1/\eta)) O α ( a + log ( 1/ η )) Theorem 1.7 .
Sampler parameters from the extractor. Apply the correspondence (23) with deficiency a = ⌈ log ( 4 D / δ ) ⌉ a = \lceil\log(4D/\delta)\rceil a = ⌈ log ( 4 D / δ )⌉ η = ε / 4 \eta= \varepsilon/4 η = ε /4 d d d 2 d 2^d 2 d ℓ \ell ℓ Theorem 1.6 , with randomness m + O α ( log ( D / δ ) ) m+O_\alpha(\log(D/\delta)) m + O α ( log ( D / δ ))
Preliminaries
All logarithms are base two. Logarithmic factors in asymptotic bounds are understood to be at least one. For entropy deficiency a ≥ 0 a \ge0 a ≥ 0 log a = log 2 max { 2 , a } \log a = \log_2 \max\{2,a\} log a = log 2 max { 2 , a } 0 < δ ≤ ε ≤ 1 / 2 0 < \delta\le\varepsilon\le1/2 0 < δ ≤ ε ≤ 1/2 A A A U A U_A U A τ A \tau_A τ A A A A Δ \Delta Δ
We use n , d , m n,d,m n , d , m n − m n-m n − m n − k n-k n − k r r r t t t D D D δ \delta δ ε \varepsilon ε η \eta η b b b dim E ≤ 2 b \dim E \le2^b dim E ≤ 2 b
Hermitian dilation
Hermitian dilation
The Hermitian dilation of A ∈ C D × D A \in\mathbb{C}^{D \times D} A ∈ C D × D
H ( A ) = ( 0 A A ∗ 0 ) . \mathcal{H}(A)=\begin{pmatrix}0 & A \\ A^* & 0\end{pmatrix}. H ( A ) = ( 0 A ∗ A 0 ) . The identity
H ( A ) 2 = ( A A ∗ 0 0 A ∗ A ) \mathcal{H}(A)^2=\begin{pmatrix}AA^* & 0 \\ 0 & A^*A\end{pmatrix} H ( A ) 2 = ( A A ∗ 0 0 A ∗ A ) gives ∥ H ( A ) ∥ = ∥ A ∥ \|\mathcal{H}(A)\|=\|A\| ∥ H ( A ) ∥ = ∥ A ∥ H ( A ) \mathcal{H}(A) H ( A ) diag ( I , − I ) \operatorname{diag}(I,-I) diag ( I , − I ) diag − 1 ( I , − I ) H ( A ) diag ( I , − I ) \operatorname{diag}^{-1}(I,-I)\mathcal{H}(A)\operatorname{diag}(I,-I) diag − 1 ( I , − I ) H ( A ) diag ( I , − I ) H ( A ) \mathcal{H}(A) H ( A ) H ( A ) \mathcal{H}(A) H ( A ) H ( A ) \mathcal{H}(A) H ( A ) ∥ A ∥ \|A\| ∥ A ∥ H \mathcal{H} H
Quantum side information and extraction
A quantum state on a finite-dimensional register is represented by a positive semidefinite operator ρ \rho ρ Tr ρ = 1 \operatorname{Tr}\rho=1 Tr ρ = 1 Tr ρ ≤ 1 \operatorname{Tr}\rho\le1 Tr ρ ≤ 1 ∥ A ∥ 1 = Tr A ∗ A \|A\|_1=\operatorname{Tr}\sqrt{A^*A} ∥ A ∥ 1 = Tr A ∗ A
A classical–quantum (cq) state ρ X E \rho_{XE} ρ X E X X X E E E ρ E x \rho_E^x ρ E x x ∈ supp ( X ) x\in\operatorname{supp}(X) x ∈ supp ( X )
ρ X E = ∑ x ∣ x ⟩ ⟨ x ∣ ⊗ ρ E x , ρ E = ∑ x ρ E x . \rho_{XE}=\sum_x |x\rangle\langle x|\otimes\rho_E^x,\qquad\rho_E=\sum_x\rho_E^x. ρ X E = x ∑ ∣ x ⟩ ⟨ x ∣ ⊗ ρ E x , ρ E = x ∑ ρ E x . The min-entropy of a classical random variable X X X H ∞ ( X ) : = − log max x Pr [ X = x ] H_\infty(X):=-\log\max_x\Pr[X=x] H ∞ ( X ) := − log max x Pr [ X = x ] ρ X E \rho_{XE} ρ X E H ∞ ( X ) ρ : = − log max x Tr ρ E x H_\infty(X)_\rho:=-\log\max_x\operatorname{Tr}\rho_E^x H ∞ ( X ) ρ := − log max x Tr ρ E x
A positive operator-valued measurement (POVM) is a family of positive semidefinite matrices ( M x ) x ∈ supp ( X ) (M_x)_{x\in\operatorname{supp}(X)} ( M x ) x ∈ supp ( X ) ∑ x M x = I \sum_x M_x=I ∑ x M x = I ( M x ) x (M_x)_x ( M x ) x X X X ∑ x Tr ( M x ρ E x ) \sum_x\operatorname{Tr}(M_x\rho_E^x) ∑ x Tr ( M x ρ E x ) X X X E E E
p g u e s s ( X ∣ E ) ρ : = max ( M x ) x ∑ x Tr ( M x ρ E x ) , (12) p_{\mathrm{guess}}(X\mid E)_\rho:=\max_{(M_x)_x}\sum_x\operatorname{Tr}(M_x\rho_E^x), \tag*{(12)} p guess ( X ∣ E ) ρ := ( M x ) x max x ∑ Tr ( M x ρ E x ) , (12) where the maximum is over POVMs on E E E H min ( X ∣ E ) ρ = − log p g u e s s ( X ∣ E ) ρ H_{\min}(X\mid E)_\rho=-\log p_{\mathrm{guess}}(X\mid E)_\rho H m i n ( X ∣ E ) ρ = − log p guess ( X ∣ E ) ρ [29 Theorem 1]
2 − H min ( X ∣ E ) = min { Tr W E : W E ⪰ ρ E x for every x } . (13) 2^{-H_{\min}(X\mid E)}=\min\{\operatorname{Tr}W_E:W_E\succeq\rho_E^x\text{ for every }x\}. \tag*{(13)} 2 − H m i n ( X ∣ E ) = min { Tr W E : W E ⪰ ρ E x for every x } . (13) Thus H min ( X ∣ E ) ≥ k H_{\min}(X\mid E)\ge k H m i n ( X ∣ E ) ≥ k ω E \omega_E ω E ρ E x ⪯ 2 − k ω E \rho_E^x\preceq2^{-k}\omega_E ρ E x ⪯ 2 − k ω E x x x (13) also defines the conditional min-entropy for subnormalized cq states ( X , E ) (X,E) ( X , E )
A matrix M M M 0 ⪯ M ⪯ I 0\preceq M\preceq I 0 ⪯ M ⪯ I { M , I − M } \{M,I-M\} { M , I − M } M M M Tr ( M ρ ) \operatorname{Tr}(M\rho) Tr ( M ρ ) ρ \rho ρ
Δ ( ρ , σ ) : = max 0 ⪯ M ⪯ I ∣ Tr M ( ρ − σ ) ∣ . (14) \Delta(\rho,\sigma):=\max_{0\preceq M\preceq I}\left|\operatorname{Tr}M(\rho-\sigma)\right|. \tag*{(14)} Δ ( ρ , σ ) := 0 ⪯ M ⪯ I max ∣ Tr M ( ρ − σ ) ∣ . (14) A quantum channel is a completely positive, trace-preserving map. Trace distance is contractive under quantum channels: Δ ( Φ ( ρ ) , Φ ( σ ) ) ≤ Δ ( ρ , σ ) \Delta(\Phi(\rho),\Phi(\sigma))\le\Delta(\rho,\sigma) Δ ( Φ ( ρ ) , Φ ( σ )) ≤ Δ ( ρ , σ ) Φ \Phi Φ
For a state ρ X V E \rho_{XVE} ρ X V E X X X V V V E E E V V V a a a
H min ( X ∣ V E ) ρ ≥ H min ( X ∣ E ) ρ − a , H min ( X ∣ E ) ρ ≥ H ∞ ( X ) ρ − log dim E , (15) H_{\min}(X \mid VE)_{\rho} \ge H_{\min}(X \mid E)_{\rho} - a,\qquad H_{\min}(X \mid E)_{\rho} \ge H_{\infty}(X)_{\rho} - \log\dim E, \tag*{(15)} H m i n ( X ∣ V E ) ρ ≥ H m i n ( X ∣ E ) ρ − a , H m i n ( X ∣ E ) ρ ≥ H ∞ ( X ) ρ − log dim E , (15) where 2nd inequality of (15) follows from (13) by taking ( max x Pr [ X = x ] ) I E (\max_x \Pr[X=x])I_E ( max x Pr [ X = x ]) I E ρ X 1 X 2 E \rho_{X_1X_2E} ρ X 1 X 2 E ( X 1 , X 2 ) (X_1,X_2) ( X 1 , X 2 ) E E E
H min ( X 1 ∣ E ) ρ ≥ H min ( X 1 X 2 ∣ E ) ρ − ∣ X 2 ∣ , H min ( X 2 ∣ X 1 E ) ρ ≥ H min ( X 1 X 2 ∣ E ) ρ − ∣ X 1 ∣ . (16) H_{\min}(X_1 \mid E)_{\rho} \ge H_{\min}(X_1X_2 \mid E)_{\rho} - |X_2|,\qquad H_{\min}(X_2 \mid X_1E)_{\rho} \ge H_{\min}(X_1X_2 \mid E)_{\rho} - |X_1|. \tag*{(16)} H m i n ( X 1 ∣ E ) ρ ≥ H m i n ( X 1 X 2 ∣ E ) ρ − ∣ X 2 ∣ , H m i n ( X 2 ∣ X 1 E ) ρ ≥ H m i n ( X 1 X 2 ∣ E ) ρ − ∣ X 1 ∣. (16) The above leakage inequality and chain inequalities follow from Renner’s min-entropy inequalities [37 Lemmas 3.1.9–3.1.10] .
Smooth min-entropy. We will define the smooth min-entropy of ρ X E \rho_{XE} ρ X E ρ , σ \rho,\sigma ρ , σ
F ‾ ( ρ , σ ) = ∥ ρ σ ∥ 1 + ( 1 − Tr ρ ) ( 1 − Tr σ ) , \overline{F}(\rho,\sigma) = \left\|\sqrt{\rho}\sqrt{\sigma}\right\|_1 + \sqrt{(1-\operatorname{Tr}\rho)(1-\operatorname{Tr}\sigma)}, F ( ρ , σ ) = ρ σ 1 + ( 1 − Tr ρ ) ( 1 − Tr σ ) , P ( ρ , σ ) = 1 − F ‾ ( ρ , σ ) 2 . P(\rho,\sigma) = \sqrt{1-\overline{F}(\rho,\sigma)^2}. P ( ρ , σ ) = 1 − F ( ρ , σ ) 2 . Purified distance is contractive under quantum channels [47 Lemma 7] , i.e. for subnormalized states ρ , σ \rho,\sigma ρ , σ Φ \Phi Φ P ( Φ ( ρ ) , Φ ( σ ) ) ≤ P ( ρ , σ ) P(\Phi(\rho),\Phi(\sigma)) \le P(\rho,\sigma) P ( Φ ( ρ ) , Φ ( σ )) ≤ P ( ρ , σ )
For subnormalized states, the trace-norm and purified-distance bounds of [47 Lemma 6] imply
1 2 ∥ ρ ~ − ρ ∥ 1 ≤ P ( ρ ~ , ρ ) ≤ 2 ∥ ρ ~ − ρ ∥ 1 . (17) \frac{1}{2}\|\widetilde{\rho}-\rho\|_1 \le P(\widetilde{\rho},\rho) \le\sqrt{2\|\widetilde{\rho}-\rho\|_1}. \tag*{(17)} 2 1 ∥ ρ − ρ ∥ 1 ≤ P ( ρ , ρ ) ≤ 2∥ ρ − ρ ∥ 1 . (17) For a cq state ρ X E \rho_{XE} ρ X E
H min τ ( X ∣ E ) ρ = sup ρ ~ X E : P ( ρ ~ X E , ρ X E ) ≤ τ H min ( X ∣ E ) ρ ~ , (18) H_{\min}^{\tau}(X \mid E)_{\rho} = \sup_{\widetilde{\rho}_{XE}:P(\widetilde{\rho}_{XE},\rho_{XE})\le\tau} H_{\min}(X \mid E)_{\widetilde{\rho}}, \tag*{(18)} H m i n τ ( X ∣ E ) ρ = ρ X E : P ( ρ X E , ρ X E ) ≤ τ sup H m i n ( X ∣ E ) ρ , (18) where the supremum ranges over subnormalized cq states on the same registers. For trace-norm smoothing, we write
H min s , ∥ ⋅ ∥ 1 ( X ∣ E ) ρ = sup ρ ~ X E : ∥ ρ ~ X E − ρ X E ∥ 1 ≤ s H min ( X ∣ E ) ρ ~ , (19) H_{\min}^{s,\|\cdot\|_1}(X \mid E)_{\rho} = \sup_{\widetilde{\rho}_{XE}:\|\widetilde{\rho}_{XE}-\rho_{XE}\|_1\le s} H_{\min}(X \mid E)_{\widetilde{\rho}}, \tag*{(19)} H m i n s , ∥ ⋅ ∥ 1 ( X ∣ E ) ρ = ρ X E : ∥ ρ X E − ρ X E ∥ 1 ≤ s sup H m i n ( X ∣ E ) ρ , (19) with the same convention on ρ ~ X E \widetilde{\rho}_{XE} ρ X E (17) gives
H min 2 s ( X ∣ E ) ρ ≥ H min s , ∥ ⋅ ∥ 1 ( X ∣ E ) ρ . (20) H_{\min}^{\sqrt{2s}}(X \mid E)_{\rho} \ge H_{\min}^{s,\|\cdot\|_1}(X \mid E)_{\rho}. \tag*{(20)} H m i n 2 s ( X ∣ E ) ρ ≥ H m i n s , ∥ ⋅ ∥ 1 ( X ∣ E ) ρ . (20) The next two lemmas are proved in Appendix § 10 .
Lemma 2.1 (Smooth classical leakage; cf. [15 Lemma B.3] ). Let ρ X L E \rho_{XLE} ρ X L E X , L X,L X , L L L L L \mathcal{L} L 0 ≤ τ < 1 0 \le\tau< 1 0 ≤ τ < 1
H min τ ( X ∣ L E ) ρ ≥ H min τ ( X ∣ E ) ρ − log ∣ L ∣ . H_{\min}^{\tau}(X \mid LE)_{\rho} \ge H_{\min}^{\tau}(X \mid E)_{\rho} - \log|\mathcal{L}|. H m i n τ ( X ∣ L E ) ρ ≥ H m i n τ ( X ∣ E ) ρ − log ∣ L ∣. Lemma 2.2 (Extraction from smooth sources; cf. [15 Lemma 3.5] ). Let Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m} Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m ( k , η ) (k,\eta) ( k , η ) τ ≥ 0 \tau\ge0 τ ≥ 0 ρ X E \rho_{XE} ρ X E H min τ ( X ∣ E ) ρ ≥ k + 1 H_{\min}^{\tau}(X \mid E)_{\rho} \ge k+1 H m i n τ ( X ∣ E ) ρ ≥ k + 1 Y ∼ U d Y\sim U_d Y ∼ U d
Δ ( ρ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ E ) ≤ η + 4 τ . \Delta(\rho_{\operatorname{Ext}(X,Y)YE},\tau_m\otimes\tau_d\otimes\rho_E)\le\eta+4\tau. Δ ( ρ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ E ) ≤ η + 4 τ . Two-universal hashing. A family { h w : Z → { 0 , 1 } m } w ∈ W \{h_w : \mathcal{Z} \to\{0,1\}^{m}\}_{w\in\mathcal{W}} { h w : Z → { 0 , 1 } m } w ∈ W two-universal if, for a uniform seed W W W W \mathcal{W} W
Pr W [ h W ( z ) = h W ( z ′ ) ] ≤ 2 − m \Pr_W[h_W(z)=h_W(z')] \le2^{-m} W Pr [ h W ( z ) = h W ( z ′ )] ≤ 2 − m for every distinct z , z ′ ∈ Z z,z'\in\mathcal{Z} z , z ′ ∈ Z
The Quantum Extractor–Matrix Sampler Correspondence
We now prove Theorem 1.5, restated below.
Theorem 1.5 (restated). Let F : { 0 , 1 } n × [ t ] → { 0 , 1 } m F:\{0,1\}^{n}\times[t]\to\{0,1\}^{m} F : { 0 , 1 } n × [ t ] → { 0 , 1 } m D ≥ 1 D\ge1 D ≥ 1 0 < δ , ε < 1 0<\delta,\varepsilon<1 0 < δ , ε < 1
If F F F strong (resp. weak ) log ( 2 D ) \log(2D) log ( 2 D ) ( n − log ( 1 / δ ) , ε / 2 ) (n-\log(1/\delta),\varepsilon/2) ( n − log ( 1/ δ ) , ε /2 ) F F F strong (resp. ordinary ) D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε )
Suppose F F F strong (resp. ordinary ) D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) 0 ≤ a ≤ n 0\le a\le n 0 ≤ a ≤ n F F F strong (resp. weak ) ( log D ) (\log D) ( log D ) ( n − a , ε / 2 + 2 a δ ) (n-a,\varepsilon/2+2^{a}\delta) ( n − a , ε /2 + 2 a δ )
Proof of Theorem 1.5. For part (1), for every i ∈ [ t ] i\in[t] i ∈ [ t ] f i : { 0 , 1 } m → C D × D f_i:\{0,1\}^{m}\to\mathbb{C}^{D\times D} f i : { 0 , 1 } m → C D × D ∥ f i ( z ) ∥ ≤ 1 \lVert f_i(z)\rVert\le1 ∥ f i ( z )∥ ≤ 1 x ∈ { 0 , 1 } n x\in\{0,1\}^{n} x ∈ { 0 , 1 } n
A x = 1 t ∑ i = 1 t ( f i ( F ( x , i ) ) − E Z ∼ U m f i ( Z ) ) . (21) A_x=\frac{1}{t}\sum_{i=1}^{t}\left(f_i(F(x,i))-\mathbb{E}_{Z\sim U_m}f_i(Z)\right). \tag*{(21)} A x = t 1 i = 1 ∑ t ( f i ( F ( x , i )) − E Z ∼ U m f i ( Z ) ) . (21) Suppose B = { x : ∥ A x ∥ > ε } \mathcal{B}=\{x:\lVert A_x\rVert>\varepsilon\} B = { x : ∥ A x ∥ > ε } δ 2 n \delta2^n δ 2 n x ∈ B x\in\mathcal{B} x ∈ B H ( A x ) \mathcal{H}(A_x) H ( A x ) ∥ A x ∥ > ε \lVert A_x\rVert>\varepsilon ∥ A x ∥ > ε v x v_x v x X X X B \mathcal{B} B ρ X E = ∣ B ∣ − 1 ∑ x ∈ B ∣ x ⟩ ⟨ x ∣ ⊗ ∣ v x ⟩ ⟨ v x ∣ \rho_{XE}=|\mathcal{B}|^{-1}\sum_{x\in\mathcal{B}}|x\rangle\langle x|\otimes|v_x\rangle\langle v_x| ρ X E = ∣ B ∣ − 1 ∑ x ∈ B ∣ x ⟩ ⟨ x ∣ ⊗ ∣ v x ⟩ ⟨ v x ∣ E E E 2 D 2D 2 D x ↦ ∣ v x ⟩ ⟨ v x ∣ x\mapsto|v_x\rangle\langle v_x| x ↦ ∣ v x ⟩ ⟨ v x ∣ i i i X X X
H ∞ ( X ) = log ∣ B ∣ > n − log ( 1 / δ ) . H_\infty(X)=\log|\mathcal{B}|>n-\log(1/\delta). H ∞ ( X ) = log ∣ B ∣ > n − log ( 1/ δ ) . Let I I I [ t ] [t] [ t ] X E XE X E z ∈ { 0 , 1 } m z\in\{0,1\}^{m} z ∈ { 0 , 1 } m H ( f i ( z ) ) \mathcal{H}(f_i(z)) H ( f i ( z ))
M i , z : = ( I 2 D + H ( f i ( z ) ) ) / 2 , ∀ i ∈ [ t ] , z ∈ { 0 , 1 } m . (22) M_{i,z}:=(I_{2D}+\mathcal{H}(f_i(z)))/2,\qquad\forall i\in[t],\ z\in\{0,1\}^{m}. \tag*{(22)} M i , z := ( I 2 D + H ( f i ( z ))) /2 , ∀ i ∈ [ t ] , z ∈ { 0 , 1 } m . (22) This satisfies $0\preceq M_{i,z}\preceq I_{2D}f o r e v e r y for every f or e v er y
Define the measurement operator
M : = ∑ z ∈ { 0 , 1 } m ∑ i = 1 t ∣ z ⟩ ⟨ z ∣ ⊗ ∣ i ⟩ ⟨ i ∣ ⊗ M i , z . M:=\sum_{z\in\{0,1\}^{m}}\sum_{i=1}^{t}|z\rangle\langle z|\otimes|i\rangle\langle i|\otimes M_{i,z}. M := z ∈ { 0 , 1 } m ∑ i = 1 ∑ t ∣ z ⟩ ⟨ z ∣ ⊗ ∣ i ⟩ ⟨ i ∣ ⊗ M i , z . Since 0 ⪯ M i , z ⪯ I E 0\preceq M_{i,z}\preceq I_E 0 ⪯ M i , z ⪯ I E i , z i,z i , z { M , I − M } \{M,I-M\} { M , I − M } M M M ρ F ( X , I ) I E \rho_{F(X,I)IE} ρ F ( X , I ) I E τ m ⊗ ρ I E \tau_m\otimes\rho_{IE} τ m ⊗ ρ I E
Tr [ M ( ρ F ( X , I ) I E − τ m ⊗ ρ I E ) ] = E X 1 t ∑ i = 1 t ⟨ v X , ( M i , F ( X , i ) − E Z ∼ U m M i , Z ) v X ⟩ = 1 2 E X ⟨ v X , H ( A X ) v X ⟩ = 1 2 E X ∥ A X ∥ > ε / 2. \begin{aligned}
\operatorname{Tr}\left[M\left(\rho_{F(X,I)IE}-\tau_m\otimes\rho_{IE}\right)\right]
&=\mathbb{E}_X\frac{1}{t}\sum_{i=1}^{t}\langle v_X,(M_{i,F(X,i)}-\mathbb{E}_{Z\sim U_m}M_{i,Z})v_X\rangle\\
&=\frac{1}{2}\mathbb{E}_X\langle v_X,\mathcal{H}(A_X)v_X\rangle
=\frac{1}{2}\mathbb{E}_X\lVert A_X\rVert>\varepsilon/2.
\end{aligned} Tr [ M ( ρ F ( X , I ) I E − τ m ⊗ ρ I E ) ] = E X t 1 i = 1 ∑ t ⟨ v X , ( M i , F ( X , i ) − E Z ∼ U m M i , Z ) v X ⟩ = 2 1 E X ⟨ v X , H ( A X ) v X ⟩ = 2 1 E X ∥ A X ∥ > ε /2. The second equality follows from (22) and (21) , the third from the choice of v x v_x v x X X X B \mathcal{B} B (14) ,
Δ ( ρ F ( X , I ) I E , τ m ⊗ ρ I E ) ≥ Tr [ M ( ρ F ( X , I ) I E − τ m ⊗ ρ I E ) ] > ε / 2. \Delta(\rho_{F(X,I)IE},\tau_m\otimes\rho_{IE})\geq\operatorname{Tr}\left[M\left(\rho_{F(X,I)IE}-\tau_m\otimes\rho_{IE}\right)\right]>\varepsilon/2. Δ ( ρ F ( X , I ) I E , τ m ⊗ ρ I E ) ≥ Tr [ M ( ρ F ( X , I ) I E − τ m ⊗ ρ I E ) ] > ε /2. contradicting the extractor guarantee Δ ( ρ F ( X , I ) I E , τ m ⊗ ρ I E ) ≤ ε / 2 \Delta(\rho_{F(X,I)IE},\tau_m\otimes\rho_{IE})\leq\varepsilon/2 Δ ( ρ F ( X , I ) I E , τ m ⊗ ρ I E ) ≤ ε /2
For the weak extractor and ordinary sampler case of part (1), notice that if f 1 = ⋯ = f t f_1=\cdots=f_t f 1 = ⋯ = f t M i , z = M z M_{i,z}=M_z M i , z = M z i i i { M ′ , I − M ′ } \{M',I-M'\} { M ′ , I − M ′ } ρ F ( X , I ) E \rho_{F(X,I)E} ρ F ( X , I ) E τ m ⊗ ρ E \tau_m\otimes\rho_E τ m ⊗ ρ E
M ′ : = ∑ z ∈ { 0 , 1 } m ∣ z ⟩ ⟨ z ∣ ⊗ M z . M' := \sum_{z\in\{0,1\}^m}|z\rangle\langle z|\otimes M_z. M ′ := z ∈ { 0 , 1 } m ∑ ∣ z ⟩ ⟨ z ∣ ⊗ M z . This measurement distinguishes ρ F ( X , I ) E \rho_{F(X,I)E} ρ F ( X , I ) E τ m ⊗ ρ E \tau_m\otimes\rho_E τ m ⊗ ρ E ε / 2 \varepsilon/2 ε /2 Δ ( ρ F ( X , I ) E , τ m ⊗ ρ E ) ≤ ε / 2 \Delta(\rho_{F(X,I)E},\tau_m\otimes\rho_E)\leq\varepsilon/2 Δ ( ρ F ( X , I ) E , τ m ⊗ ρ E ) ≤ ε /2
For part (2), consider a cq state with H ∞ ( X ) ≥ n − a H_\infty(X)\geq n-a H ∞ ( X ) ≥ n − a dim E ≤ D \dim E\leq D dim E ≤ D E E E D D D ρ X E = ∑ x p x ∣ x ⟩ ⟨ x ∣ ⊗ ρ x \rho_{XE}=\sum_x p_x|x\rangle\langle x|\otimes\rho_x ρ X E = ∑ x p x ∣ x ⟩ ⟨ x ∣ ⊗ ρ x p x p_x p x Pr [ X = x ] ≤ 2 a − n \Pr[X=x]\leq2^{a-n} Pr [ X = x ] ≤ 2 a − n { M , I 2 m ⊗ I t ⊗ I D − M } \{M,I_{2^m}\otimes I_t\otimes I_D-M\} { M , I 2 m ⊗ I t ⊗ I D − M } ρ F ( X , I ) I E \rho_{F(X,I)IE} ρ F ( X , I ) I E τ m ⊗ ρ I E \tau_m\otimes\rho_{IE} τ m ⊗ ρ I E
M = ∑ z ∈ { 0 , 1 } m ∑ i = 1 t ∣ z ⟩ ⟨ z ∣ ⊗ ∣ i ⟩ ⟨ i ∣ ⊗ M i , z , 0 ⪯ M i , z ⪯ I E . M=\sum_{z\in\{0,1\}^m}\sum_{i=1}^{t}|z\rangle\langle z|\otimes|i\rangle\langle i|\otimes M_{i,z},\qquad0\preceq M_{i,z}\preceq I_E. M = z ∈ { 0 , 1 } m ∑ i = 1 ∑ t ∣ z ⟩ ⟨ z ∣ ⊗ ∣ i ⟩ ⟨ i ∣ ⊗ M i , z , 0 ⪯ M i , z ⪯ I E . We define acceptance of the measure to be the case when the outcome corresponds to M M M
Set f i ( z ) = 2 M i , z − I f_i(z)=2M_{i,z}-I f i ( z ) = 2 M i , z − I f i ( z ) f_i(z) f i ( z ) ∥ f i ( z ) ∥ ≤ 1 \lVert f_i(z)\rVert\leq1 ∥ f i ( z )∥ ≤ 1 f 1 , … , f t f_1,\ldots,f_t f 1 , … , f t x ∈ { 0 , 1 } n x\in\{0,1\}^n x ∈ { 0 , 1 } n
B x : = 1 t ∑ i = 1 t ( M i , F ( x , i ) − E Z ∼ U m M i , Z ) . B_x:=\frac{1}{t}\sum_{i=1}^{t}\left(M_{i,F(x,i)}-\mathbb{E}_{Z\sim U_m}M_{i,Z}\right). B x := t 1 i = 1 ∑ t ( M i , F ( x , i ) − E Z ∼ U m M i , Z ) . Define B = { x ∈ { 0 , 1 } n : ∥ B x ∥ > ε / 2 } \mathcal{B}=\{x\in\{0,1\}^n:\lVert B_x\rVert>\varepsilon/2\} B = { x ∈ { 0 , 1 } n : ∥ B x ∥ > ε /2 } ∣ B ∣ ≤ δ 2 n |\mathcal{B}|\leq\delta2^n ∣ B ∣ ≤ δ 2 n B x B_x B x I I I − I ⪯ B x ⪯ I -I\preceq B_x\preceq I − I ⪯ B x ⪯ I x x x
Pr [ X ∈ B ] = ∑ x ∈ B p x ≤ 2 a − n ∣ B ∣ ≤ 2 a δ . \Pr[X\in\mathcal{B}]=\sum_{x\in\mathcal{B}}p_x\leq2^{a-n}|\mathcal{B}|\leq2^a\delta. Pr [ X ∈ B ] = x ∈ B ∑ p x ≤ 2 a − n ∣ B ∣ ≤ 2 a δ . The difference of acceptance probabilities for measuring ρ F ( X , I ) I E \rho_{F(X,I)IE} ρ F ( X , I ) I E τ m ⊗ ρ I E \tau_m\otimes\rho_{IE} τ m ⊗ ρ I E
Tr [ M ( ρ F ( X , I ) I E − τ m ⊗ ρ I E ) ] = ∑ x p x 1 t ∑ i = 1 t ( Tr ( ρ x M i , F ( x , i ) ) − E Z ∼ U m Tr ( ρ x M i , Z ) ) = ∑ x p x Tr ( ρ x B x ) , \begin{aligned}
\operatorname{Tr}\left[M\left(\rho_{F(X,I)IE}-\tau_m\otimes\rho_{IE}\right)\right] \\
&=\sum_x p_x\frac{1}{t}\sum_{i=1}^{t}\left(\operatorname{Tr}(\rho_xM_{i,F(x,i)})-\mathbb{E}_{Z\sim U_m}\operatorname{Tr}(\rho_xM_{i,Z})\right) \\
&=\sum_x p_x\operatorname{Tr}(\rho_xB_x),
\end{aligned} Tr [ M ( ρ F ( X , I ) I E − τ m ⊗ ρ I E ) ] = x ∑ p x t 1 i = 1 ∑ t ( Tr ( ρ x M i , F ( x , i ) ) − E Z ∼ U m Tr ( ρ x M i , Z ) ) = x ∑ p x Tr ( ρ x B x ) , where the first equality follows from the block-diagonal form of M M M B x B_x B x
The absolute difference in acceptance probabilities is therefore
∣ ∑ x p x Tr ( ρ x B x ) ∣ ≤ ∑ x ∉ B p x ∥ B x ∥ + ∑ x ∈ B p x ∥ B x ∥ ≤ ε 2 Pr [ X ∉ B ] + Pr [ X ∈ B ] ≤ ε 2 + 2 a δ . \begin{aligned}
\left|\sum_xp_x\operatorname{Tr}(\rho_xB_x)\right|
\leq\sum_{x\notin\mathcal{B}}p_x\lVert B_x\rVert+\sum_{x\in\mathcal{B}}p_x\lVert B_x\rVert\\
&\leq\frac{\varepsilon}{2}\Pr[X\notin\mathcal{B}]+\Pr[X\in\mathcal{B}]
\leq\frac{\varepsilon}{2}+2^a\delta.
\end{aligned} x ∑ p x Tr ( ρ x B x ) ≤ x ∈ / B ∑ p x ∥ B x ∥ + x ∈ B ∑ p x ∥ B x ∥ ≤ 2 ε Pr [ X ∈ / B ] + Pr [ X ∈ B ] ≤ 2 ε + 2 a δ . Since this holds for all measurements M M M
For weak extractors, consider a binary POVM { M , I 2 m ⊗ I D − M } \{M, I_{2^m} \otimes I_D - M\} { M , I 2 m ⊗ I D − M }
M = ∑ z ∈ { 0 , 1 } m ∣ z ⟩ ⟨ z ∣ ⊗ M z . M = \sum_{z \in\{0,1\}^m} |z\rangle\langle z| \otimes M_z. M = z ∈ { 0 , 1 } m ∑ ∣ z ⟩ ⟨ z ∣ ⊗ M z . Set f ( z ) = 2 M z − I E f(z) = 2M_z - I_E f ( z ) = 2 M z − I E f f f ρ F ( X , I ) E \rho_{F(X,I)E} ρ F ( X , I ) E τ m ⊗ ρ E \tau_m \otimes\rho_E τ m ⊗ ρ E
Corollary 3.1. Let F : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m F : \{0,1\}^n \times\{0,1\}^d \to\{0,1\}^m F : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m ( k , η ) (k,\eta) ( k , η ) F F F D D D ( δ , ϵ ) (\delta,\epsilon) ( δ , ϵ )
k ≤ n − log ( 2 D / δ ) , η ≤ ϵ / 2. (23) k \le n - \log(2D/\delta), \qquad\eta\le\epsilon/2. \tag*{(23)} k ≤ n − log ( 2 D / δ ) , η ≤ ϵ /2. (23) The sampler uses r = n r = n r = n t = 2 d t = 2^d t = 2 d
Proof. Let ρ X E \rho_{XE} ρ X E H ∞ ( X ) ρ ≥ n − log ( 1 / δ ) H_\infty(X)_\rho\ge n - \log(1/\delta) H ∞ ( X ) ρ ≥ n − log ( 1/ δ ) dim E ≤ 2 D \dim E \le2D dim E ≤ 2 D (15) ,
H min ( X ∣ E ) ρ ≥ H ∞ ( X ) − log dim E ≥ n − log ( 2 D / δ ) ≥ k . H_{\min}(X \mid E)_\rho\ge H_\infty(X) - \log\dim E \ge n - \log(2D/\delta) \ge k. H m i n ( X ∣ E ) ρ ≥ H ∞ ( X ) − log dim E ≥ n − log ( 2 D / δ ) ≥ k . Thus F F F ( log 2 D ) (\log2D) ( log 2 D ) ( n − log ( 1 / δ ) , ϵ / 2 ) (n - \log(1/\delta), \epsilon/2) ( n − log ( 1/ δ ) , ϵ /2 )
A Quantum-Proof Extractor with Linear Output
Fix a constant conditional min-entropy rate μ > 0 \mu> 0 μ > 0 h = log ( n / η ) h = \log(n/\eta) h = log ( n / η ) h h h n n n O μ ( h log 2 ( n / h ) ) O_\mu(h \log^2(n/h)) O μ ( h log 2 ( n / h ))
Collision bounds and hashing
We combine the collision bound of Tomamichel et al. [51 Lemma 5] with the quantum leftover hash lemma [37 Theorem 5.5.1] .
Lemma 4.1. Let F : X × Y → Z F : \mathcal{X} \times\mathcal{Y} \to\mathcal{Z} F : X × Y → Z
Pr Y ∼ U Y [ F ( x , Y ) = F ( x ′ , Y ) ] ≤ ξ for all distinct x , x ′ ∈ X . \Pr_{Y \sim U_Y}[F(x,Y) = F(x',Y)] \le\xi\qquad\text{for all distinct } x,x' \in\mathcal{X}. Y ∼ U Y Pr [ F ( x , Y ) = F ( x ′ , Y )] ≤ ξ for all distinct x , x ′ ∈ X . Let k k k η > 0 \eta> 0 η > 0 { h w : Z → { 0 , 1 } m } w ∈ W \{h_w : \mathcal{Z} \to\{0,1\}^m\}_{w \in\mathcal{W}} { h w : Z → { 0 , 1 } m } w ∈ W
1 2 2 m ( 2 − k + ξ ) ≤ η . (24) \frac{1}{2}\sqrt{2^m(2^{-k}+\xi)} \le\eta. \tag*{(24)} 2 1 2 m ( 2 − k + ξ ) ≤ η . (24) Then Ext : X × ( Y × W ) → { 0 , 1 } m \operatorname{Ext} : \mathcal{X} \times(\mathcal{Y} \times\mathcal{W}) \to\{0,1\}^m Ext : X × ( Y × W ) → { 0 , 1 } m Ext ( x ; y , w ) = h w ( F ( x , y ) ) \operatorname{Ext}(x;y,w) = h_w(F(x,y)) Ext ( x ; y , w ) = h w ( F ( x , y )) ( k , η ) (k,\eta) ( k , η ) Y × W \mathcal{Y} \times\mathcal{W} Y × W
Proof. For a normalized cq state ω A E = ∑ a ∣ a ⟩ ⟨ a ∣ ⊗ ω E a \omega_{AE} = \sum_a |a\rangle\langle a| \otimes\omega_E^a ω A E = ∑ a ∣ a ⟩ ⟨ a ∣ ⊗ ω E a
cp ( A ∣ E ) ω : = ∑ a Tr ( ω E a ω E − 1 / 2 ω E a ω E − 1 / 2 ) , ω E = ∑ a ω E a . \operatorname{cp}(A \mid E)_\omega:= \sum_a \operatorname{Tr}\left(\omega_E^{a}\omega_E^{-1/2}\omega_E^{a}\omega_E^{-1/2}\right), \qquad\omega_E = \sum_a \omega_E^a. cp ( A ∣ E ) ω := a ∑ Tr ( ω E a ω E − 1/2 ω E a ω E − 1/2 ) , ω E = a ∑ ω E a . where, if ω E = ∑ j λ j ∣ e j ⟩ ⟨ e j ∣ \omega_E = \sum_j \lambda_j |e_j\rangle\langle e_j| ω E = ∑ j λ j ∣ e j ⟩ ⟨ e j ∣
ω E − 1 / 2 : = ∑ j : λ j > 0 λ j − 1 / 2 ∣ e j ⟩ ⟨ e j ∣ . \omega_E^{-1/2} := \sum_{j:\lambda_j>0} \lambda_j^{-1/2}|e_j\rangle\langle e_j|. ω E − 1/2 := j : λ j > 0 ∑ λ j − 1/2 ∣ e j ⟩ ⟨ e j ∣. The operators
{ M a : = ω E − 1 / 2 ω E a ω E − 1 / 2 } a ∈ A \left\{M_a := \omega_E^{-1/2}\omega_E^a\omega_E^{-1/2}\right\}_{a\in\mathcal{A}} { M a := ω E − 1/2 ω E a ω E − 1/2 } a ∈ A form a POVM, where A \mathcal{A} A A A A A A A ∑ a Tr ( M a ω E a ) = cp ( A ∣ E ) ω \sum_a \operatorname{Tr}(M_a\omega_E^a) = \operatorname{cp}(A \mid E)_\omega ∑ a Tr ( M a ω E a ) = cp ( A ∣ E ) ω cp ( A ∣ E ) ω ≤ p g u e s s ( A ∣ E ) ω \operatorname{cp}(A \mid E)_\omega\leq p_{\mathrm{guess}}(A \mid E)_\omega cp ( A ∣ E ) ω ≤ p guess ( A ∣ E ) ω p g u e s s p_{\mathrm{guess}} p guess (12) .
Fix a source ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ≥ k H_{\min}(X \mid E) \geq k H m i n ( X ∣ E ) ≥ k Z = F ( X , Y ) Z = F(X,Y) Z = F ( X , Y ) Y Y Y [51 Lemma 5, Eq. (17)] gives
cp ( Z ∣ Y E ) ρ ≤ cp ( X ∣ E ) ρ + ξ ≤ 2 − k + ξ . \operatorname{cp}(Z \mid YE)_\rho\leq\operatorname{cp}(X \mid E)_\rho+ \xi\leq2^{-k} + \xi. cp ( Z ∣ Y E ) ρ ≤ cp ( X ∣ E ) ρ + ξ ≤ 2 − k + ξ . The quantum leftover hash lemma in collision form [37 Theorem 5.5.1] , with side information Y E YE Y E W W W
Δ ( ρ h W ( Z ) W Y E , τ m ⊗ ρ W ⊗ ρ Y E ) ≤ 1 2 2 m cp ( Z ∣ Y E ) ρ ≤ 1 2 2 m ( 2 − k + ξ ) . \Delta(\rho_{h_W(Z)WYE}, \tau_m \otimes\rho_W \otimes\rho_{YE}) \leq\frac{1}{2}\sqrt{2^m\operatorname{cp}(Z \mid YE)_\rho} \leq\frac{1}{2}\sqrt{2^m(2^{-k}+\xi)}. Δ ( ρ h W ( Z ) W Y E , τ m ⊗ ρ W ⊗ ρ Y E ) ≤ 2 1 2 m cp ( Z ∣ Y E ) ρ ≤ 2 1 2 m ( 2 − k + ξ ) . Multilinear evaluations and weak designs
We adapt the extractor construction of Raz, Reingold, and Vadhan [39 ] to sources with quantum side information.
Definition 4.2 (Weak design). A family S 1 , … , S M ⊆ [ v ] S_1,\ldots,S_M \subseteq[v] S 1 , … , S M ⊆ [ v ] ( ℓ , ϱ ) (\ell,\varrho) ( ℓ , ϱ ) ∣ S i ∣ = ℓ |S_i|=\ell ∣ S i ∣ = ℓ i i i ∑ j < i 2 ∣ S i ∩ S j ∣ ≤ ϱ M \sum_{j<i}2^{|S_i\cap S_j|}\leq\varrho M ∑ j < i 2 ∣ S i ∩ S j ∣ ≤ ϱM i i i
Theorem 4.3 ([39 Lemma 15] ). For every ϱ > 1 \varrho>1 ϱ > 1
v = O ( ℓ + ℓ 2 log ϱ ) . (25) v = O\left(\ell+\frac{\ell^2}{\log\varrho}\right). \tag*{(25)} v = O ( ℓ + log ϱ ℓ 2 ) . (25) The design can be constructed in time polynomial in M M M
Theorem 4.4. Let n , λ , ℓ , M , m 0 ≥ 1 n,\lambda,\ell,M,m_0\geq1 n , λ , ℓ , M , m 0 ≥ 1 n ≤ λ 2 ℓ n\leq\lambda2^\ell n ≤ λ 2 ℓ m 0 ≤ λ m_0\leq\lambda m 0 ≤ λ S 1 , … , S M ⊆ [ v ] S_1,\ldots,S_M\subseteq[v] S 1 , … , S M ⊆ [ v ] ( ℓ , ϱ ) (\ell,\varrho) ( ℓ , ϱ ) 0 ≤ k ≤ n 0\leq k\leq n 0 ≤ k ≤ n η > 0 \eta>0 η > 0
M 2 2 m 0 ( 2 λ ϱ M − k + ℓ 2 − λ ) ≤ η , (26) \frac{M}{2}\sqrt{2^{m_0}(2^{\lambda\varrho M-k}+\ell2^{-\lambda})}\leq\eta, \tag*{(26)} 2 M 2 m 0 ( 2 λ ϱM − k + ℓ 2 − λ ) ≤ η , (26) there is a strong quantum-proof ( k , η ) (k,\eta) ( k , η ) Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m d = λ ( v + 1 ) d=\lambda(v+1) d = λ ( v + 1 ) m = M m 0 m=Mm_0 m = M m 0
Proof. Fix a binary basis of F 2 λ \mathbb{F}_{2^\lambda} F 2 λ x ∈ { 0 , 1 } n x\in\{0,1\}^n x ∈ { 0 , 1 } n
Polynomial encoding. Pad x x x λ 2 ℓ \lambda2^\ell λ 2 ℓ 2 ℓ 2^\ell 2 ℓ λ \lambda λ I ⊆ [ ℓ ] I \subseteq[\ell] I ⊆ [ ℓ ] a I ( x ) a_I(x) a I ( x )
p x ( z 1 , … , z ℓ ) = ∑ I ⊆ [ ℓ ] a I ( x ) ∏ j ∈ I z j ∈ F 2 λ [ z 1 , … , z ℓ ] . p_x(z_1,\ldots,z_\ell)=\sum_{I\subseteq[\ell]}a_I(x)\prod_{j\in I}z_j\in\mathbb{F}_{2^\lambda}[z_1,\ldots,z_\ell]. p x ( z 1 , … , z ℓ ) = I ⊆ [ ℓ ] ∑ a I ( x ) j ∈ I ∏ z j ∈ F 2 λ [ z 1 , … , z ℓ ] . Distinct strings x x x p x p_x p x
Generating the seed. Let ( Y , W ) (Y,W) ( Y , W ) F 2 λ × F 2 λ \mathbb{F}_{2^\lambda}\times\mathbb{F}_{2^\lambda} F 2 λ × F 2 λ i i i Y ∣ S i ∈ F 2 λ ℓ Y|_{S_i}\in\mathbb{F}_{2^\lambda}^{\ell} Y ∣ S i ∈ F 2 λ ℓ S i S_i S i ( Y , W ) (Y,W) ( Y , W )
Evaluation and hashing. Fix a linear projection π m 0 : F 2 λ → { 0 , 1 } m 0 \pi_{m_0}:\mathbb{F}_{2^\lambda}\to\{0,1\}^{m_0} π m 0 : F 2 λ → { 0 , 1 } m 0 m 0 m_0 m 0 i i i p x p_x p x Y ∣ S i Y|_{S_i} Y ∣ S i W W W π m 0 \pi_{m_0} π m 0
Ext ( x ; Y , W ) = ( π m 0 ( W p x ( Y ∣ S 1 ) ) , … , π m 0 ( W p x ( Y ∣ S M ) ) ) . \operatorname{Ext}(x;Y,W)=\left(\pi_{m_0}(Wp_x(Y|_{S_1})),\ldots,\pi_{m_0}(Wp_x(Y|_{S_M}))\right). Ext ( x ; Y , W ) = ( π m 0 ( W p x ( Y ∣ S 1 )) , … , π m 0 ( W p x ( Y ∣ S M )) ) . Fix a normalized cq source ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ρ ≥ k H_{\min}(X\mid E)_\rho\ge k H m i n ( X ∣ E ) ρ ≥ k ρ X E \rho_{XE} ρ X E ( Y , W ) (Y,W) ( Y , W ) Z = ( Z 1 , … , Z M ) Z=(Z_1,\ldots,Z_M) Z = ( Z 1 , … , Z M ) ρ \rho ρ
Z i = π m 0 ( W p X ( Y ∣ S i ) ) . Z_i=\pi_{m_0}(Wp_X(Y|_{S_i})). Z i = π m 0 ( W p X ( Y ∣ S i )) . Write Z ≤ i = ( Z 1 , … , Z i ) Z_{\le i}=(Z_1,\ldots,Z_i) Z ≤ i = ( Z 1 , … , Z i ) Z < i = ( Z 1 , … , Z i − 1 ) Z_{<i}=(Z_1,\ldots,Z_{i-1}) Z < i = ( Z 1 , … , Z i − 1 ) Z ≤ 0 Z_{\le0} Z ≤ 0 Z < 1 Z_{<1} Z < 1
ε 0 = 1 2 2 m 0 ( 2 λ M − k + ℓ 2 − λ ) . \varepsilon_0=\frac{1}{2}\sqrt{2^{m_0}\left(2^{\lambda M-k}+\ell2^{-\lambda}\right)}. ε 0 = 2 1 2 m 0 ( 2 λ M − k + ℓ 2 − λ ) . Hybrid states. For 0 ≤ i ≤ M 0\le i\le M 0 ≤ i ≤ M Z i + 1 , … , Z M Z_{i+1},\ldots,Z_M Z i + 1 , … , Z M
ρ Z Y W E ( i ) = ρ Z ≤ i Y W E ⊗ τ m 0 ⊗ ( M − i ) . \rho^{(i)}_{Z Y W E}=\rho_{Z_{\le i}Y W E}\otimes\tau_{m_0}^{\otimes(M-i)}. ρ Z Y W E ( i ) = ρ Z ≤ i Y W E ⊗ τ m 0 ⊗ ( M − i ) . We abbreviate ρ Z Y W E ( i ) \rho^{(i)}_{Z Y W E} ρ Z Y W E ( i ) ρ ( i ) \rho^{(i)} ρ ( i )
ρ Z Y W E ( 0 ) = τ m ⊗ ρ Y W E , ρ Z Y W E ( M ) = ρ Z Y W E . \rho^{(0)}_{Z Y W E}=\tau_m\otimes\rho_{Y W E},\qquad\rho^{(M)}_{Z Y W E}=\rho_{Z Y W E}. ρ Z Y W E ( 0 ) = τ m ⊗ ρ Y W E , ρ Z Y W E ( M ) = ρ Z Y W E . For 1 ≤ i ≤ M 1\le i\le M 1 ≤ i ≤ M ρ ( i ) \rho^{(i)} ρ ( i ) ρ ( i − 1 ) \rho^{(i-1)} ρ ( i − 1 ) ( Z i + 1 , … , Z M ) (Z_{i+1},\ldots,Z_M) ( Z i + 1 , … , Z M ) ( Z i + 1 , … , Z M ) (Z_{i+1},\ldots,Z_M) ( Z i + 1 , … , Z M ) ρ ( i ) \rho^{(i)} ρ ( i ) ρ ( i − 1 ) \rho^{(i-1)} ρ ( i − 1 )
Δ ( ρ ( i ) , ρ ( i − 1 ) ) = Δ ( ρ Z i Z < i Y W E , τ m 0 ⊗ ρ Z < i Y W E ) . \Delta\left(\rho^{(i)},\rho^{(i-1)}\right)=\Delta\left(\rho_{Z_iZ_{<i}YWE},\tau_{m_0}\otimes\rho_{Z_{<i}YWE}\right). Δ ( ρ ( i ) , ρ ( i − 1 ) ) = Δ ( ρ Z i Z < i Y W E , τ m 0 ⊗ ρ Z < i Y W E ) . We will prove Δ ( ρ ( i ) , ρ ( i − 1 ) ) ≤ ε 0 \Delta(\rho^{(i)},\rho^{(i-1)})\le\varepsilon_0 Δ ( ρ ( i ) , ρ ( i − 1 ) ) ≤ ε 0 i ∈ [ M ] i\in[M] i ∈ [ M ]
Distance between consecutive hybrids. Fix i i i Y Y Y Y i n = Y ∣ S i Y_{\mathrm{in}}=Y|_{S_i} Y in = Y ∣ S i Y o u t = Y ∣ [ ℓ ] ∖ S i Y_{\mathrm{out}}=Y|_{[\ell]\setminus S_i} Y out = Y ∣ [ ℓ ] ∖ S i y o u t y_{\mathrm{out}} y out
σ X E Y W : = ρ X E Y W ∣ Y o u t = y o u t . \sigma_{XEYW}:=\left.\rho_{XEYW}\right|_{Y_{\mathrm{out}}=y_{\mathrm{out}}}. σ X E Y W := ρ X E Y W ∣ Y out = y out . Conditioning on Y o u t = y o u t Y_{\mathrm{out}}=y_{\mathrm{out}} Y out = y out X E XE X E σ X E = ρ X E \sigma_{XE}=\rho_{XE} σ X E = ρ X E Y i n , W Y_{\mathrm{in}},W Y in , W σ X E \sigma_{XE} σ X E
For each j < i j<i j < i Y o u t Y_{\mathrm{out}} Y out Y ∣ S j Y|_{S_j} Y ∣ S j S i ∩ S j S_i\cap S_j S i ∩ S j p X ( Y ∣ S j ) p_X(Y|_{S_j}) p X ( Y ∣ S j ) q j q_j q j Y ∣ S i ∩ S j Y|_{S_i\cap S_j} Y ∣ S i ∩ S j A i A_i A i q j q_j q j j < i j<i j < i 2 ∣ S i ∩ S j ∣ 2^{|S_i\cap S_j|} 2 ∣ S i ∩ S j ∣ j j j λ \lambda λ A i A_i A i λ ∑ j < i 2 ∣ S i ∩ S j ∣ ≤ λ ϱ M \lambda\sum_{j<i} 2^{|S_i\cap S_j|} \le\lambda\varrho M λ ∑ j < i 2 ∣ S i ∩ S j ∣ ≤ λ ϱM (15) gives
H min ( X ∣ A i E ) σ ≥ k − λ ϱ M . H_{\min}(X \mid A_iE)_\sigma\ge k-\lambda\varrho M. H m i n ( X ∣ A i E ) σ ≥ k − λ ϱM . The advice A i A_i A i X X X y o u t y_{\mathrm{out}} y out Y i n Y_{\mathrm{in}} Y in W W W X A i E XA_iE X A i E σ \sigma σ
Define
F : { 0 , 1 } n × F 2 λ ℓ → F 2 λ , F ( x , u ) = p x ( u ) . F:\{0,1\}^{n}\times\mathbb{F}_{2^\lambda}^{\ell}\to\mathbb{F}_{2^\lambda},\qquad F(x,u)=p_x(u). F : { 0 , 1 } n × F 2 λ ℓ → F 2 λ , F ( x , u ) = p x ( u ) . For x ≠ x ′ x\ne x' x = x ′ p x − p x ′ p_x-p_{x'} p x − p x ′ ℓ \ell ℓ u ∈ F 2 λ u\in\mathbb{F}_{2^\lambda} u ∈ F 2 λ
Pr u [ F ( x , u ) = F ( x ′ , u ) ] ≤ ℓ 2 − λ . \Pr_u[F(x,u)=F(x',u)]\le\ell2^{-\lambda}. u Pr [ F ( x , u ) = F ( x ′ , u )] ≤ ℓ 2 − λ . Define the hash family h w ( z ) : = π m 0 ( w z ) h_w(z):=\pi_{m_0}(wz) h w ( z ) := π m 0 ( w z ) z ≠ z ′ z\ne z' z = z ′ W ( z − z ′ ) W(z-z') W ( z − z ′ ) F 2 λ \mathbb{F}_{2^\lambda} F 2 λ π m 0 ( W ( z − z ′ ) ) \pi_{m_0}(W(z-z')) π m 0 ( W ( z − z ′ )) 2 − m 0 2^{-m_0} 2 − m 0 { h w } \{h_w\} { h w }
Apply Lemma 4.1 to Z i = h W ( F ( X , Y i n ) ) Z_i=h_W(F(X,Y_{\mathrm{in}})) Z i = h W ( F ( X , Y in )) X X X Y i n Y_{\mathrm{in}} Y in W W W A i E A_iE A i E H min ( X ∣ A i E ) σ ≥ k − λ ϱ M H_{\min}(X\mid A_iE)_\sigma\ge k-\lambda\varrho M H m i n ( X ∣ A i E ) σ ≥ k − λ ϱM m 0 m_0 m 0 ξ : = ℓ 2 − λ \xi:=\ell2^{-\lambda} ξ := ℓ 2 − λ Lemma 4.1 gives
Δ ( σ Z i A i Y W E , τ m 0 ⊗ σ A i Y W E ) ≤ ϵ 0 . \Delta(\sigma_{Z_iA_iY W E},\tau_{m_0}\otimes\sigma_{A_iY W E})\le\epsilon_0. Δ ( σ Z i A i Y W E , τ m 0 ⊗ σ A i Y W E ) ≤ ϵ 0 . For each j < i j<i j < i
q j ( Y ∣ S i ∩ S j ) = p X ( Y ∣ S j ) . q_j(Y\mid S_i\cap S_j)=p_X(Y\mid S_j). q j ( Y ∣ S i ∩ S j ) = p X ( Y ∣ S j ) . Recall that A i A_i A i q j q_j q j j < i j<i j < i A i , Y , W A_i,Y,W A i , Y , W Z j Z_j Z j j < i j<i j < i
Z j = π m 0 ( W q j ( Y ∣ S i ∩ S j ) ) . Z_j=\pi_{m_0}\bigl(Wq_j(Y\mid S_i\cap S_j)\bigr). Z j = π m 0 ( W q j ( Y ∣ S i ∩ S j ) ) . Let R i \mathcal{R}_i R i Z < i Z_{<i} Z < i A i , Y , W A_i,Y,W A i , Y , W A i A_i A i Z i , Y , W , E Z_i,Y,W,E Z i , Y , W , E
R i ( σ Z i A i Y W E ) = σ Z i Z < i Y W E , \mathcal{R}_i(\sigma_{Z_iA_iYWE})=\sigma_{Z_iZ_{<i}YWE}, R i ( σ Z i A i Y W E ) = σ Z i Z < i Y W E , R i ( τ m 0 ⊗ σ A i Y W E ) = τ m 0 ⊗ σ Z < i Y W E . \mathcal{R}_i(\tau_{m_0}\otimes\sigma_{A_iYWE})=\tau_{m_0}\otimes\sigma_{Z_{<i}YWE}. R i ( τ m 0 ⊗ σ A i Y W E ) = τ m 0 ⊗ σ Z < i Y W E . Contractivity gives
Δ ( σ Z i Z < i Y W E , τ m 0 ⊗ σ Z < i Y W E ) ≤ ϵ 0 . \Delta(\sigma_{Z_iZ_{<i}YWE},\tau_{m_0}\otimes\sigma_{Z_{<i}YWE})\le\epsilon_0. Δ ( σ Z i Z < i Y W E , τ m 0 ⊗ σ Z < i Y W E ) ≤ ϵ 0 . Averaging over y o u t y_{\mathrm{out}} y out Δ ( ρ ( i ) , ρ ( i − 1 ) ) ≤ ϵ 0 \Delta(\rho^{(i)},\rho^{(i-1)})\le\epsilon_0 Δ ( ρ ( i ) , ρ ( i − 1 ) ) ≤ ϵ 0
Total error. Summing the adjacent distances yields
Δ ( ρ Z Y W E , τ m ⊗ ρ Y W E ) ≤ ∑ i = 1 M Δ ( ρ ( i ) , ρ ( i − 1 ) ) ≤ M ϵ 0 . \Delta(\rho_{ZYW E},\tau_m\otimes\rho_{YW E})\le\sum_{i=1}^{M}\Delta(\rho^{(i)},\rho^{(i-1)})\le M\epsilon_0. Δ ( ρ Z Y W E , τ m ⊗ ρ Y W E ) ≤ i = 1 ∑ M Δ ( ρ ( i ) , ρ ( i − 1 ) ) ≤ M ϵ 0 . By (26) , M ϵ 0 ≤ η M\epsilon_0\le\eta M ϵ 0 ≤ η
Linear output at constant entropy rate
Lemma 4.5. Fix a constant 0 < μ ≤ 1 0<\mu\le1 0 < μ ≤ 1 c μ , a μ , A μ c_\mu,a_\mu,A_\mu c μ , a μ , A μ n n n μ n ≤ k ≤ n \mu n\le k\le n μ n ≤ k ≤ n 0 < η ≤ 1 / 2 0<\eta\le1/2 0 < η ≤ 1/2 h = log ( n / η ) ≤ c μ n h=\log(n/\eta)\le c_\mu n h = log ( n / η ) ≤ c μ n ( k , η ) (k,\eta) ( k , η ) Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m} Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m
d ≤ A μ h log 2 ( n / h ) , m ≥ a μ n . d\le A_\mu h\log^2(n/h),\qquad m\ge a_\mu n. d ≤ A μ h log 2 ( n / h ) , m ≥ a μ n . The map Ext \operatorname{Ext} Ext μ \mu μ
Proof. In Theorem 4.4 , take
λ = ⌈ 16 h ⌉ , ℓ = ⌈ log ( n / λ ) ⌉ , m 0 = ⌊ λ / 4 ⌋ , ϱ = 2 , M = ⌊ μ n 8 λ ⌋ . \lambda=\lceil16h\rceil,\qquad\ell=\lceil\log(n/\lambda)\rceil,\qquad m_0=\lfloor\lambda/4\rfloor,\qquad\varrho=2,\qquad M=\left\lfloor\frac{\mu n}{8\lambda}\right\rfloor. λ = ⌈ 16 h ⌉ , ℓ = ⌈ log ( n / λ )⌉ , m 0 = ⌊ λ /4 ⌋ , ϱ = 2 , M = ⌊ 8 λ μ n ⌋ . Choose c μ c_\mu c μ λ ≤ μ n / 16 \lambda\le\mu n/16 λ ≤ μ n /16 n n n ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 λ 2 ℓ = O ( n ) \lambda2^\ell=O(n) λ 2 ℓ = O ( n ) M ≥ μ n / ( 16 λ ) M\ge\mu n/(16\lambda) M ≥ μ n / ( 16 λ ) m 0 ≥ λ / 8 m_0\ge\lambda/8 m 0 ≥ λ /8 m = M m 0 ≥ μ n / 128 m=Mm_0\ge\mu n/128 m = M m 0 ≥ μ n /128 v = O ( ℓ 2 ) v=O(\ell^2) v = O ( ℓ 2 ) d = λ ( v + 1 ) = O μ ( h log 2 ( n / h ) ) d=\lambda(v+1)=O_\mu(h\log^2(n/h)) d = λ ( v + 1 ) = O μ ( h log 2 ( n / h ))
Since k − λ ϱ M ≥ 3 μ n / 4 k-\lambda\varrho M\ge3\mu n/4 k − λ ϱM ≥ 3 μ n /4 m 0 ≤ λ / 4 m_0\le\lambda/4 m 0 ≤ λ /4 M ≤ n M\le n M ≤ n (26) is at most
n 2 ( 2 λ / 8 − 3 μ n / 8 + ℓ 2 − 3 λ / 8 ) . \frac{n}{2}\left(2^{\lambda/8-3\mu n/8}+\sqrt{\ell}\,2^{-3\lambda/8}\right). 2 n ( 2 λ /8 − 3 μ n /8 + ℓ 2 − 3 λ /8 ) . Using λ ≤ μ n / 16 \lambda\le\mu n/16 λ ≤ μ n /16 h ≤ μ n / 256 h\le\mu n/256 h ≤ μ n /256 λ ≥ 16 h \lambda\ge16h λ ≥ 16 h ℓ ≤ h \ell\le h ℓ ≤ h η = n 2 − h \eta=n2^{-h} η = n 2 − h
n 2 2 λ / 8 − 3 μ n / 8 ≤ n 2 2 − 47 μ n / 128 = n 2 2 h − 47 μ n / 128 ≤ η 2 , \frac{n}{2}2^{\lambda/8-3\mu n/8}\le\frac{n}{2}2^{-47\mu n/128}=\frac{n}{2}2^{h-47\mu n/128}\le\frac{\eta}{2}, 2 n 2 λ /8 − 3 μ n /8 ≤ 2 n 2 − 47 μ n /128 = 2 n 2 h − 47 μ n /128 ≤ 2 η , n 2 ℓ 2 − 3 λ / 8 ≤ η 2 ℓ 2 − 5 h ≤ η 2 . \frac{n}{2}\sqrt{\ell}\,2^{-3\lambda/8}\le\frac{\eta}{2}\sqrt{\ell}\,2^{-5h}\le\frac{\eta}{2}. 2 n ℓ 2 − 3 λ /8 ≤ 2 η ℓ 2 − 5 h ≤ 2 η . Shoup’s algorithm [44 Theorem 4.1] deterministically constructs an irreducible polynomial of degree λ \lambda λ F 2 \mathbb{F}_2 F 2 λ \lambda λ F 2 λ \mathbb{F}_{2^\lambda} F 2 λ F 2 [ z ] \mathbb{F}_2[z] F 2 [ z ] λ \lambda λ n n n
Reducing the Seed Length
Put h = log ( n / η ) h=\log(n/\eta) h = log ( n / η ) Lemma 4.5 from O μ ( h log 2 ( n / h ) ) O_\mu(h\log^2(n/h)) O μ ( h log 2 ( n / h )) O μ ( h ) O_\mu(h) O μ ( h )
Sampling and extraction tools
Combining Vadhan’s sampler [Vad04, Lemma 8.4] with König and Renner’s entropy-sampling theorem [28 Corollary 6.19] gives an explicit entropy sampler for sources with quantum side information.
Lemma 5.1 (Entropy sampling). For every 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 there is a constant C ϵ > 0 C_\epsilon>0 C ϵ > 0 such that the following holds. Let N , w ≥ 1 N,w\ge1 N , w ≥ 1 be integers, let 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 and let C ϵ log ( 1 / δ ) ≤ t ≤ N C_\epsilon\log(1/\delta)\le t\le N C ϵ log ( 1/ δ ) ≤ t ≤ N be an integer. There is an explicit map
S : { 0 , 1 } r → ( [ N ] t ) , r = O ϵ ( log N + log ( 1 / δ ) ) , S:\{0,1\}^r\to\binom{[N]}{t},\qquad r=O_\epsilon(\log N+\log(1/\delta)), S : { 0 , 1 } r → ( t [ N ] ) , r = O ϵ ( log N + log ( 1/ δ )) , with the following entropy guarantee.
Let ρ X E \rho_{XE} ρ X E be a normalized cq state with X ∈ ( { 0 , 1 } w ) N X\in(\{0,1\}^w)^N X ∈ ({ 0 , 1 } w ) N and H min ( X ∣ E ) ρ ≥ μ N w H_{\min}(X\mid E)_\rho\ge\mu Nw H m i n ( X ∣ E ) ρ ≥ μ N w where 0 < μ ≤ 1 0<\mu\le1 0 < μ ≤ 1 For a uniform seed R R R independent of X E XE X E set
B = X S ( R ) , κ = N t w . B=X_{S(R)},\qquad\kappa=\frac{N}{tw}. B = X S ( R ) , κ = tw N . If κ ≤ 0.15 \kappa\le0.15 κ ≤ 0.15 then
H min τ ( B ∣ R E ) ρ ≥ ( μ − 3 ϵ − 2 κ log ( 1 / κ ) ) w t (27) H_{\min}^{\tau}(B\mid RE)_\rho\ge(\mu-3\epsilon-2\kappa\log(1/\kappa))wt \tag*{(27)} H m i n τ ( B ∣ R E ) ρ ≥ ( μ − 3 ϵ − 2 κ log ( 1/ κ )) w t (27) for every 0 < τ < 1 0<\tau<1 0 < τ < 1 satisfying
4 ⋅ 2 − ϵ N w + 6 δ 1 / 4 ≤ τ 2 . 4\cdot2^{-\epsilon Nw}+6\delta^{1/4}\le\tau^2. 4 ⋅ 2 − ϵ N w + 6 δ 1/4 ≤ τ 2 . The short-seed hash family of [51 Theorem 10] gives the following extractor.
Lemma 5.2 (Short-seed extraction). There is an absolute constant C > 0 C > 0 C > 0 n ≥ 1 n \ge1 n ≥ 1 , e r r o r , error , er r or , a n d i n t e g e r o u t p u t l e n g t h $ 1 ≤ m ≤ k − C log ( 1 / η ) , and integer output length \$1 \le m \le k - C \log(1/\eta) , an d in t e g er o u tp u tl e n g t h $1 ≤ m ≤ k − C log ( 1/ η ) ( k , η ) (k,\eta) ( k , η )
H : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m , d ≤ 2 m + C log ( n / η ) . H:\{0,1\}^{n} \times\{0,1\}^{d} \to\{0,1\}^{m}, \qquad d \le2m + C\log(n/\eta). H : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m , d ≤ 2 m + C log ( n / η ) . The map H H H n + m + log ( 1 / η ) n+m+\log(1/\eta) n + m + log ( 1/ η )
The original statements and the derivations of Lemmas 5.1 and 5.2 appear in Appendix § 11 .
Generating the internal seed
Theorem 5.3. Fix constants 0 < μ ≤ 1 0 < \mu\le1 0 < μ ≤ 1 A > 0 A > 0 A > 0 C M > 0 C_M > 0 C M > 0 c = c ( μ , A , C M ) > 0 c=c(\mu,A,C_M)>0 c = c ( μ , A , C M ) > 0 n n n μ n ≤ k ≤ n \mu n \le k \le n μ n ≤ k ≤ n 2 − c n ≤ η ≤ 1 / 2 2^{-cn} \le\eta\le1/2 2 − c n ≤ η ≤ 1/2 ( k , η ) (k,\eta) ( k , η ) G : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } M G:\{0,1\}^{n} \times\{0,1\}^{d} \to\{0,1\}^{M} G : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } M
d = O μ , A , C M ( h ) , M = ⌊ C M h log A ( n / h ) ⌋ , h = log ( n / η ) . d=O_{\mu,A,C_M}(h), \qquad M=\left\lfloor C_M h\log^{A}(n/h)\right\rfloor, \qquad h=\log(n/\eta). d = O μ , A , C M ( h ) , M = ⌊ C M h log A ( n / h ) ⌋ , h = log ( n / η ) . The map G G G μ \mu μ A A A C M C_M C M
Construction. Set ν = μ / 4 \nu=\mu/4 ν = μ /4 Q ≥ 1 + 2 / ν Q \ge1+2/\nu Q ≥ 1 + 2/ ν C 0 C_0 C 0 C w C_w C w C t C_t C t ε \varepsilon ε μ \mu μ A A A C M C_M C M Theorem 5.3 .
String lengths. Let
d 0 = ⌈ C 0 h ⌉ , m j = ⌊ d j / 4 ⌋ , d j + 1 = d j + m j , d_0=\lceil C_0h\rceil,\qquad m_j=\lfloor d_j/4\rfloor,\qquad d_{j+1}=d_j+m_j, d 0 = ⌈ C 0 h ⌉ , m j = ⌊ d j /4 ⌋ , d j + 1 = d j + m j , and stop at the first T T T d T − d 0 ≥ M d_T-d_0 \ge M d T − d 0 ≥ M d 0 d_0 d 0 Z 0 Z_0 Z 0
Samples of increasing length. Pad X X X N = ⌈ n / w ⌉ N=\lceil n/w\rceil N = ⌈ n / w ⌉ w = ⌈ C w n / h ⌉ w=\lceil C_w\sqrt{n/h}\rceil w = ⌈ C w n / h ⌉ t 0 = ⌈ C t h ⌉ t_0=\lceil C_th\rceil t 0 = ⌈ C t h ⌉ t i = Q i t 0 t_i=Q^it_0 t i = Q i t 0 0 ≤ i < T 0 \le i<T 0 ≤ i < T i i i Lemma 5.1 with sample size t i t_i t i ε \varepsilon ε
δ = ( η 32 T ) 8 . \delta=\left(\frac{\eta}{32T}\right)^8. δ = ( 32 T η ) 8 . Let r r r R ∈ { 0 , 1 } r R \in\{0,1\}^{r} R ∈ { 0 , 1 } r X E , Z 0 XE,Z_0 X E , Z 0 t i t_i t i R R R S i ( R ) S_i(R) S i ( R ) B i = X S i ( R ) B_i=X_{S_i(R)} B i = X S i ( R ) B < i = ( B 0 , … , B i − 1 ) B_{<i}=(B_0,\ldots,B_{i-1}) B < i = ( B 0 , … , B i − 1 ) B < 0 B_{<0} B < 0
Extraction in reverse order. At step j = 0 , … , T − 1 j=0,\ldots,T-1 j = 0 , … , T − 1 B T − 1 − j B_{T-1-j} B T − 1 − j η 0 = η / ( 2 T ) \eta_0=\eta/(2T) η 0 = η / ( 2 T ) H j H_j H j Lemma 5.2 . The input length is w t T − 1 − j w t_{T-1-j} w t T − 1 − j m j m_j m j η 0 \eta_0 η 0 H j H_j H j m j + C log ( 1 / η 0 ) m_j+C\log(1/\eta_0) m j + C log ( 1/ η 0 ) H j H_j H j d j d_j d j H j H_j H j H j ( B T − 1 − j , Z j ) H_j(B_{T-1-j},Z_j) H j ( B T − 1 − j , Z j ) Z j Z_j Z j
Z j + 1 = Z j ∘ H j ( B T − 1 − j , Z j ) . (28) Z_{j+1}=Z_j\mathbin{\circ}H_j(B_{T-1-j},Z_j). \tag*{(28)} Z j + 1 = Z j ∘ H j ( B T − 1 − j , Z j ) . (28) The external seed is ( R , Z 0 ) (R,Z_0) ( R , Z 0 ) M M M
The geometric growth of the sample lengths lets B i B_i B i B < i B_{<i} B < i B T − 1 , … , B 0 B_{T-1},\ldots,B_0 B T − 1 , … , B 0 B i B_i B i B < i B_{<i} B < i
Proof of Theorem 5.3 . Parameter choices. Set ν = μ / 4 \nu=\mu/4 ν = μ /4 ε = μ / 100 \varepsilon=\mu/100 ε = μ /100 Q = ⌈ 1 + 8 / μ ⌉ Q=\lceil1+8/\mu\rceil Q = ⌈ 1 + 8/ μ ⌉ C ε ≥ 1 C_\varepsilon\ge1 C ε ≥ 1 C C C Lemmas 5.1 and 5.2 , respectively. Choose C w ≥ 4 C_w\ge4 C w ≥ 4 C t , C 0 C_t,C_0 C t , C 0
3 ε + 4 C w 2 log ( C w 2 / 2 ) ≤ μ / 4 , (29) 3\varepsilon+\frac{4}{C_w^2}\log(C_w^2/2)\le\mu/4, \tag*{(29)} 3 ε + C w 2 4 log ( C w 2 /2 ) ≤ μ /4 , (29) C t ≥ 48 C ε , C 0 ≥ 20 , C 0 ≥ 8 C . C_t\ge48C_\varepsilon,\qquad C_0\ge20,\qquad C_0\ge8C. C t ≥ 48 C ε , C 0 ≥ 20 , C 0 ≥ 8 C . Choose 0 < c ≤ ε / 8 0<c\le\varepsilon/8 0 < c ≤ ε /8 h ≤ 2 c n h\le2cn h ≤ 2 c n
t T − 1 ≤ N , d T 4 + 4 C h + 1 ≤ ν 2 w t 0 . (30) t_{T-1}\le N,\qquad\frac{d_T}{4}+4Ch+1\le\frac{\nu}{2}wt_0. \tag*{(30)} t T − 1 ≤ N , 4 d T + 4 C h + 1 ≤ 2 ν w t 0 . (30) Put η 0 = η / ( 2 T ) \eta_0=\eta/(2T) η 0 = η / ( 2 T ) τ = η / ( 8 T ) \tau=\eta/(8T) τ = η / ( 8 T )
To see that such a constant c c c d j ≥ C 0 h ≥ 20 d_j\ge C_0h\ge20 d j ≥ C 0 h ≥ 20 m j = ⌊ d j / 4 ⌋ ≥ d j / 4 − 1 ≥ d j / 5 m_j=\lfloor d_j/4\rfloor\ge d_j/4-1\ge d_j/5 m j = ⌊ d j /4 ⌋ ≥ d j /4 − 1 ≥ d j /5 d j + 1 ≥ ( 6 / 5 ) d j d_{j+1}\ge(6/5)d_j d j + 1 ≥ ( 6/5 ) d j T = O ( log log ( n / h ) ) T=O(\log\log(n/h)) T = O ( log log ( n / h )) d T ≤ 5 4 ( d 0 + M ) d_T\le\frac{5}{4}(d_0+M) d T ≤ 4 5 ( d 0 + M )
t T − 1 = h ( log ( n / h ) ) O ( 1 ) , d T = O ( h log A ( n / h ) ) , N , w t 0 = Θ ( n h ) . (31) t_{T-1}=h(\log(n/h))^{O(1)},\qquad d_T=O(h\log^A(n/h)),\qquad N,wt_0=\Theta(\sqrt{nh}). \tag*{(31)} t T − 1 = h ( log ( n / h ) ) O ( 1 ) , d T = O ( h log A ( n / h )) , N , w t 0 = Θ ( nh ) . (31) Both conditions in (30) hold when n / h n/h n / h n / h \sqrt{n/h} n / h log ( n / h ) \log(n/h) log ( n / h ) c c c n n n h ≤ 2 c n h\le2cn h ≤ 2 c n
Entropy of the sampled blocks. Fix a cq source ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ≥ μ n H_{\min}(X\mid E)\ge\mu n H m i n ( X ∣ E ) ≥ μ n H min τ ( B i ∣ R E ) ρ ≥ ν w t i H_{\min}^{\tau}(B_i\mid RE)_\rho\ge\nu wt_i H m i n τ ( B i ∣ R E ) ρ ≥ ν w t i Lemma 5.1 . We then account for revealing B < i B_{<i} B < i
Padding preserves the source entropy. Since n ′ = N w < n + w = n + O ( n / h ) ≤ 2 n n'=Nw<n+w=n+O(\sqrt{n/h})\le2n n ′ = N w < n + w = n + O ( n / h ) ≤ 2 n n n n μ / 2 \mu/2 μ /2 T = O ( log log n ) ≤ n T=O(\log\log n)\le n T = O ( log log n ) ≤ n
log ( 1 / δ ) = 8 log ( 32 T / η ) ≤ 48 h , log ( n ′ / η 0 ) ≤ log ( 4 n T / η ) ≤ 4 h . (32) \log(1/\delta)=8\log(32T/\eta)\le48h,\qquad\log(n'/\eta_0)\le\log(4nT/\eta)\le4h. \tag*{(32)} log ( 1/ δ ) = 8 log ( 32 T / η ) ≤ 48 h , log ( n ′ / η 0 ) ≤ log ( 4 n T / η ) ≤ 4 h . (32) We check the sample-size condition using C t ≥ 48 C ε C_t\ge48C_\varepsilon C t ≥ 48 C ε (29) , the logarithmic bound (5.6, and t T − 1 ≤ N t_{T-1}\le N t T − 1 ≤ N (30) :
C ε log ( 1 / δ ) ≤ 48 C ε h ≤ C t h ≤ t 0 ≤ t i ≤ t T − 1 ≤ N . (33) C_\varepsilon\log(1/\delta)\le48C_\varepsilon h\le C_t h\le t_0\le t_i\le t_{T-1}\le N. \tag*{(33)} C ε log ( 1/ δ ) ≤ 48 C ε h ≤ C t h ≤ t 0 ≤ t i ≤ t T − 1 ≤ N . (33) Next, t i ≥ t 0 ≥ h t_i\ge t_0\ge h t i ≥ t 0 ≥ h w 2 ≥ C w 2 n / h w^2\ge C_w^2n/h w 2 ≥ C w 2 n / h n ′ ≤ 2 n n'\le2n n ′ ≤ 2 n
κ i : = N t i w = n ′ t i w 2 ≤ 2 n h ⋅ C w 2 n / h = 2 C w 2 ≤ 1 8 . (34) \kappa_i:=\frac{N}{t_iw}=\frac{n'}{t_iw^2}\le\frac{2n}{h\cdot C_w^2n/h}=\frac{2}{C_w^2}\le\frac{1}{8}. \tag*{(34)} κ i := t i w N = t i w 2 n ′ ≤ h ⋅ C w 2 n / h 2 n = C w 2 2 ≤ 8 1 . (34) Since κ log ( 1 / κ ) \kappa\log(1/\kappa) κ log ( 1/ κ ) ( 0 , 1 / 8 ] (0,1/8] ( 0 , 1/8 ] (34) and (29) imply
3 ε + 2 κ i log ( 1 / κ i ) ≤ 3 ε + 4 C w 2 log ( C w 2 / 2 ) ≤ μ / 4. (35) 3\varepsilon+2\kappa_i\log(1/\kappa_i)\le3\varepsilon+\frac{4}{C_w^2}\log(C_w^2/2)\le\mu/4. \tag*{(35)} 3 ε + 2 κ i log ( 1/ κ i ) ≤ 3 ε + C w 2 4 log ( C w 2 /2 ) ≤ μ /4. (35) For the smoothing condition, T ≤ n T\le n T ≤ n 512 T 2 − 3 ε n / 4 ≤ 1 512T2^{-3\varepsilon n/4}\le1 512 T 2 − 3 ε n /4 ≤ 1 n n n n ′ ≥ n n'\ge n n ′ ≥ n η ≥ 2 − c n \eta\ge2^{-cn} η ≥ 2 − c n c ≤ ε / 8 c\le\varepsilon/8 c ≤ ε /8
2 − ε n ′ ≤ η 2 2 − ( ε − 2 c ) n ≤ η 2 2 − 3 ε n / 4 ≤ η 2 512 T 2 , 2^{-\varepsilon n'}\le\eta^2 2^{-(\varepsilon-2c)n}\le\eta^2 2^{-3\varepsilon n/4}\le\frac{\eta^2}{512T^2}, 2 − ε n ′ ≤ η 2 2 − ( ε − 2 c ) n ≤ η 2 2 − 3 ε n /4 ≤ 512 T 2 η 2 , 6 δ 1 / 4 = 6 ( η 32 T ) 2 = 3 η 2 512 T 2 . (36) 6\delta^{1/4}=6\left(\frac{\eta}{32T}\right)^2=\frac{3\eta^2}{512T^2}. \tag*{(36)} 6 δ 1/4 = 6 ( 32 T η ) 2 = 512 T 2 3 η 2 . (36) Substituting (36) gives
4 ⋅ 2 − ε n ′ + 6 δ 1 / 4 ≤ 4 η 2 + 3 η 2 512 T 2 ≤ η 2 64 T 2 = τ 2 . (37) 4 \cdot2^{-\varepsilon n'} + 6\delta^{1/4} \le\frac{4\eta^2+3\eta^2}{512T^2} \le\frac{\eta^2}{64T^2}=\tau^2. \tag*{(37)} 4 ⋅ 2 − ε n ′ + 6 δ 1/4 ≤ 512 T 2 4 η 2 + 3 η 2 ≤ 64 T 2 η 2 = τ 2 . (37) Let ρ B 0 ⋯ B T − 1 R E \rho_{B_0\cdots B_{T-1}RE} ρ B 0 ⋯ B T − 1 R E ρ X E ⊗ τ r \rho_{XE} \otimes\tau_r ρ X E ⊗ τ r B q = X S q ( R ) B_q = X_{S_q(R)} B q = X S q ( R ) 0 ≤ q < T 0 \le q < T 0 ≤ q < T X X X
Equations (33) , (34) , and (37) verify the hypotheses of Lemma 5.1 with entropy rate μ / 2 \mu/2 μ /2 t i t_i t i ε \varepsilon ε δ \delta δ τ \tau τ B i B_i B i E E E S i S_i S i R R R B i B_i B i E E E (35) and ν = μ / 4 \nu=\mu/4 ν = μ /4
H min τ ( B i ∣ R E ) ρ ≥ ( μ 2 − 3 ε − 2 κ i log ( 1 / κ i ) ) w t i ≥ ν w t i . (38) H_{\min}^{\tau}(B_i \mid RE)_\rho\ge\left(\frac{\mu}{2}-3\varepsilon-2\kappa_i\log(1/\kappa_i)\right)wt_i \ge\nu wt_i. \tag*{(38)} H m i n τ ( B i ∣ R E ) ρ ≥ ( 2 μ − 3 ε − 2 κ i log ( 1/ κ i ) ) w t i ≥ ν w t i . (38) Apply Lemma 2.1 with source B i B_i B i B < i B_{<i} B < i R E RE R E B < i B_{<i} B < i w ∑ q < i t q w\sum_{q<i}t_q w ∑ q < i t q
H min τ ( B i ∣ B < i R E ) ρ ≥ H min τ ( B i ∣ R E ) ρ − w ∑ q < i t q . (39) H_{\min}^{\tau}(B_i \mid B_{<i}RE)_\rho\ge H_{\min}^{\tau}(B_i \mid RE)_\rho- w\sum_{q<i}t_q. \tag*{(39)} H m i n τ ( B i ∣ B < i R E ) ρ ≥ H m i n τ ( B i ∣ R E ) ρ − w q < i ∑ t q . (39) Substituting (38) and t q = Q q t 0 t_q=Q^q t_0 t q = Q q t 0 (39) , and using Q ≥ 1 + 2 / ν Q\ge1+2/\nu Q ≥ 1 + 2/ ν
H min τ ( B i ∣ B < i R E ) ρ ≥ ν w t i − w ∑ q < i t q ≥ ( ν − 1 Q − 1 ) w t i ≥ ν 2 w t i . (40) \begin{aligned}
H_{\min}^{\tau}(B_i \mid B_{<i}RE)_\rho\ge\nu wt_i-w\sum_{q<i}t_q \\
&\ge\left(\nu-\frac{1}{Q-1}\right)wt_i\ge\frac{\nu}{2}wt_i. \tag*{(40)}
\end{aligned} H m i n τ ( B i ∣ B < i R E ) ρ ≥ ν w t i − w q < i ∑ t q ≥ ( ν − Q − 1 1 ) w t i ≥ 2 ν w t i . (40) In particular, every B i B_i B i Ω ( n h ) \Omega(\sqrt{nh}) Ω ( nh ) B < i R E B_{<i}RE B < i R E
Requirements for extraction. Fix 0 ≤ j < T 0\le j<T 0 ≤ j < T i = T − 1 − j i=T-1-j i = T − 1 − j Lemma 5.2 with input length w t i wt_i w t i m j m_j m j η 0 \eta_0 η 0 H j H_j H j 2 m j + C log ( w t i / η 0 ) 2m_j+C\log(wt_i/\eta_0) 2 m j + C log ( w t i / η 0 ) w t i ≤ N w = n ′ wt_i\le Nw=n' w t i ≤ N w = n ′ m j ≤ d j / 4 m_j\le d_j/4 m j ≤ d j /4 (32) gives
2 m j + C log ( w t i / η 0 ) ≤ d j / 2 + C log ( n ′ / η 0 ) ≤ d j / 2 + 4 C h ≤ d j . 2m_j+C\log(wt_i/\eta_0)\le d_j/2+C\log(n'/\eta_0)\le d_j/2+4Ch\le d_j. 2 m j + C log ( w t i / η 0 ) ≤ d j /2 + C log ( n ′ / η 0 ) ≤ d j /2 + 4 C h ≤ d j . The last inequality uses 4 C h ≤ C 0 h / 2 ≤ d j / 2 4Ch\le C_0h/2\le d_j/2 4 C h ≤ C 0 h /2 ≤ d j /2 Z j Z_j Z j H j H_j H j (32) and (30) give
m j + C log ( 1 / η 0 ) + 1 ≤ d T 4 + 4 C h + 1 ≤ ν 2 w t 0 ≤ ν 2 w t i . (41) m_j+C\log(1/\eta_0)+1\le\frac{d_T}{4}+4Ch+1\le\frac{\nu}{2}wt_0\le\frac{\nu}{2}wt_i. \tag*{(41)} m j + C log ( 1/ η 0 ) + 1 ≤ 4 d T + 4 C h + 1 ≤ 2 ν w t 0 ≤ 2 ν w t i . (41) Together, equations (40) and (41) allow us to apply Lemma 2.2 to each H j H_j H j
Hybrid states. Let ρ \rho ρ 0 ≤ j ≤ T 0\le j\le T 0 ≤ j ≤ T Z j Z_j Z j d j d_j d j
τ d j ⊗ ρ B < T − j R E \tau_{d_j}\otimes\rho_{B_{<T-j}RE} τ d j ⊗ ρ B < T − j R E apply (28) for j , … , T − 1 j,\ldots,T-1 j , … , T − 1 ρ Z T R E ( j ) \rho_{Z_TRE}^{(j)} ρ Z T R E ( j ) Z 0 Z_0 Z 0
ρ Z T R E ( 0 ) = ρ Z T R E , ρ Z T R E ( T ) = τ d T ⊗ ρ R E . \rho_{Z_TRE}^{(0)}=\rho_{Z_TRE},\qquad\rho_{Z_TRE}^{(T)}=\tau_{d_T}\otimes\rho_{RE}. ρ Z T R E ( 0 ) = ρ Z T R E , ρ Z T R E ( T ) = τ d T ⊗ ρ R E . We will prove Δ ( ρ ( j ) , ρ ( j + 1 ) ) ≤ η 0 + 4 τ \Delta(\rho^{(j)}, \rho^{(j+1)}) \le\eta_0 + 4\tau Δ ( ρ ( j ) , ρ ( j + 1 ) ) ≤ η 0 + 4 τ 0 ≤ j < T 0 \le j < T 0 ≤ j < T
Distance between consecutive hybrids. Fix 0 ≤ j < T 0 \le j < T 0 ≤ j < T i = T − 1 − j i = T - 1 - j i = T − 1 − j V ∼ U d j V \sim U_{d_j} V ∼ U d j B < i R E B_{<i}RE B < i R E ρ ( j ) \rho^{(j)} ρ ( j ) d j + 1 d_{j+1} d j + 1 V ∘ H j ( B i , V ) V \circ H_j(B_i,V) V ∘ H j ( B i , V ) j j j ρ ( j + 1 ) \rho^{(j+1)} ρ ( j + 1 ) V ∘ H j ( B i , V ) V \circ H_j(B_i,V) V ∘ H j ( B i , V ) d j + 1 d_{j+1} d j + 1 B < i R E B_{<i}RE B < i R E j + 1 , … , T − 1 j+1,\ldots,T-1 j + 1 , … , T − 1 B < i B_{<i} B < i Z T R E Z_TRE Z T R E
The map H j H_j H j Lemma 5.2 is a strong quantum-proof ( m j + C log ( 1 / η 0 ) , η 0 ) (m_j+C\log(1/\eta_0),\eta_0) ( m j + C log ( 1/ η 0 ) , η 0 ) Lemma 2.2 to H j H_j H j B i B_i B i V V V B < i R E B_{<i}RE B < i R E τ \tau τ (40) and (41) supply the required smooth entropy. The strong guarantee of H j H_j H j V V V
Δ ( ρ ( V ∘ H j ( B i , V ) ) B < i R E , τ d j + 1 ⊗ ρ B < i R E ) ≤ η 0 + 4 τ . \Delta\left(\rho_{(V\circ H_j(B_i,V))B_{<i}RE},\tau_{d_{j+1}}\otimes\rho_{B_{<i}RE}\right)\le\eta_0+4\tau. Δ ( ρ ( V ∘ H j ( B i , V )) B < i R E , τ d j + 1 ⊗ ρ B < i R E ) ≤ η 0 + 4 τ . Let Φ j \Phi_j Φ j Z j + 1 B < i R E Z_{j+1}B_{<i}RE Z j + 1 B < i R E j + 1 , … , T − 1 j+1,\ldots,T-1 j + 1 , … , T − 1 Z j + 1 Z_{j+1} Z j + 1 Z T Z_T Z T B < i B_{<i} B < i B < i B_{<i} B < i Z T R E Z_TRE Z T R E R E RE R E Φ j \Phi_j Φ j ρ ( V ∘ H j ( B i , V ) ) B < i R E \rho_{(V\circ H_j(B_i,V))B_{<i}RE} ρ ( V ∘ H j ( B i , V )) B < i R E ρ ( j ) \rho^{(j)} ρ ( j ) Φ j \Phi_j Φ j τ d j + 1 ⊗ ρ B < i R E \tau_{d_{j+1}}\otimes\rho_{B_{<i}RE} τ d j + 1 ⊗ ρ B < i R E ρ ( j + 1 ) \rho^{(j+1)} ρ ( j + 1 )
Δ ( ρ ( j ) , ρ ( j + 1 ) ) ≤ η 0 + 4 τ . (42) \Delta(\rho^{(j)},\rho^{(j+1)})\le\eta_0+4\tau. \tag*{(42)} Δ ( ρ ( j ) , ρ ( j + 1 ) ) ≤ η 0 + 4 τ . (42) Total error. Summing (42) over 0 ≤ j < T 0\le j<T 0 ≤ j < T
Δ ( ρ Z T R E , τ d T ⊗ ρ R E ) ≤ ∑ j = 0 T − 1 Δ ( ρ ( j ) , ρ ( j + 1 ) ) ≤ T ( η 0 + 4 τ ) = η . \Delta(\rho_{Z_TRE},\tau_{d_T}\otimes\rho_{RE})
\le\sum_{j=0}^{T-1}\Delta(\rho^{(j)},\rho^{(j+1)})
\le T(\eta_0+4\tau)=\eta. Δ ( ρ Z T R E , τ d T ⊗ ρ R E ) ≤ j = 0 ∑ T − 1 Δ ( ρ ( j ) , ρ ( j + 1 ) ) ≤ T ( η 0 + 4 τ ) = η . The string Z T Z_T Z T Z 0 Z_0 Z 0 O O O M M M
Δ ( ρ O Z 0 R E , τ M ⊗ ρ Z 0 R E ) ≤ η , ρ Z 0 R E = τ d 0 ⊗ ρ R E . \Delta(\rho_{OZ_0RE},\tau_M\otimes\rho_{Z_0RE})\le\eta,\qquad
\rho_{Z_0RE}=\tau_{d_0}\otimes\rho_{RE}. Δ ( ρ O Z 0 R E , τ M ⊗ ρ Z 0 R E ) ≤ η , ρ Z 0 R E = τ d 0 ⊗ ρ R E . Thus O O O ( R , Z 0 ) (R,Z_0) ( R , Z 0 ) Lemma 5.1 and (32) , the common seed R R R r = O ( h ) r=O(h) r = O ( h ) r + d 0 = O ( h ) r+d_0=O(h) r + d 0 = O ( h )
Combining the extractors
Proof of Theorem 1.8 . Construction. Put h = log ( n / η ) h=\log(n/\eta) h = log ( n / η ) τ = η / 100 \tau=\eta/100 τ = η /100 ε = μ / 100 \varepsilon=\mu/100 ε = μ /100 δ = ( τ / 100 ) 8 \delta=(\tau/100)^8 δ = ( τ /100 ) 8 w = w ( μ ) w=w(\mu) w = w ( μ ) N = ⌊ n / w ⌋ N=\lfloor n/w\rfloor N = ⌊ n / w ⌋ n ′ = w N n'=wN n ′ = w N t = ⌊ μ N / 16 ⌋ t=\lfloor\mu N/16\rfloor t = ⌊ μ N /16 ⌋ n ′ n' n ′ N N N w w w T : { 0 , 1 } r → ( [ N ] t ) T:\{0,1\}^r\to\binom{[N]}{t} T : { 0 , 1 } r → ( t [ N ] ) Lemma 5.1 with parameters ε , δ \varepsilon,\delta ε , δ
S ( a ) = ⋃ i ∈ T ( a ) { ( i − 1 ) w + 1 , … , i w } . S(a)=\bigcup_{i\in T(a)}\{(i-1)w+1,\ldots,iw\}. S ( a ) = i ∈ T ( a ) ⋃ {( i − 1 ) w + 1 , … , i w } . For a source string x x x a a a
b = x S ( a ) , c = x [ n ] ∖ S ( a ) , b=x_{S(a)},\qquad c=x_{[n]\setminus S(a)}, b = x S ( a ) , c = x [ n ] ∖ S ( a ) , with coordinates in increasing order. Set n B = w t n_B=wt n B = w t n C = n − n B n_C=n-n_B n C = n − n B n B , n C = Θ μ ( n ) n_B,n_C=\Theta_\mu(n) n B , n C = Θ μ ( n ) n B ≤ μ n / 16 n_B\le\mu n/16 n B ≤ μ n /16 r = O μ ( h ) r=O_\mu(h) r = O μ ( h ) Lemma 4.5 at input length n B n_B n B μ / 2 \mu/2 μ /2 η / 4 \eta/4 η /4
F : { 0 , 1 } n B × { 0 , 1 } d 1 → { 0 , 1 } m , d 1 = O μ ( h log 2 ( n / h ) ) , m = Ω μ ( n ) . F : \{0,1\}^{n_B} \times\{0,1\}^{d_1} \to\{0,1\}^{m}, \qquad d_1 = O_\mu\left(h\log^2(n/h)\right), \qquad m = \Omega_\mu(n). F : { 0 , 1 } n B × { 0 , 1 } d 1 → { 0 , 1 } m , d 1 = O μ ( h log 2 ( n / h ) ) , m = Ω μ ( n ) . To generate the d 1 d_1 d 1 F F F c c c h C = log ( 4 n C / η ) h_C = \log(4n_C/\eta) h C = log ( 4 n C / η ) h C = Θ μ ( h ) h_C = \Theta_\mu(h) h C = Θ μ ( h ) n C / h C = Θ μ ( n / h ) n_C/h_C = \Theta_\mu(n/h) n C / h C = Θ μ ( n / h ) C M C_M C M μ \mu μ d 1 ≤ C M h C log 2 ( n C / h C ) d_1 \le C_M h_C\log^2(n_C/h_C) d 1 ≤ C M h C log 2 ( n C / h C ) Theorem 5.3 at input length n C n_C n C μ / 2 \mu/2 μ /2 η / 4 \eta/4 η /4 A = 2 A = 2 A = 2 d 1 d_1 d 1
G : { 0 , 1 } n C × { 0 , 1 } d 2 → { 0 , 1 } d 1 , d 2 = O μ ( h ) . G : \{0,1\}^{n_C} \times\{0,1\}^{d_2} \to\{0,1\}^{d_1}, \qquad d_2 = O_\mu(h). G : { 0 , 1 } n C × { 0 , 1 } d 2 → { 0 , 1 } d 1 , d 2 = O μ ( h ) . Take c μ c_\mu c μ h ≤ c μ n h \le c_\mu n h ≤ c μ n n n n S , F , G S,F,G S , F , G ( a , y ) ∈ { 0 , 1 } r + d 2 (a,y) \in\{0,1\}^{r+d_2} ( a , y ) ∈ { 0 , 1 } r + d 2
Ext ( x ; a , y ) = F ( b , G ( c , y ) ) . \operatorname{Ext}(x;a,y) = F(b,G(c,y)). Ext ( x ; a , y ) = F ( b , G ( c , y )) . Correctness. Fix a normalized cq state ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ≥ μ n H_{\min}(X \mid E) \ge\mu n H m i n ( X ∣ E ) ≥ μ n A ∼ U r A \sim U_r A ∼ U r Y ∼ U d 2 Y \sim U_{d_2} Y ∼ U d 2 X E XE X E B = X S ( A ) B = X_{S(A)} B = X S ( A ) C = X [ n ] ∖ S ( A ) C = X_{[n]\setminus S(A)} C = X [ n ] ∖ S ( A )
We first check that B B B F F F n − n ′ n-n' n − n ′ H min ( X [ n ′ ] ∣ E ) ≥ μ n − w ≥ ( 7 μ / 8 ) n ′ H_{\min}(X_{[n']} \mid E) \ge\mu n-w \ge(7\mu/8)n' H m i n ( X [ n ′ ] ∣ E ) ≥ μ n − w ≥ ( 7 μ /8 ) n ′ (16) . Since t ≥ μ N / 32 t \ge\mu N/32 t ≥ μ N /32 κ = N / ( t w ) ≤ 32 / ( μ w ) \kappa= N/(tw) \le32/(\mu w) κ = N / ( tw ) ≤ 32/ ( μ w ) w = w ( μ ) w = w(\mu) w = w ( μ )
κ ≤ 0.15 , 3 ε + 2 κ log ( 1 / κ ) ≤ μ / 8. \kappa\le0.15,\qquad3\varepsilon+ 2\kappa\log(1/\kappa) \le\mu/8. κ ≤ 0.15 , 3 ε + 2 κ log ( 1/ κ ) ≤ μ /8. The remaining conditions of Lemma 5.1 are
t ≥ C ε log ( 1 / δ ) , 4 ⋅ 2 − ε n ′ + 6 δ 1 / 4 ≤ τ 2 . t \ge C_\varepsilon\log(1/\delta),\qquad4\cdot2^{-\varepsilon n'} + 6\delta^{1/4} \le\tau^2. t ≥ C ε log ( 1/ δ ) , 4 ⋅ 2 − ε n ′ + 6 δ 1/4 ≤ τ 2 . After fixing w w w
c μ ≤ min { μ 512 C ε w , ε 4 } . c_\mu\le\min\left\{\frac{\mu}{512C_\varepsilon w},\frac{\varepsilon}{4}\right\}. c μ ≤ min { 512 C ε w μ , 4 ε } . For sufficiently large n n n n ≥ 100 n \ge100 n ≥ 100 n ′ ≥ n / 2 n' \ge n/2 n ′ ≥ n /2 t ≥ μ N / 32 ≥ μ n / ( 64 w ) t \ge\mu N/32 \ge\mu n/(64w) t ≥ μ N /32 ≥ μ n / ( 64 w ) δ = ( τ / 100 ) 8 \delta= (\tau/100)^8 δ = ( τ /100 ) 8 log ( n / τ ) ≤ c μ n \log(n/\tau) \le c_\mu n log ( n / τ ) ≤ c μ n
C ε log ( 1 / δ ) = 8 C ε log ( 100 / τ ) ≤ 8 C ε c μ n ≤ μ n 64 w ≤ t . C_\varepsilon\log(1/\delta) = 8C_\varepsilon\log(100/\tau) \le8C_\varepsilon c_\mu n \le\frac{\mu n}{64w} \le t. C ε log ( 1/ δ ) = 8 C ε log ( 100/ τ ) ≤ 8 C ε c μ n ≤ 64 w μ n ≤ t . Moreover,
ε n ′ ≥ ε n 2 ≥ 2 c μ n ≥ 2 log ( 100 / τ ) . \varepsilon n' \ge\frac{\varepsilon n}{2} \ge2c_\mu n \ge2\log(100/\tau). ε n ′ ≥ 2 ε n ≥ 2 c μ n ≥ 2 log ( 100/ τ ) . Consequently,
4 ⋅ 2 − ε n ′ + 6 δ 1 / 4 ≤ 4 ( τ / 100 ) 2 + 6 ( τ / 100 ) 2 = 10 ( τ / 100 ) 2 < τ 2 . 4\cdot2^{-\varepsilon n'} + 6\delta^{1/4} \le4(\tau/100)^2 + 6(\tau/100)^2 = 10(\tau/100)^2 < \tau^2. 4 ⋅ 2 − ε n ′ + 6 δ 1/4 ≤ 4 ( τ /100 ) 2 + 6 ( τ /100 ) 2 = 10 ( τ /100 ) 2 < τ 2 . Applying the lemma at entropy rate 7 μ / 8 7\mu/8 7 μ /8
H min τ ( B ∣ A E ) ≥ 3 μ 4 n B ≥ μ 2 n B + 1. (43) H_{\min}^{\tau}(B \mid AE) \ge\frac{3\mu}{4}n_B \ge\frac{\mu}{2}n_B + 1. \tag*{(43)} H m i n τ ( B ∣ A E ) ≥ 4 3 μ n B ≥ 2 μ n B + 1. (43) Next, we check that C C C G G G B B B A A A ( B , C ) (B,C) ( B , C ) X X X A A A (16) therefore give
H min ( C ∣ B A E ) ≥ H min ( X ∣ E ) − n B ≥ μ n − n B ≥ μ 2 n C . (44) H_{\min}(C \mid BAE) \ge H_{\min}(X \mid E) - n_B \ge\mu n - n_B \ge\frac{\mu}{2}n_C. \tag*{(44)} H m i n ( C ∣ B A E ) ≥ H m i n ( X ∣ E ) − n B ≥ μ n − n B ≥ 2 μ n C . (44) We now replace the internal seed G ( C , Y ) G(C,Y) G ( C , Y ) V ∼ U d 1 V \sim U_{d_1} V ∼ U d 1 (44) and the strong guarantee of G G G
Δ ( ρ G ( C , Y ) B A Y E , τ d 1 ⊗ ρ B A Y E ) ≤ η / 4. \Delta\left(\rho_{G(C,Y)BAYE},\tau_{d_1}\otimes\rho_{BAYE}\right)\leq\eta/4. Δ ( ρ G ( C , Y ) B A Y E , τ d 1 ⊗ ρ B A Y E ) ≤ η /4. Applying F F F B B B
Δ ( ρ Ext ( X ; A , Y ) A Y E , ρ F ( B , V ) A Y E ) ≤ η / 4. (45) \Delta\left(\rho_{\operatorname{Ext}(X;A,Y)AYE},\rho_{F(B,V)AYE}\right)\leq\eta/4. \tag*{(45)} Δ ( ρ Ext ( X ; A , Y ) A Y E , ρ F ( B , V ) A Y E ) ≤ η /4. (45) Finally, Y Y Y B A E BAE B A E (43) also holds with side information A Y E AYE A Y E F F F B B B V V V
Δ ( ρ F ( B , V ) A Y E , τ m ⊗ ρ A Y E ) ≤ η / 4 + 4 τ . (46) \Delta\left(\rho_{F(B,V)AYE},\tau_m\otimes\rho_{AYE}\right)\leq\eta/4+4\tau. \tag*{(46)} Δ ( ρ F ( B , V ) A Y E , τ m ⊗ ρ A Y E ) ≤ η /4 + 4 τ . (46) Combining (45) and (46) , we obtain
Δ ( ρ Ext ( X ; A , Y ) A Y E , τ m ⊗ ρ A Y E ) ≤ η / 2 + 4 τ < η . \Delta\left(\rho_{\operatorname{Ext}(X;A,Y)AYE},\tau_m\otimes\rho_{AYE}\right)\leq\eta/2+4\tau<\eta. Δ ( ρ Ext ( X ; A , Y ) A Y E , τ m ⊗ ρ A Y E ) ≤ η /2 + 4 τ < η . The public seed has length r + d 2 = O μ ( h ) r+d_2=O_\mu(h) r + d 2 = O μ ( h ) m = Ω μ ( n ) m=\Omega_\mu(n) m = Ω μ ( n ) S , F , G S,F,G S , F , G
Corollary 5.4. Fix constants 0 < μ , θ < 1 0<\mu,\theta<1 0 < μ , θ < 1 c μ , θ > 0 c_{\mu,\theta}>0 c μ , θ > 0 n n n μ n ≤ k ≤ n \mu n\leq k\leq n μ n ≤ k ≤ n 0 < η ≤ 1 / 2 0<\eta\leq1/2 0 < η ≤ 1/2 log ( n / η ) ≤ c μ , θ n \log(n/\eta)\leq c_{\mu,\theta}n log ( n / η ) ≤ c μ , θ n ( k , η ) (k,\eta) ( k , η ) Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m} Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m
d = O μ , θ ( log ( n / η ) ) , m = ⌊ ( 1 − θ ) k ⌋ . d=O_{\mu,\theta}(\log(n/\eta)),\qquad m=\lfloor(1-\theta)k\rfloor. d = O μ , θ ( log ( n / η )) , m = ⌊( 1 − θ ) k ⌋ . The map Ext \operatorname{Ext} Ext μ , θ \mu,\theta μ , θ
Proof. Put m = ⌊ ( 1 − θ ) k ⌋ m=\lfloor(1-\theta)k\rfloor m = ⌊( 1 − θ ) k ⌋ θ μ \theta\mu θ μ Theorem 1.8 provides b = ⌊ β n ⌋ b=\lfloor\beta n\rfloor b = ⌊ β n ⌋ β > 0 \beta>0 β > 0 μ , θ \mu,\theta μ , θ J = ⌈ m / b ⌉ = O μ , θ ( 1 ) J=\lceil m/b\rceil=O_{\mu,\theta}(1) J = ⌈ m / b ⌉ = O μ , θ ( 1 ) η / J \eta/J η / J F F F b b b d 0 = O μ , θ ( log ( n / η ) ) d_0=O_{\mu,\theta}(\log(n/\eta)) d 0 = O μ , θ ( log ( n / η )) c μ , θ c_{\mu,\theta} c μ , θ log ( n J / η ) ≤ c θ μ n \log(nJ/\eta)\leq c_{\theta\mu}n log ( n J / η ) ≤ c θ μ n
For a seed ( y 1 , … , y J ) (y_1,\ldots,y_J) ( y 1 , … , y J )
F ( x , y 1 ) ∘ ⋯ ∘ F ( x , y J ) F(x,y_1)\circ\cdots\circ F(x,y_J) F ( x , y 1 ) ∘ ⋯ ∘ F ( x , y J ) and retain the first m m m Ext \operatorname{Ext} Ext
Fix a source ρ X E \rho_{XE} ρ X E H min ( X ∣ E ) ≥ k H_{\min}(X\mid E)\geq k H m i n ( X ∣ E ) ≥ k Y 1 , … , Y J Y_1,\ldots,Y_J Y 1 , … , Y J X E XE X E Z i = F ( X , Y i ) Z_i=F(X,Y_i) Z i = F ( X , Y i ) j j j ( j − 1 ) b < m (j-1)b<m ( j − 1 ) b < m
H min ( X ∣ Z 1 ⋯ Z j − 1 Y 1 ⋯ Y j − 1 E ) ρ ≥ k − ( j − 1 ) b ≥ k − m ≥ θ μ n . H_{\min}(X\mid Z_1\cdots Z_{j-1}Y_1\cdots Y_{j-1}E)_\rho\geq k-(j-1)b\geq k-m\geq\theta\mu n. H m i n ( X ∣ Z 1 ⋯ Z j − 1 Y 1 ⋯ Y j − 1 E ) ρ ≥ k − ( j − 1 ) b ≥ k − m ≥ θ μ n . Thus every call meets the entropy requirement of F F F [15 Lemma A.4] gives the strong guarantee for Ext \operatorname{Ext} Ext J ( η / J ) = η J(\eta/J)=\eta J ( η / J ) = η J d 0 = O μ , θ ( log ( n / η ) ) Jd_0=O_{\mu,\theta}(\log(n/\eta)) J d 0 = O μ , θ ( log ( n / η ))
Extraction with Small Entropy Deficiency
Fix α > 0 \alpha>0 α > 0 n − a n-a n − a ( 1 + α ) log a + ( 2 + α ) log ( 1 / η ) + O α ( 1 ) (1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1) ( 1 + α ) log a + ( 2 + α ) log ( 1/ η ) + O α ( 1 ) O α ( a + log ( 1 / η ) ) O_\alpha(a+\log(1/\eta)) O α ( a + log ( 1/ η ))
A base extractor with small output loss
We start with the classical extractor of Goldreich and Wigderson.
Theorem 6.1 (Goldreich–Wigderson [24 Theorem 4.2 and Lemma 4.3] ). For every integer u ≥ 2 u \ge2 u ≥ 2 1 ≤ k < u 1 \le k < u 1 ≤ k < u 0 < ε < 1 / 4 0 < \varepsilon< 1/4 0 < ε < 1/4 ( k , ε ) (k,\varepsilon) ( k , ε ) H : { 0 , 1 } u × { 0 , 1 } d → { 0 , 1 } m H : \{0,1\}^{u} \times\{0,1\}^{d} \to\{0,1\}^{m} H : { 0 , 1 } u × { 0 , 1 } d → { 0 , 1 } m b = u − k b = u-k b = u − k
d = O ( b + log ( 1 / ε ) ) , m ≥ u − O ( b + log ( 1 / ε ) ) . d = O(b + \log(1/\varepsilon)), \qquad m \ge u - O(b + \log(1/\varepsilon)). d = O ( b + log ( 1/ ε )) , m ≥ u − O ( b + log ( 1/ ε )) . The map H H H u + log ( 1 / ε ) u + \log(1/\varepsilon) u + log ( 1/ ε )
Theorem 6.2 (Berta–Fawzi–Scholz [6 Theorem II.4] ). Let u ≥ 2 u \ge2 u ≥ 2 1 ≤ k 0 ≤ u − 1 1 \le k_0 \le u-1 1 ≤ k 0 ≤ u − 1 0 < η 0 < 1 0 < \eta_0 < 1 0 < η 0 < 1 C B ≥ 1 C_B \ge1 C B ≥ 1 ( k 0 , η 0 ) (k_0,\eta_0) ( k 0 , η 0 ) H : { 0 , 1 } u × { 0 , 1 } d → { 0 , 1 } m H : \{0,1\}^{u} \times\{0,1\}^{d} \to\{0,1\}^{m} H : { 0 , 1 } u × { 0 , 1 } d → { 0 , 1 } m ( k 0 + 1 , C B 2 u − k 0 η 0 ) (k_0+1,C_B2^{u-k_0}\eta_0) ( k 0 + 1 , C B 2 u − k 0 η 0 )
Combining Theorems 6.1 and 6.2 gives a quantum-proof extractor with seed length and output loss O ( a + log ( 1 / η ) ) O(a+\log(1/\eta)) O ( a + log ( 1/ η )) O ( log a + log ( 1 / η ) ) O(\log a+\log(1/\eta)) O ( log a + log ( 1/ η ))
Lemma 6.3. For every integer n ≥ 1 n \ge1 n ≥ 1 0 ≤ k ≤ n 0 \le k \le n 0 ≤ k ≤ n 0 < η ≤ 1 / 2 0 < \eta\le1/2 0 < η ≤ 1/2 ( k , η ) (k,\eta) ( k , η ) Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext} : \{0,1\}^{n} \times\{0,1\}^{d} \to\{0,1\}^{m} Ext : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m a = n − k a = n-k a = n − k
d = O ( log a + log ( 1 / η ) ) , m ≥ n − O ( a + log ( 1 / η ) ) . d = O(\log a+\log(1/\eta)), \qquad m \ge n-O(a+\log(1/\eta)). d = O ( log a + log ( 1/ η )) , m ≥ n − O ( a + log ( 1/ η )) . The map Ext \operatorname{Ext} Ext
Proof. Put η ^ = min { η , 1 / 8 } \widehat{\eta}=\min\{\eta,1/8\} η = min { η , 1/8 } C F , C H , C 0 C_F,C_H,C_0 C F , C H , C 0
Construction. Set n B = ⌈ C 0 ( a + log ( 1 / η ^ ) ) ⌉ n_B=\lceil C_0(a+\log(1/\widehat{\eta}))\rceil n B = ⌈ C 0 ( a + log ( 1/ η ))⌉ n − n B − C F ( a + log ( 1 / η ^ ) ) < 1 n-n_B-C_F(a+\log(1/\widehat{\eta}))<1 n − n B − C F ( a + log ( 1/ η )) < 1
L = n − n B , m = ⌊ L − C F ( a + log ( 1 / η ^ ) ) ⌋ , d H = ⌈ C H ( a + log ( 1 / η ^ ) ) ⌉ . L=n-n_B,\qquad m=\lfloor L-C_F(a+\log(1/\widehat{\eta}))\rfloor,\qquad d_H=\lceil C_H(a+\log(1/\widehat{\eta}))\rceil. L = n − n B , m = ⌊ L − C F ( a + log ( 1/ η ))⌋ , d H = ⌈ C H ( a + log ( 1/ η ))⌉ . Split the input x x x n B n_B n B x B x_B x B L L L x Z x_Z x Z x B x_B x B x Z x_Z x Z
To construct H L H_L H L
b = ⌈ a ⌉ + 1 , ε = η ^ C B 2 b + 1 . b=\lceil a\rceil+1,\qquad\varepsilon=\frac{\widehat{\eta}}{C_B2^{b+1}}. b = ⌈ a ⌉ + 1 , ε = C B 2 b + 1 η . Apply Theorem 6.1 with input length L L L L − b L-b L − b ε \varepsilon ε ( L − b , ε ) (L-b,\varepsilon) ( L − b , ε ) b + log ( 1 / ε ) = O ( a + log ( 1 / η ^ ) ) b+\log(1/\varepsilon)=O(a+\log(1/\widehat{\eta})) b + log ( 1/ ε ) = O ( a + log ( 1/ η )) C F , C H C_F,C_H C F , C H m m m d H d_H d H L − b ≥ 1 L-b\ge1 L − b ≥ 1
H L : { 0 , 1 } L × { 0 , 1 } d H → { 0 , 1 } m . H_L:\{0,1\}^{L}\times\{0,1\}^{d_H}\to\{0,1\}^{m}. H L : { 0 , 1 } L × { 0 , 1 } d H → { 0 , 1 } m . By Theorem 6.2, H L H_L H L ( L − b + 1 , η ^ / 2 ) (L-b+1,\widehat{\eta}/2) ( L − b + 1 , η /2 ) C B 2 b ε = η ^ / 2 C_B2^b\varepsilon=\widehat{\eta}/2 C B 2 b ε = η /2 L − b + 1 = L − ⌈ a ⌉ ≤ L − a L-b+1=L-\lceil a\rceil\le L-a L − b + 1 = L − ⌈ a ⌉ ≤ L − a
Apply Theorem 1.8 at length n B n_B n B 3 / 4 3/4 3/4 η ^ / 2 \widehat{\eta}/2 η /2 ( 3 n B / 4 , η ^ / 2 ) (3n_B/4,\widehat{\eta}/2) ( 3 n B /4 , η /2 ) C 0 C_0 C 0 d H d_H d H d H d_H d H
F : { 0 , 1 } n B × { 0 , 1 } d B → { 0 , 1 } d H , d B = O ( log n B + log ( 1 / η ^ ) ) . F:\{0,1\}^{n_B}\times\{0,1\}^{d_B}\to\{0,1\}^{d_H},\qquad d_B=O(\log n_B+\log(1/\widehat{\eta})). F : { 0 , 1 } n B × { 0 , 1 } d B → { 0 , 1 } d H , d B = O ( log n B + log ( 1/ η )) . With public seed y ∈ { 0 , 1 } d B y \in\{0,1\}^{d_B} y ∈ { 0 , 1 } d B
Ext ( x ; y ) = H L ( x Z , F ( x B , y ) ) . \operatorname{Ext}(x;y)=H_L(x_Z,F(x_B,y)). Ext ( x ; y ) = H L ( x Z , F ( x B , y )) . Correctness. Fix a normalized cq source ρ B Z E \rho_{BZE} ρ B Z E H min ( B Z ∣ E ) ≥ n − a H_{\min}(BZ\mid E)\ge n-a H m i n ( B Z ∣ E ) ≥ n − a B B B Z Z Z n B n_B n B L L L C 0 C_0 C 0 (16) give
H min ( B ∣ Z E ) ≥ n B − a ≥ 3 n B / 4 , H min ( Z ∣ E ) ≥ L − a . H_{\min}(B\mid ZE)\ge n_B-a\ge3n_B/4,\qquad H_{\min}(Z\mid E)\ge L-a. H m i n ( B ∣ Z E ) ≥ n B − a ≥ 3 n B /4 , H m i n ( Z ∣ E ) ≥ L − a . Take Y ∼ U d B Y\sim U_{d_B} Y ∼ U d B B Z E BZE B Z E W = F ( B , Y ) W=F(B,Y) W = F ( B , Y ) V = H L ( Z , W ) V=H_L(Z,W) V = H L ( Z , W ) V V V U ∼ U d H U\sim U_{d_H} U ∼ U d H B Z Y E BZY E B Z Y E V ′ = H L ( Z , U ) V'=H_L(Z,U) V ′ = H L ( Z , U ) V V V V ′ V' V ′ W W W U U U
The strong guarantee of F F F B B B Z E ZE Z E
Δ ( ρ W Z Y E , ρ U Z Y E ) ≤ η ^ / 2 , ρ U Z Y E = τ d H ⊗ ρ Z Y E . \Delta(\rho_{WZYE},\rho_{UZYE})\le\widehat{\eta}/2,\qquad\rho_{UZYE}=\tau_{d_H}\otimes\rho_{ZYE}. Δ ( ρ W Z Y E , ρ U Z Y E ) ≤ η /2 , ρ U Z Y E = τ d H ⊗ ρ Z Y E . Apply H L H_L H L Z Z Z
Δ ( ρ V Y E , ρ V ′ Y E ) ≤ η ^ / 2. (47) \Delta(\rho_{VYE},\rho_{V'YE})\le\widehat{\eta}/2. \tag*{(47)} Δ ( ρ V Y E , ρ V ′ Y E ) ≤ η /2. (47) It remains to bound the distance of V ′ V' V ′ Y Y Y H min ( Z ∣ Y E ) = H min ( Z ∣ E ) ≥ L − a H_{\min}(Z\mid YE)=H_{\min}(Z\mid E)\ge L-a H m i n ( Z ∣ Y E ) = H m i n ( Z ∣ E ) ≥ L − a U U U Z Y E ZYE Z Y E H L H_L H L Z Z Z Y E YE Y E U U U
Δ ( ρ V ′ Y E , τ m ⊗ ρ Y E ) ≤ η ^ / 2. (48) \Delta(\rho_{V'YE},\tau_m\otimes\rho_{YE})\le\widehat{\eta}/2. \tag*{(48)} Δ ( ρ V ′ Y E , τ m ⊗ ρ Y E ) ≤ η /2. (48) Combining (47) and (48) by the triangle inequality gives
Δ ( ρ V Y E , τ m ⊗ ρ Y E ) ≤ Δ ( ρ V Y E , ρ V ′ Y E ) + Δ ( ρ V ′ Y E , τ m ⊗ ρ Y E ) ≤ η ^ ≤ η . \begin{aligned}
\Delta(\rho_{VYE},\tau_m\otimes\rho_{YE})
&\le\Delta(\rho_{VYE},\rho_{V'YE})+\Delta(\rho_{V'YE},\tau_m\otimes\rho_{YE})\\
&\le\widehat{\eta}\le\eta.
\end{aligned} Δ ( ρ V Y E , τ m ⊗ ρ Y E ) ≤ Δ ( ρ V Y E , ρ V ′ Y E ) + Δ ( ρ V ′ Y E , τ m ⊗ ρ Y E ) ≤ η ≤ η . Since ρ Y E = τ d B ⊗ ρ E \rho_{YE}=\tau_{d_B}\otimes\rho_E ρ Y E = τ d B ⊗ ρ E d B = O ( log n B + log ( 1 / η ^ ) ) = O ( log a + log ( 1 / η ^ ) ) d_B=O(\log n_B+\log(1/\widehat{\eta}))=O(\log a+\log(1/\widehat{\eta})) d B = O ( log n B + log ( 1/ η )) = O ( log a + log ( 1/ η )) n − m = n B + ⌈ C F ( a + log ( 1 / η ^ ) ) ⌉ = O ( a + log ( 1 / η ^ ) ) n-m=n_B+\lceil C_F(a+\log(1/\widehat{\eta}))\rceil=O(a+\log(1/\widehat{\eta})) n − m = n B + ⌈ C F ( a + log ( 1/ η ))⌉ = O ( a + log ( 1/ η )) F F F H L H_L H L
Seed-length refinement by limited independence
We next reduce the seed length of the extractor in Lemma 6.3, at the cost of a larger output loss.
Theorem 6.4 (Seed length versus output loss). *For every integer N ≥ 1 N\ge1 N ≥ 1 0 ≤ k ≤ N 0\le k\le N 0 ≤ k ≤ N 0 < η < 1 / 4 0<\eta<1/4 0 < η < 1/4 ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 ( k , η ) (k,\eta) ( k , η ) Ext : { 0 , 1 } N × { 0 , 1 } d → { 0 , 1 } m \operatorname{Ext}:\{0,1\}^{N}\times\{0,1\}^{d}\to\{0,1\}^{m} Ext : { 0 , 1 } N × { 0 , 1 } d → { 0 , 1 } m a = N − k a=N-k a = N − k
d ≤ 2 log ( 1 / η ) + log ℓ + a ℓ + 5 , (49) d\le2\log(1/\eta)+\log\ell+\frac{a}{\ell}+5, \tag*{(49)} d ≤ 2 log ( 1/ η ) + log ℓ + ℓ a + 5 , (49) m ≥ N − O ( a + log ( 1 / η ) + ℓ [ log a + log ( 1 / η ) + log ℓ ] ) . (50) m\ge N-O\bigl(a+\log(1/\eta)+\ell[\log a+\log(1/\eta)+\log\ell]\bigr). \tag*{(50)} m ≥ N − O ( a + log ( 1/ η ) + ℓ [ log a + log ( 1/ η ) + log ℓ ] ) . (50) *The map Ext \operatorname{Ext} Ext N + log ( 1 / η ) + ℓ N+\log(1/\eta)+\ell N + log ( 1/ η ) + ℓ
Proof. Construction. Let d 0 = O ( log a + log ( 1 / η ) ) d_0 = O(\log a + \log(1/\eta)) d 0 = O ( log a + log ( 1/ η )) a a a η / 2 \eta/2 η /2 t t t d 0 d_0 d 0 d = log t d = \log t d = log t t = 2 d t = 2^d t = 2 d 12 ℓ η − 2 2 a / ℓ 12\ell\eta^{-2}2^{a/\ell} 12 ℓ η − 2 2 a / ℓ
We generate the candidate seeds by evaluating a polynomial over F 2 w \mathbb{F}_{2^w} F 2 w t t t d 0 d_0 d 0 w w w max { d 0 , d } \max\{d_0,d\} max { d 0 , d } 2 ℓ − 1 2\ell- 1 2 ℓ − 1 2 ℓ 2\ell 2 ℓ s = 2 ℓ w s = 2\ell w s = 2 ℓ w
Put n = N − s n = N - s n = N − s n < max { 1 , a } n < \max\{1,a\} n < max { 1 , a } ( x , z ) ∈ { 0 , 1 } n × { 0 , 1 } s (x,z) \in\{0,1\}^n \times\{0,1\}^s ( x , z ) ∈ { 0 , 1 } n × { 0 , 1 } s n n n d 0 d_0 d 0 ( n − a , η / 2 ) (n-a,\eta/2) ( n − a , η /2 )
Ext 0 : { 0 , 1 } n × { 0 , 1 } d 0 → { 0 , 1 } m . \operatorname{Ext}_0 : \{0,1\}^n \times\{0,1\}^{d_0} \to\{0,1\}^m. Ext 0 : { 0 , 1 } n × { 0 , 1 } d 0 → { 0 , 1 } m . Following Xun and Zuckerman [XZ25, Section 1.6.1], use z z z F 2 w \mathbb{F}_{2^w} F 2 w z z z 2 ℓ 2\ell 2 ℓ z 0 , … , z 2 ℓ − 1 z_0,\ldots,z_{2\ell-1} z 0 , … , z 2 ℓ − 1
p z ( u ) = ∑ q = 0 2 ℓ − 1 z q u q . p_z(u) = \sum_{q=0}^{2\ell-1} z_q u^q. p z ( u ) = q = 0 ∑ 2 ℓ − 1 z q u q . For each j ∈ [ t ] j \in[t] j ∈ [ t ] u j ∈ F 2 w u_j \in\mathbb{F}_{2^w} u j ∈ F 2 w j − 1 j-1 j − 1 π d 0 : F 2 w → { 0 , 1 } d 0 \pi_{d_0} : \mathbb{F}_{2^w} \to\{0,1\}^{d_0} π d 0 : F 2 w → { 0 , 1 } d 0 d 0 d_0 d 0
G : { 0 , 1 } s × [ t ] → { 0 , 1 } d 0 , G ( z , j ) = π d 0 ( p z ( u j ) ) . G : \{0,1\}^s \times[t] \to\{0,1\}^{d_0}, \qquad G(z,j) = \pi_{d_0}(p_z(u_j)). G : { 0 , 1 } s × [ t ] → { 0 , 1 } d 0 , G ( z , j ) = π d 0 ( p z ( u j )) . The public seed is a uniform j ∈ [ t ] j \in[t] j ∈ [ t ]
Ext ( ( x , z ) ; j ) = Ext 0 ( x ; G ( z , j ) ) . \operatorname{Ext}((x,z);j) = \operatorname{Ext}_0(x;G(z,j)). Ext (( x , z ) ; j ) = Ext 0 ( x ; G ( z , j )) . Correctness. Since 2 w ≥ t 2^w \ge t 2 w ≥ t z ∼ U s z \sim U_s z ∼ U s 2 ℓ 2\ell 2 ℓ p z p_z p z π d 0 \pi_{d_0} π d 0 G ( U s , 1 ) , … , G ( U s , t ) G(U_s,1),\ldots,G(U_s,t) G ( U s , 1 ) , … , G ( U s , t ) 2 ℓ 2\ell 2 ℓ Ext ( ( x , z ) ; j ) = Ext 0 ( x ; G ( z , j ) ) \operatorname{Ext}((x,z);j) = \operatorname{Ext}_0(x;G(z,j)) Ext (( x , z ) ; j ) = Ext 0 ( x ; G ( z , j ))
Claim. Let Ext 0 : { 0 , 1 } n × { 0 , 1 } d 0 → { 0 , 1 } m \operatorname{Ext}_0 : \{0,1\}^n \times\{0,1\}^{d_0} \to\{0,1\}^m Ext 0 : { 0 , 1 } n × { 0 , 1 } d 0 → { 0 , 1 } m ( n − a , η 0 ) (n-a,\eta_0) ( n − a , η 0 ) G : { 0 , 1 } s × [ t ] → { 0 , 1 } d 0 G : \{0,1\}^s \times[t] \to\{0,1\}^{d_0} G : { 0 , 1 } s × [ t ] → { 0 , 1 } d 0 G ( U s , 1 ) , … , G ( U s , t ) G(U_s,1),\ldots,G(U_s,t) G ( U s , 1 ) , … , G ( U s , t ) 2 ℓ 2\ell 2 ℓ t ≥ ℓ t \ge\ell t ≥ ℓ Ext : { 0 , 1 } n + s × [ t ] → { 0 , 1 } m \operatorname{Ext} : \{0,1\}^{n+s} \times[t] \to\{0,1\}^m Ext : { 0 , 1 } n + s × [ t ] → { 0 , 1 } m Ext ( ( x , z ) ; j ) = Ext 0 ( x ; G ( z , j ) ) \operatorname{Ext}((x,z);j) = \operatorname{Ext}_0(x;G(z,j)) Ext (( x , z ) ; j ) = Ext 0 ( x ; G ( z , j )) ( n + s − a , η ) (n+s-a,\eta) ( n + s − a , η )
η = η 0 + 2 a / ( 2 ℓ ) 3 ℓ t . (51) \eta= \eta_0 + 2^{a/(2\ell)}\sqrt{\frac{3\ell}{t}}. \tag*{(51)} η = η 0 + 2 a / ( 2 ℓ ) t 3 ℓ . (51) Proof of the claim. Fix a normalized cq state ρ X Z E \rho_{XZE} ρ X Z E H min ( X Z ∣ E ) ≥ n + s − a H_{\min}(XZ \mid E) \ge n+s-a H m i n ( X Z ∣ E ) ≥ n + s − a ρ E x z \rho_E^{xz} ρ E x z ρ X Z E \rho_{XZE} ρ X Z E (13) , there is a normalized state ω E \omega_E ω E
ρ E x z ⪯ 2 a − n − s ω E for every x , z . (52) \rho_E^{xz} \preceq2^{a-n-s}\omega_E \quad\text{for every }x,z. \tag*{(52)} ρ E x z ⪯ 2 a − n − s ω E for every x , z . (52) Summing over z z z ρ E x : = ∑ z ρ E x z ⪯ 2 a − n ω E \rho_E^x := \sum_z \rho_E^{xz} \preceq2^{a-n}\omega_E ρ E x := ∑ z ρ E x z ⪯ 2 a − n ω E H min ( X ∣ E ) ≥ n − a H_{\min}(X \mid E) \ge n-a H m i n ( X ∣ E ) ≥ n − a
Let J J J [ t ] [t] [ t ] X Z E XZE X Z E ρ V J E \rho_{VJE} ρ V J E V = Ext 0 ( X ; G ( Z , J ) ) V = \operatorname{Ext}_0(X;G(Z,J)) V = Ext 0 ( X ; G ( Z , J )) J J J E E E σ V J E \sigma_{VJE} σ V J E G ( Z , J ) G(Z,J) G ( Z , J ) R ∼ U d 0 R \sim U_{d_0} R ∼ U d 0 X Z E J XZEJ X Z E J V V V Ext 0 ( X ; R ) \operatorname{Ext}_0(X;R) Ext 0 ( X ; R ) σ V J E \sigma_{VJE} σ V J E J J J V E VE V E Ext 0 \operatorname{Ext}_0 Ext 0
Δ ( σ V J E , τ m ⊗ τ [ t ] ⊗ ρ E ) ≤ η 0 . \Delta(\sigma_{VJE},\tau_m\otimes\tau_{[t]}\otimes\rho_E)\le\eta_0. Δ ( σ V J E , τ m ⊗ τ [ t ] ⊗ ρ E ) ≤ η 0 . We next compare ρ V J E \rho_{VJE} ρ V J E σ V J E \sigma_{VJE} σ V J E j j j y y y { M j , y , I − M j , y } \{M_{j,y},I-M_{j,y}\} { M j , y , I − M j , y } E E E 0 ⪯ M j , y ⪯ I 0\preceq M_{j,y}\preceq I 0 ⪯ M j , y ⪯ I M j , y M_{j,y} M j , y x x x
A x , j ( z ) = M j , Ext 0 ( x ; G ( z , j ) ) − E r ∼ U d 0 M j , Ext 0 ( x ; r ) , A_{x,j}(z)=M_{j,\operatorname{Ext}_0(x;G(z,j))}-\mathbb{E}_{r\sim U_{d_0}}M_{j,\operatorname{Ext}_0(x;r)}, A x , j ( z ) = M j , Ext 0 ( x ; G ( z , j )) − E r ∼ U d 0 M j , Ext 0 ( x ; r ) , B x ( z ) = 1 t ∑ j = 1 t A x , j ( z ) . (53) B_x(z)=\frac{1}{t}\sum_{j=1}^{t}A_{x,j}(z). \tag*{(53)} B x ( z ) = t 1 j = 1 ∑ t A x , j ( z ) . (53) By (53) , the difference between the acceptance probabilities of the measurements { M j , y , I − M j , y } \{M_{j,y},I-M_{j,y}\} { M j , y , I − M j , y } ρ V J E \rho_{VJE} ρ V J E σ V J E \sigma_{VJE} σ V J E
∑ x , z Tr ( ρ E x z B x ( z ) ) . \sum_{x,z}\operatorname{Tr}(\rho_E^{xz}B_x(z)). x , z ∑ Tr ( ρ E x z B x ( z )) . Fix x x x 2 ℓ 2\ell 2 ℓ B x ( z ) B_x(z) B x ( z ) z ∼ U s z\sim U_s z ∼ U s z ∼ U s z\sim U_s z ∼ U s A x , j ( z ) A_{x,j}(z) A x , j ( z ) 2 ℓ 2\ell 2 ℓ A x , j ( z ) A_{x,j}(z) A x , j ( z ) t 2 ℓ ∥ E z B x ( z ) 2 ℓ ∥ t^{2\ell}\left\|\mathbb{E}_zB_x(z)^{2\ell}\right\| t 2 ℓ E z B x ( z ) 2 ℓ A x , j 1 ⋯ A x , j 2 ℓ A_{x,j_1}\cdots A_{x,j_{2\ell}} A x , j 1 ⋯ A x , j 2 ℓ j j j A x , j 1 ⋯ A x , j 2 ℓ A_{x,j_1}\cdots A_{x,j_{2\ell}} A x , j 1 ⋯ A x , j 2 ℓ A x , j A_{x,j} A x , j ℓ \ell ℓ
t 2 ℓ ∥ E z B x ( z ) 2 ℓ ∥ ≤ ∑ q = 1 ℓ ( t q ) q 2 ℓ ≤ ∑ q = 1 ℓ t q q 2 ℓ q ! ≤ t ℓ ℓ ℓ ∑ q = 1 ℓ ℓ q q ! ≤ ( 3 ℓ t ) ℓ . (54) \begin{aligned}
t^{2\ell}\left\|\mathbb{E}_zB_x(z)^{2\ell}\right\|
\le\sum_{q=1}^{\ell}\binom{t}{q}q^{2\ell}
\le\sum_{q=1}^{\ell}\frac{t^qq^{2\ell}}{q!} \\
&\le t^\ell\ell^\ell\sum_{q=1}^{\ell}\frac{\ell^q}{q!}
\le(3\ell t)^\ell. \tag*{(54)}
\end{aligned} t 2 ℓ E z B x ( z ) 2 ℓ ≤ q = 1 ∑ ℓ ( q t ) q 2 ℓ ≤ q = 1 ∑ ℓ q ! t q q 2 ℓ ≤ t ℓ ℓ ℓ q = 1 ∑ ℓ q ! ℓ q ≤ ( 3 ℓ t ) ℓ . (54) The third inequality in (54) uses t ≥ ℓ t\ge\ell t ≥ ℓ B x ( z ) 2 ℓ ⪰ 0 B_x(z)^{2\ell}\succeq0 B x ( z ) 2 ℓ ⪰ 0 (54) gives
0 ⪯ E z ∼ U s B x ( z ) 2 ℓ ⪯ ( 3 ℓ t ) ℓ I . (55) 0\preceq\mathbb{E}_{z\sim U_s}B_x(z)^{2\ell}\preceq\left(\frac{3\ell}{t}\right)^\ell I. \tag*{(55)} 0 ⪯ E z ∼ U s B x ( z ) 2 ℓ ⪯ ( t 3 ℓ ) ℓ I . (55) Since ∑ x , z Tr ρ E x z = 1 \sum_{x,z}\operatorname{Tr}\rho_E^{xz}=1 ∑ x , z Tr ρ E x z = 1 (52) and (55) , gives
∣ ∑ x , z Tr ( ρ E x z B x ( z ) ) ∣ ≤ ( ∑ x , z Tr ( ρ E x z B x ( z ) 2 ℓ ) ) 1 / ( 2 ℓ ) ≤ ( 2 a E x ∼ U n , z ∼ U s Tr ( ω E B x ( z ) 2 ℓ ) ) 1 / ( 2 ℓ ) \begin{aligned}
\left|\sum_{x,z}\operatorname{Tr}(\rho_E^{xz}B_x(z))\right|
\le\left(\sum_{x,z}\operatorname{Tr}(\rho_E^{xz}B_x(z)^{2\ell})\right)^{1/(2\ell)} \\
&\le\left(2^a\mathbb{E}_{x\sim U_n,z\sim U_s}\operatorname{Tr}(\omega_EB_x(z)^{2\ell})\right)^{1/(2\ell)}
\end{aligned} x , z ∑ Tr ( ρ E x z B x ( z )) ≤ ( x , z ∑ Tr ( ρ E x z B x ( z ) 2 ℓ ) ) 1/ ( 2 ℓ ) ≤ ( 2 a E x ∼ U n , z ∼ U s Tr ( ω E B x ( z ) 2 ℓ ) ) 1/ ( 2 ℓ ) ≤ 2 a / ( 2 ℓ ) 3 ℓ t . \le2^{a/(2\ell)}\sqrt{\frac{3\ell}{t}}. ≤ 2 a / ( 2 ℓ ) t 3 ℓ . Maximizing over the matrices 0 ⪯ M j , y ⪯ I 0\preceq M_{j,y}\preceq I 0 ⪯ M j , y ⪯ I Δ ( ρ V J E , σ V J E ) ≤ 2 a / ( 2 ℓ ) 3 ℓ / t \Delta(\rho_{VJE},\sigma_{VJE})\le2^{a/(2\ell)}\sqrt{3\ell/t} Δ ( ρ V J E , σ V J E ) ≤ 2 a / ( 2 ℓ ) 3 ℓ / t (51) . ▫
For the constructed Ext 0 \operatorname{Ext}_0 Ext 0 G G G η 0 = η / 2 \eta_0=\eta/2 η 0 = η /2 t ≥ 12 ℓ η − 2 2 a / ℓ t\ge12\ell\eta^{-2}2^{a/\ell} t ≥ 12 ℓ η − 2 2 a / ℓ (51) therefore bounds the total error by η \eta η
Parameters. Rounding t t t
d < 2 log ( 1 / η ) + log ℓ + a ℓ + log 12 + 1 < 2 log ( 1 / η ) + log ℓ + a ℓ + 5. d<2\log(1/\eta)+\log\ell+\frac{a}{\ell}+\log12+1<2\log(1/\eta)+\log\ell+\frac{a}{\ell}+5. d < 2 log ( 1/ η ) + log ℓ + ℓ a + log 12 + 1 < 2 log ( 1/ η ) + log ℓ + ℓ a + 5. The block Z Z Z s = 2 ℓ w s=2\ell w s = 2 ℓ w w < 2 max { d 0 , d } w<2\max\{d_0,d\} w < 2 max { d 0 , d }
s = 2 ℓ w < 4 ℓ max { d 0 , d } = O ( a + ℓ [ log a + log ( 1 / η ) + log ℓ ] ) . s=2\ell w<4\ell\max\{d_0,d\}=O\left(a+\ell[\log a+\log(1/\eta)+\log\ell]\right). s = 2 ℓ w < 4 ℓ max { d 0 , d } = O ( a + ℓ [ log a + log ( 1/ η ) + log ℓ ] ) . The total output loss is N − m = s + ( n − m ) N-m=s+(n-m) N − m = s + ( n − m ) n − m = O ( a + log ( 1 / η ) ) n-m=O(a+\log(1/\eta)) n − m = O ( a + log ( 1/ η )) Ext 0 \operatorname{Ext}_0 Ext 0 (50) . The same bound holds when N − s < max { 1 , a } N-s<\max\{1,a\} N − s < max { 1 , a } N < s + max { 1 , a } N<s+\max\{1,a\} N < s + max { 1 , a } (50) sufficiently large makes its right-hand side nonpositive.
Computing Ext ( ( x , z ) ; j ) \operatorname{Ext}((x,z);j) Ext (( x , z ) ; j ) Ext 0 \operatorname{Ext}_0 Ext 0 [44 ] , the running time is polynomial in N + log ( 1 / η ) + ℓ N+\log(1/\eta)+\ell N + log ( 1/ η ) + ℓ
Proof of Theorem 1.7. Put a = n − k a=n-k a = n − k 0 < η < 1 / 4 0<\eta<1/4 0 < η < 1/4 N = n N=n N = n k k k h = log a + log ( 1 / η ) h=\log a+\log(1/\eta) h = log a + log ( 1/ η )
ℓ = max { 1 , ⌈ a α h ⌉ } . \ell=\max\left\{1,\left\lceil\frac{a}{\alpha h}\right\rceil\right\}. ℓ = max { 1 , ⌈ α h a ⌉ } . We have a / ℓ ≤ α h a/\ell\le\alpha h a / ℓ ≤ α h ℓ h ≤ a / α + h \ell h\le a/\alpha+h ℓ h ≤ a / α + h log ℓ ≤ log a + O α ( 1 ) \log\ell\le\log a+O_\alpha(1) log ℓ ≤ log a + O α ( 1 ) (49) and (50) gives
d ≤ ( 1 + α ) log a + ( 2 + α ) log ( 1 / η ) + O α ( 1 ) , d\le(1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1), d ≤ ( 1 + α ) log a + ( 2 + α ) log ( 1/ η ) + O α ( 1 ) , n − m = O α ( a + log ( 1 / η ) + ℓ h ) = O α ( a + log ( 1 / η ) ) . n-m=O_\alpha(a+\log(1/\eta)+\ell h)=O_\alpha(a+\log(1/\eta)). n − m = O α ( a + log ( 1/ η ) + ℓ h ) = O α ( a + log ( 1/ η )) . Since ℓ = O α ( n ) \ell=O_\alpha(n) ℓ = O α ( n ) 1 / 4 ≤ η ≤ 1 / 2 1/4\le\eta\le1/2 1/4 ≤ η ≤ 1/2 1 / 8 1/8 1/8 O α ( 1 ) O_\alpha(1) O α ( 1 )
Strong Matrix Samplers
From extractors to samplers
Fix m m m D ≥ 1 D\ge1 D ≥ 1 0 < δ ≤ ε ≤ 1 / 2 0<\delta\le\varepsilon\le1/2 0 < δ ≤ ε ≤ 1/2 Λ = log ( 2 D / δ ) \Lambda=\log(2D/\delta) Λ = log ( 2 D / δ ) a = ⌈ Λ ⌉ a=\lceil\Lambda\rceil a = ⌈ Λ ⌉ 1 ≤ ℓ ≤ a 1\le\ell\le a 1 ≤ ℓ ≤ a a a a ε / 4 \varepsilon/4 ε /4
N = m + ⌈ C 0 ( Λ + ℓ log ( Λ / ε ) ) ⌉ , N=m+\left\lceil C_0\left(\Lambda+\ell\log(\Lambda/\varepsilon)\right)\right\rceil, N = m + ⌈ C 0 ( Λ + ℓ log ( Λ/ ε ) ) ⌉ , where C 0 C_0 C 0 ( N − a , ε / 4 ) (N-a,\varepsilon/4) ( N − a , ε /4 ) F : { 0 , 1 } N × { 0 , 1 } d → { 0 , 1 } m F:\{0,1\}^{N}\times\{0,1\}^{d}\to\{0,1\}^{m} F : { 0 , 1 } N × { 0 , 1 } d → { 0 , 1 } m (23) , the map Samp ( x , y ) = F ( x , y ) \operatorname{Samp}(x,y)=F(x,y) Samp ( x , y ) = F ( x , y ) D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε )
r = N = m + O ( Λ + ℓ log ( Λ / ε ) ) . (56) r=N=m+O\left(\Lambda+\ell\log(\Lambda/\varepsilon)\right). \tag*{(56)} r = N = m + O ( Λ + ℓ log ( Λ/ ε ) ) . (56) t = 2 d = O ( ε − 2 ℓ 2 Λ / ℓ ) . (57) t=2^d=O\left(\varepsilon^{-2}\ell2^{\Lambda/\ell}\right). \tag*{(57)} t = 2 d = O ( ε − 2 ℓ 2 Λ/ ℓ ) . (57) Each sample is computable by one evaluation of F F F m + Λ + log ( 1 / ε ) m+\Lambda+\log(1/\varepsilon) m + Λ + log ( 1/ ε )
Proof of Theorem 1.6. Put h = log a + log ( 1 / ε ) h=\log a+\log(1/\varepsilon) h = log a + log ( 1/ ε )
ℓ = min { a , ⌊ a α h ⌋ } . \ell=\min\left\{a,\left\lfloor\frac{a}{\alpha h}\right\rfloor\right\}. ℓ = min { a , ⌊ α h a ⌋ } . Since h ≤ 2 a h\le2a h ≤ 2 a ℓ = O α ( a / h ) \ell=O_{\alpha}(a/h) ℓ = O α ( a / h ) Λ / ℓ ≤ max { 1 , α h } \Lambda/\ell\le\max\{1,\alpha h\} Λ/ ℓ ≤ max { 1 , α h }
ℓ = O α ( Λ log ( Λ / ε ) ) , 2 Λ / ℓ = O α ( Λ α ε − α ) . \ell=O_{\alpha}\left(\frac{\Lambda}{\log(\Lambda/\varepsilon)}\right),\qquad2^{\Lambda/\ell}=O_{\alpha}\left(\Lambda^{\alpha}\varepsilon^{-\alpha}\right). ℓ = O α ( log ( Λ/ ε ) Λ ) , 2 Λ/ ℓ = O α ( Λ α ε − α ) . Substituting into (56) –(57) gives (3) .
Corollary 7.1. Fix α > 0 \alpha>0 α > 0 m m m D ≥ 1 D\ge1 D ≥ 1 0 < δ ≤ ε ≤ 1 / 2 0<\delta\le\varepsilon\le1/2 0 < δ ≤ ε ≤ 1/2 Λ = log ( 2 D / δ ) \Lambda=\log(2D/\delta) Λ = log ( 2 D / δ ) D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m \operatorname{Samp}:\{0,1\}^{r}\times[t]\to\{0,1\}^{m} Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m
r = m + O α ( Λ [ 1 + log ( 1 / ε ) log Λ ] ) , t = O α ( ε − 2 Λ 1 + α log Λ ) . r=m+O_{\alpha}\left(\Lambda\left[1+\frac{\log(1/\varepsilon)}{\log\Lambda}\right]\right),\qquad t=O_{\alpha}\left(\frac{\varepsilon^{-2}\Lambda^{1+\alpha}}{\log\Lambda}\right). r = m + O α ( Λ [ 1 + log Λ log ( 1/ ε ) ] ) , t = O α ( log Λ ε − 2 Λ 1 + α ) . For every fixed C > 0 C>0 C > 0 ε ≥ Λ − C \varepsilon\ge\Lambda^{-C} ε ≥ Λ − C r = m + O α , C ( Λ ) r=m+O_{\alpha,C}(\Lambda) r = m + O α , C ( Λ ) α \alpha α Samp ( x , i ) \operatorname{Samp}(x,i) Samp ( x , i ) x ∈ { 0 , 1 } r x\in\{0,1\}^{r} x ∈ { 0 , 1 } r i ∈ [ t ] i\in[t] i ∈ [ t ] m + Λ + log ( 1 / ε ) m+\Lambda+\log(1/\varepsilon) m + Λ + log ( 1/ ε )
Proof. In (56) –(57) , take
ℓ = min { ⌈ Λ ⌉ , ⌈ Λ α log Λ ⌉ } . \ell=\min\left\{\lceil\Lambda\rceil,\left\lceil\frac{\Lambda}{\alpha\log\Lambda}\right\rceil\right\}. ℓ = min { ⌈ Λ ⌉ , ⌈ α log Λ Λ ⌉ } . Then ℓ = O α ( Λ / log Λ ) \ell=O_{\alpha}(\Lambda/\log\Lambda) ℓ = O α ( Λ/ log Λ ) 2 Λ / ℓ ≤ 2 Λ α 2^{\Lambda/\ell}\le2\Lambda^{\alpha} 2 Λ/ ℓ ≤ 2 Λ α ε ≥ Λ − C \varepsilon\ge\Lambda^{-C} ε ≥ Λ − C log ( 1 / ε ) ≤ C log Λ \log(1/\varepsilon)\le C\log\Lambda log ( 1/ ε ) ≤ C log Λ
Lower bounds
Lemma 7.2. Let m , D ≥ 1 m,D\ge1 m , D ≥ 1 0 < δ , ε < 1 0<\delta,\varepsilon<1 0 < δ , ε < 1 D D D ( δ , ε ) (\delta,\varepsilon) ( δ , ε ) Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m \operatorname{Samp}:\{0,1\}^{r}\times[t]\to\{0,1\}^{m} Samp : { 0 , 1 } r × [ t ] → { 0 , 1 } m
r ≥ m + log D + log ( 1 / δ ) − 1. r\ge m+\log D+\log(1/\delta)-1. r ≥ m + log D + log ( 1/ δ ) − 1. If 0 < δ ≤ ε ≤ 1 / 2 0<\delta\le\varepsilon\le1/2 0 < δ ≤ ε ≤ 1/2
t = Ω ( ε − 2 log ( D / δ ) ) . t=\Omega\left(\varepsilon^{-2}\log(D/\delta)\right). t = Ω ( ε − 2 log ( D / δ ) ) . Proof. Partition a set of min { M , D q } \min\{M,Dq\} min { M , D q } D D D B 1 , … , B D B_1,\ldots,B_D B 1 , … , B D ⌊ min { M / D , q } ⌋ \lfloor\min\{M/D,q\}\rfloor ⌊ min { M / D , q }⌋ ⌈ min { M / D , q } ⌉ \lceil\min\{M/D,q\}\rceil ⌈ min { M / D , q }⌉ i ∈ [ t ] i\in[t] i ∈ [ t ] f i f_i f i
A i j = { Samp ( x , i ) : x ∈ B j } , ( f i ( z ) ) j j = 21 A i j ( z ) − 1 ( j ∈ [ D ] ) . A_{ij}=\{\operatorname{Samp}(x,i):x\in B_j\},\qquad(f_i(z))_{jj}=2\mathbf{1}_{A_{ij}}(z)-1\quad(j\in[D]). A ij = { Samp ( x , i ) : x ∈ B j } , ( f i ( z ) ) j j = 2 1 A ij ( z ) − 1 ( j ∈ [ D ]) . Each f i ( z ) f_i(z) f i ( z ) ∣ A i j ∣ ≤ ∣ B j ∣ ≤ 2 m − 1 |A_{ij}|\le|B_j|\le2^{m-1} ∣ A ij ∣ ≤ ∣ B j ∣ ≤ 2 m − 1 x ∈ B j x\in B_j x ∈ B j
( f i ( Samp ( x , i ) ) − E Z ∼ U m f i ( Z ) ) j j = 2 ( 1 − ∣ A i j ∣ 2 m ) ≥ 1. \left(f_i(\operatorname{Samp}(x,i))-\mathbb{E}_{Z\sim U_m}f_i(Z)\right)_{jj}
=2\left(1-\frac{|A_{ij}|}{2^m}\right)\ge1. ( f i ( Samp ( x , i )) − E Z ∼ U m f i ( Z ) ) j j = 2 ( 1 − 2 m ∣ A ij ∣ ) ≥ 1. Thus, for every x ∈ ⋃ j = 1 D B j x\in\bigcup_{j=1}^{D}B_j x ∈ ⋃ j = 1 D B j
∥ 1 t ∑ i = 1 t ( f i ( Samp ( x , i ) ) − E Z ∼ U m f i ( Z ) ) ∥ ≥ 1. \left\|\frac{1}{t}\sum_{i=1}^{t}\left(f_i(\operatorname{Samp}(x,i))-\mathbb{E}_{Z\sim U_m}f_i(Z)\right)\right\|\ge1. t 1 i = 1 ∑ t ( f i ( Samp ( x , i )) − E Z ∼ U m f i ( Z ) ) ≥ 1. Since ε < 1 \varepsilon< 1 ε < 1 ⋃ j B j \bigcup_j B_j ⋃ j B j ε \varepsilon ε
min { 1 , D q M } = ∣ ⋃ j B j ∣ M ≤ Pr X ∼ U r [ ∥ 1 t ∑ i = 1 t ( f i ( Samp ( X , i ) ) − E Z ∼ U m f i ( Z ) ) ∥ > ε ] ≤ δ , \min\left\{1,\frac{Dq}{M}\right\}=\frac{\left|\bigcup_j B_j\right|}{M}
\le\Pr_{X\sim U_r}\left[\left\|\frac{1}{t}\sum_{i=1}^{t}\left(f_i(\operatorname{Samp}(X,i))-\mathbb{E}_{Z\sim U_m}f_i(Z)\right)\right\|>\varepsilon\right]
\le\delta, min { 1 , M D q } = M ⋃ j B j ≤ X ∼ U r Pr [ t 1 i = 1 ∑ t ( f i ( Samp ( X , i )) − E Z ∼ U m f i ( Z ) ) > ε ] ≤ δ , where the last inequality follows from the sampler guarantee. Since δ < 1 \delta< 1 δ < 1 D q / M ≤ δ Dq/M\le\delta D q / M ≤ δ M ≥ D q / δ M\ge Dq/\delta M ≥ D q / δ r ≥ m + log D + log ( 1 / δ ) − 1 r\ge m+\log D+\log(1/\delta)-1 r ≥ m + log D + log ( 1/ δ ) − 1
Sample complexity. Assume 0 < δ ≤ ε ≤ 1 / 2 0<\delta\le\varepsilon\le1/2 0 < δ ≤ ε ≤ 1/2 S s S_s S s s s s p t = Pr [ ∣ S t ∣ > ε t ] p_t=\Pr[|S_t|>\varepsilon t] p t = Pr [ ∣ S t ∣ > εt ] C C C
p t ≤ ε ⟹ log ( 1 / p t ) ≤ C ε 2 t . (58) p_t\le\varepsilon\quad\Longrightarrow\quad\log(1/p_t)\le C\varepsilon^2t. \tag*{(58)} p t ≤ ε ⟹ log ( 1/ p t ) ≤ C ε 2 t . (58) Suppose p t ≤ ε p_t\le\varepsilon p t ≤ ε E S s 2 = s \mathbb{E}S_s^2=s E S s 2 = s E S s 4 ≤ 3 s 2 \mathbb{E}S_s^4\le3s^2 E S s 4 ≤ 3 s 2
Pr [ S s > ε s ] = 1 2 Pr [ ∣ S s ∣ > ε s ] ≥ 3 32 if ε 2 s ≤ 1 4 . (59) \Pr[S_s>\varepsilon s]=\frac{1}{2}\Pr[|S_s|>\varepsilon s]\ge\frac{3}{32}\qquad\text{if }\varepsilon^2s\le\frac{1}{4}. \tag*{(59)} Pr [ S s > ε s ] = 2 1 Pr [ ∣ S s ∣ > ε s ] ≥ 32 3 if ε 2 s ≤ 4 1 . (59) If ε 2 t < 1 / 64 \varepsilon^2t<1/64 ε 2 t < 1/64 ε < 1 / 8 \varepsilon<1/8 ε < 1/8 p t ≥ 3 / 16 p_t\ge3/16 p t ≥ 3/16 p t ≤ ε p_t\le\varepsilon p t ≤ ε ε 2 t ≥ 1 / 64 \varepsilon^2t\ge1/64 ε 2 t ≥ 1/64 ℓ = ⌊ 1 / ( 4 ε 2 ) ⌋ \ell=\lfloor1/(4\varepsilon^2)\rfloor ℓ = ⌊ 1/ ( 4 ε 2 )⌋ t t t v = ⌈ t / ℓ ⌉ ≤ 8 ε 2 t + 1 = O ( ε 2 t ) v=\lceil t/\ell\rceil\le8\varepsilon^2t+1=O(\varepsilon^2t) v = ⌈ t / ℓ ⌉ ≤ 8 ε 2 t + 1 = O ( ε 2 t ) ℓ \ell ℓ ε \varepsilon ε p t ≥ ( 3 / 32 ) v p_t\ge(3/32)^v p t ≥ ( 3/32 ) v (59) . Therefore
log ( 1 / p t ) ≤ v log ( 32 / 3 ) = O ( ε 2 t ) . \log(1/p_t)\le v\log(32/3)=O(\varepsilon^2t). log ( 1/ p t ) ≤ v log ( 32/3 ) = O ( ε 2 t ) . We now apply (58) to the sampler. Choose independent uniform signs ξ i j ∈ { − 1 , 1 } \xi_{ij}\in\{-1,1\} ξ ij ∈ { − 1 , 1 } i ∈ [ t ] i\in[t] i ∈ [ t ] j ∈ [ D ] j\in[D] j ∈ [ D ] z = ( z 1 , … , z m ) z=(z_1,\ldots,z_m) z = ( z 1 , … , z m )
g i ( z ) = ( − 1 ) z 1 diag ( ξ i 1 , … , ξ i D ) . g_i(z)=(-1)^{z_1}\operatorname{diag}(\xi_{i1},\ldots,\xi_{iD}). g i ( z ) = ( − 1 ) z 1 diag ( ξ i 1 , … , ξ i D ) . Every g i g_i g i ∥ g i ( z ) ∥ = 1 \|g_i(z)\|=1 ∥ g i ( z ) ∥ = 1 E Z ∼ U m g i ( Z ) = 0 \mathbb{E}_{Z\sim U_m}g_i(Z)=0 E Z ∼ U m g i ( Z ) = 0 x x x ( − 1 ) Samp ( x , i ) 1 ξ i j (-1)^{\operatorname{Samp}(x,i)_1}\xi_{ij} ( − 1 ) Samp ( x , i ) 1 ξ ij D D D t − 1 ∑ i g i ( Samp ( x , i ) ) t^{-1}\sum_i g_i(\operatorname{Samp}(x,i)) t − 1 ∑ i g i ( Samp ( x , i )) S t / t S_t/t S t / t
For each fixed x x x ξ \xi ξ ε \varepsilon ε 1 − ( 1 − p t ) D 1-(1-p_t)^D 1 − ( 1 − p t ) D ξ \xi ξ X ∼ U r X\sim U_r X ∼ U r δ \delta δ X X X ξ \xi ξ
1 − ( 1 − p t ) D ≤ δ , p t ≤ − ln ( 1 − δ ) D ≤ 2 δ D . (60) 1-(1-p_t)^D\le\delta,\qquad p_t\le\frac{-\ln(1-\delta)}{D}\le\frac{2\delta}{D}. \tag*{(60)} 1 − ( 1 − p t ) D ≤ δ , p t ≤ D − ln ( 1 − δ ) ≤ D 2 δ . (60) The first inequality also gives p t ≤ δ ≤ ε ≤ 1 / 2 p_t\le\delta\le\varepsilon\le1/2 p t ≤ δ ≤ ε ≤ 1/2 (60) and (58) , we obtain
log ( D / δ ) ≤ 1 + log ( 1 / p t ) ≤ 2 log ( 1 / p t ) ≤ 2 C ε 2 t . \log(D/\delta)\le1+\log(1/p_t)\le2\log(1/p_t)\le2C\varepsilon^2t. log ( D / δ ) ≤ 1 + log ( 1/ p t ) ≤ 2 log ( 1/ p t ) ≤ 2 C ε 2 t . Therefore t = Ω ( ε − 2 log ( D / δ ) ) t=\Omega(\varepsilon^{-2}\log(D/\delta)) t = Ω ( ε − 2 log ( D / δ ))
Acknowledgement
AI use We initiated the topics and questions of this work without using AI. The question came to us when we survey the two interesting lines of work, i.e. quantum-proof extractors and matrix samplers. We would like to find the corresponding sampler for quantum-proof extractors and the corresponding extractor for samplers. We also had some general ideas of improving those existing constructions before using AI. Then we discussed with AI and used it substantially to develop the solutions and proofs as well as to do proof checking. The write-up is done by us humans, though we also use AI to polish sentences. We are responsible for the correctness.
References
Proofs for Smooth Min-Entropy
Proof of Lemma 2.1. Put k = H min τ ( X ∣ E ) ρ k = H_{\min}^{\tau}(X \mid E)_{\rho} k = H m i n τ ( X ∣ E ) ρ (18) , choose a subnormalized cq state ρ ~ X E \widetilde{\rho}_{XE} ρ X E
P ( ρ ~ X E , ρ X E ) ≤ τ , H min ( X ∣ E ) ρ ~ = k . P(\widetilde{\rho}_{XE}, \rho_{XE}) \leq\tau, \qquad H_{\min}(X \mid E)_{\widetilde{\rho}} = k. P ( ρ X E , ρ X E ) ≤ τ , H m i n ( X ∣ E ) ρ = k . By the extension property of purified distance [47 Corollary 9] , there is a subnormalized extension ρ ~ X L E \widetilde{\rho}_{XLE} ρ X L E ρ ~ X E \widetilde{\rho}_{XE} ρ X E
Tr L ρ ~ X L E = ρ ~ X E , P ( ρ ~ X L E , ρ X L E ) = P ( ρ ~ X E , ρ X E ) ≤ τ . \operatorname{Tr}_{L} \widetilde{\rho}_{XLE} = \widetilde{\rho}_{XE}, \qquad P(\widetilde{\rho}_{XLE}, \rho_{XLE}) = P(\widetilde{\rho}_{XE}, \rho_{XE}) \leq\tau. Tr L ρ X L E = ρ X E , P ( ρ X L E , ρ X L E ) = P ( ρ X E , ρ X E ) ≤ τ . Delete the off-diagonal blocks in the classical bases of X , L X, L X , L ρ ~ X E \widetilde{\rho}_{XE} ρ X E ρ X L E \rho_{XLE} ρ X L E P ( ρ ~ X L E , ρ X L E ) ≤ τ P(\widetilde{\rho}_{XLE}, \rho_{XLE}) \leq\tau P ( ρ X L E , ρ X L E ) ≤ τ (15) , stated in [15 Lemma B.3] , also holds for subnormalized states. Normalizing a state of trace p p p log p \log p log p (15) to ρ ~ X L E \widetilde{\rho}_{XLE} ρ X L E
H min T ( X ∣ L E ) ρ ≥ H min ( X ∣ L E ) ρ ~ ≥ H min ( X ∣ E ) ρ ~ − log ∣ L ∣ = k − log ∣ L ∣ . \begin{aligned}
H_{\min}^{\mathrm{T}}(X \mid LE)_{\rho} \ge H_{\min}(X \mid LE)_{\widetilde{\rho}} \\
&\ge H_{\min}(X \mid E)_{\widetilde{\rho}}-\log|\mathcal{L}| \\
&= k-\log|\mathcal{L}|.
\end{aligned} H m i n T ( X ∣ L E ) ρ ≥ H m i n ( X ∣ L E ) ρ ≥ H m i n ( X ∣ E ) ρ − log ∣ L ∣ = k − log ∣ L ∣. Proof of Lemma 2.2 . For τ > 1 / 4 \tau> 1/4 τ > 1/4 Lemma 2.2 follows from the upper bound of one on trace distance. Assume 0 ≤ τ ≤ 1 / 4 0 \le\tau\le1/4 0 ≤ τ ≤ 1/4 ρ ~ X E \widetilde{\rho}_{XE} ρ X E P ( ρ ~ X E , ρ X E ) ≤ τ P(\widetilde{\rho}_{XE},\rho_{XE}) \le\tau P ( ρ X E , ρ X E ) ≤ τ H min ( X ∣ E ) ρ ~ ≥ k + 1 H_{\min}(X \mid E)_{\widetilde{\rho}} \ge k+1 H m i n ( X ∣ E ) ρ ≥ k + 1 p = Tr ρ ~ X E p=\operatorname{Tr}\widetilde{\rho}_{XE} p = Tr ρ X E p ≥ 1 − τ 2 ≥ 15 / 16 p \ge1-\tau^2 \ge15/16 p ≥ 1 − τ 2 ≥ 15/16 ρ ^ X E = ρ ~ X E / p \widehat{\rho}_{XE}=\widetilde{\rho}_{XE}/p ρ X E = ρ X E / p
H min ( X ∣ E ) ρ ^ = H min ( X ∣ E ) ρ ~ + log p ≥ k , Δ ( ρ ^ X E , ρ X E ) ≤ τ + 1 − p 2 ≤ 2 τ . H_{\min}(X \mid E)_{\widehat{\rho}}=H_{\min}(X \mid E)_{\widetilde{\rho}}+\log p\ge k,\qquad\Delta(\widehat{\rho}_{XE},\rho_{XE})\le\tau+\frac{1-p}{2}\le2\tau. H m i n ( X ∣ E ) ρ = H m i n ( X ∣ E ) ρ + log p ≥ k , Δ ( ρ X E , ρ X E ) ≤ τ + 2 1 − p ≤ 2 τ . Apply Ext to ρ ^ X E \widehat{\rho}_{XE} ρ X E Y Y Y [15 Lemma 3.5] , contractivity and the triangle inequality give
Δ ( ρ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ E ) ≤ Δ ( ρ ^ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ ^ E ) + 2 Δ ( ρ ^ X E , ρ X E ) ≤ η + 4 τ . \Delta(\rho_{\operatorname{Ext}(X,Y)YE},\tau_m\otimes\tau_d\otimes\rho_E)
\le\Delta(\widehat{\rho}_{\operatorname{Ext}(X,Y)YE},\tau_m\otimes\tau_d\otimes\widehat{\rho}_E)+2\Delta(\widehat{\rho}_{XE},\rho_{XE})\le\eta+4\tau. Δ ( ρ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ E ) ≤ Δ ( ρ Ext ( X , Y ) Y E , τ m ⊗ τ d ⊗ ρ E ) + 2Δ ( ρ X E , ρ X E ) ≤ η + 4 τ . Derivations of the Sampling and Extraction Tools
Entropy sampling with a public seed
Theorem B.1 (Vadhan’s sampler; [Vad04, Lemma 8.4]). There is an absolute constant C > 0 C>0 C > 0 Fix an integer N ≥ 1 N\ge1 N ≥ 1 0 < ε < β < 1 0<\varepsilon<\beta<1 0 < ε < β < 1 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 C ε − 2 log ( 1 / δ ) ≤ t ≤ N C\varepsilon^{-2}\log(1/\delta)\le t\le N C ε − 2 log ( 1/ δ ) ≤ t ≤ N
S : { 0 , 1 } r → ( [ N ] t ) , r ≤ log ( N / t ) + poly ( 1 / ε ) log ( 1 / δ ) . S:\{0,1\}^{r}\to\binom{[N]}{t},\qquad r\le\log(N/t)+\operatorname{poly}(1/\varepsilon)\log(1/\delta). S : { 0 , 1 } r → ( t [ N ] ) , r ≤ log ( N / t ) + poly ( 1/ ε ) log ( 1/ δ ) . For every f : [ N ] → [ 0 , 1 ] f:[N]\to[0,1] f : [ N ] → [ 0 , 1 ] N − 1 ∑ j = 1 N f ( j ) ≥ β N^{-1}\sum_{j=1}^{N}f(j)\ge\beta N − 1 ∑ j = 1 N f ( j ) ≥ β R ∼ U r R\sim U_r R ∼ U r
Pr R [ 1 t ∑ j ∈ S ( R ) f ( j ) < β − ε ] ≤ δ . \Pr_R\left[\frac{1}{t}\sum_{j\in S(R)}f(j)<\beta-\varepsilon\right]\le\delta. R Pr t 1 j ∈ S ( R ) ∑ f ( j ) < β − ε ≤ δ . Corollary B.2 (Distinct samples). Fix 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 C ε > 0 C_{\varepsilon}>0 C ε > 0 Let N ≥ 1 N\ge1 N ≥ 1 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 C ε log ( 1 / δ ) ≤ t ≤ N C_{\varepsilon}\log(1/\delta)\le t\le N C ε log ( 1/ δ ) ≤ t ≤ N S : { 0 , 1 } r → ( [ N ] t ) S:\{0,1\}^{r}\to\binom{[N]}{t} S : { 0 , 1 } r → ( t [ N ] ) r = O ε ( log N + log ( 1 / δ ) ) r=O_{\varepsilon}(\log N+\log(1/\delta)) r = O ε ( log N + log ( 1/ δ )) R ∼ U r R\sim U_r R ∼ U r f : [ N ] → [ 0 , 1 ] f:[N]\to[0,1] f : [ N ] → [ 0 , 1 ]
Pr R [ 1 t ∑ j ∈ S ( R ) f ( j ) ≤ 1 N ∑ j = 1 N f ( j ) − ε ] ≤ δ . (61) \Pr_R\left[\frac{1}{t}\sum_{j\in S(R)}f(j)\le\frac{1}{N}\sum_{j=1}^{N}f(j)-\varepsilon\right]\le\delta. \tag*{(61)} R Pr t 1 j ∈ S ( R ) ∑ f ( j ) ≤ N 1 j = 1 ∑ N f ( j ) − ε ≤ δ . (61) Proof. Choose the sampler in Theorem B.1 with threshold β = 1 / 2 \beta= 1/2 β = 1/2 ε / 4 \varepsilon/4 ε /4 f f f f ˉ = N − 1 ∑ j = 1 N f ( j ) \bar{f} = N^{-1}\sum_{j=1}^{N} f(j) f ˉ = N − 1 ∑ j = 1 N f ( j ) g ( j ) = ( f ( j ) − f ˉ + 1 ) / 2 g(j) = (f(j)-\bar{f}+1)/2 g ( j ) = ( f ( j ) − f ˉ + 1 ) /2 0 ≤ g ≤ 1 0 \le g \le1 0 ≤ g ≤ 1 N − 1 ∑ j = 1 N g ( j ) = 1 / 2 N^{-1}\sum_{j=1}^{N}g(j)=1/2 N − 1 ∑ j = 1 N g ( j ) = 1/2
Pr R [ 1 t ∑ j ∈ S ( R ) f ( j ) ≤ f ˉ − ε ] = Pr R [ 1 t ∑ j ∈ S ( R ) g ( j ) ≤ 1 2 − ε 2 ] ≤ Pr R [ 1 t ∑ j ∈ S ( R ) g ( j ) < 1 2 − ε 4 ] ≤ δ . \begin{aligned}
\Pr_R\left[\frac{1}{t}\sum_{j\in S(R)}f(j)\le\bar{f}-\varepsilon\right]
=
\Pr_R\left[\frac{1}{t}\sum_{j\in S(R)}g(j)\le\frac{1}{2}-\frac{\varepsilon}{2}\right] \\
&\le\Pr_R\left[\frac{1}{t}\sum_{j\in S(R)}g(j)<\frac{1}{2}-\frac{\varepsilon}{4}\right]\le\delta.
\end{aligned} R Pr t 1 j ∈ S ( R ) ∑ f ( j ) ≤ f ˉ − ε = R Pr t 1 j ∈ S ( R ) ∑ g ( j ) ≤ 2 1 − 2 ε ≤ R Pr t 1 j ∈ S ( R ) ∑ g ( j ) < 2 1 − 4 ε ≤ δ . The sample-size and seed-length bounds in Theorem B.1 give the stated parameters.
The entropy-sampling theorem below uses trace-norm smoothing as defined in (19) .
Theorem B.3 (König–Renner entropy sampling; [28 Corollary 6.19] ). Let N , w , t ≥ 1 N,w,t\ge1 N , w , t ≥ 1 t ≤ N t\le N t ≤ N 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 ρ X E \rho_{XE} ρ X E X = ( X 1 , … , X N ) ∈ ( { 0 , 1 } w ) N X=(X_1,\ldots,X_N)\in(\{0,1\}^{w})^N X = ( X 1 , … , X N ) ∈ ({ 0 , 1 } w ) N J J J t t t [ N ] [N] [ N ] X E XE X E
Pr J [ 1 t ∑ j ∈ J f ( j ) ≤ 1 N ∑ j = 1 N f ( j ) − ε ] ≤ δ for every f : [ N ] → [ 0 , 1 ] . \Pr_J\left[\frac{1}{t}\sum_{j\in J}f(j)\le\frac{1}{N}\sum_{j=1}^{N}f(j)-\varepsilon\right]\le\delta
\quad\text{for every }f:[N]\to[0,1]. J Pr t 1 j ∈ J ∑ f ( j ) ≤ N 1 j = 1 ∑ N f ( j ) − ε ≤ δ for every f : [ N ] → [ 0 , 1 ] . Put B = X J B=X_J B = X J
κ = N t w , s = 2 ⋅ 2 − ε N w + 3 δ 1 / 4 . \kappa=\frac{N}{tw},\qquad s=2\cdot2^{-\varepsilon Nw}+3\delta^{1/4}. κ = tw N , s = 2 ⋅ 2 − εN w + 3 δ 1/4 . If κ ≤ 0.15 \kappa\le0.15 κ ≤ 0.15
H min s , ∥ ⋅ ∥ 1 ( B ∣ J E ) ρ w t ≥ H min ( X ∣ E ) ρ N w − 3 ε − 2 κ log ( 1 / κ ) . (62) \frac{H_{\min}^{s,\lVert\cdot\rVert_1}(B\mid JE)_\rho}{wt}
\ge
\frac{H_{\min}(X\mid E)_\rho}{Nw}-3\varepsilon-2\kappa\log(1/\kappa). \tag*{(62)} w t H m i n s , ∥ ⋅ ∥ 1 ( B ∣ J E ) ρ ≥ N w H m i n ( X ∣ E ) ρ − 3 ε − 2 κ log ( 1/ κ ) . (62) Proof of Lemma 5.1 . Choose S S S J = S ( R ) J=S(R) J = S ( R ) s = 2 ⋅ 2 − ε N w + 3 δ 1 / 4 s=2\cdot2^{-\varepsilon Nw}+3\delta^{1/4} s = 2 ⋅ 2 − εN w + 3 δ 1/4 J J J R R R
Φ ( ∣ j ⟩ ⟨ j ∣ ) = ∑ r : S ( r ) = j Pr [ R = r ∣ J = j ] ∣ r ⟩ ⟨ r ∣ ( j ∈ supp ( J ) ) . \Phi(|j\rangle\langle j|)
=
\sum_{r:S(r)=j}\Pr[R=r\mid J=j]|r\rangle\langle r|
\qquad(j\in\operatorname{supp}(J)). Φ ( ∣ j ⟩ ⟨ j ∣ ) = r : S ( r ) = j ∑ Pr [ R = r ∣ J = j ] ∣ r ⟩ ⟨ r ∣ ( j ∈ supp ( J )) . Since R R R X E XE X E B = X J B=X_J B = X J
ρ B E ∣ R = r = ρ B E ∣ J = S ( r ) , Φ J → R ( ρ B J E ) = ρ B R E . \rho_{BE\mid R=r}=\rho_{BE\mid J=S(r)},\qquad
\Phi_{J\to R}(\rho_{BJE})=\rho_{BRE}. ρ B E ∣ R = r = ρ B E ∣ J = S ( r ) , Φ J → R ( ρ B J E ) = ρ B R E . Applying Φ \Phi Φ B B B 2 s ≤ τ 2 2s\le\tau^2 2 s ≤ τ 2 (20) and Theorem B.3 give
H min τ ( B ∣ R E ) ρ ≥ H min s , ∥ ⋅ ∥ 1 ( B ∣ R E ) ρ ≥ H min s , ∥ ⋅ ∥ 1 ( B ∣ J E ) ρ ≥ ( μ − 3 ε − 2 κ log ( 1 / κ ) ) w t . \begin{aligned}
H_{\min}^{\tau}(B\mid RE)_\rho
\ge H_{\min}^{s,\lVert\cdot\rVert_1}(B\mid RE)_\rho\\
&\ge H_{\min}^{s,\lVert\cdot\rVert_1}(B\mid JE)_\rho\\
&\ge\left(\mu-3\varepsilon-2\kappa\log(1/\kappa)\right)wt.
\end{aligned} H m i n τ ( B ∣ R E ) ρ ≥ H m i n s , ∥ ⋅ ∥ 1 ( B ∣ R E ) ρ ≥ H m i n s , ∥ ⋅ ∥ 1 ( B ∣ J E ) ρ ≥ ( μ − 3 ε − 2 κ log ( 1/ κ ) ) w t . Short-seed extraction
Theorem B.4 (Short-seed hashing; [51 Theorem 10] ). For every pair of integers 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n 0 < η 0 ≤ 1 / 2 0 < \eta_0 \le1/2 0 < η 0 ≤ 1/2
H : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m , d ≤ 2 m + O ( log ( n / η 0 ) ) . H : \{0,1\}^{n} \times\{0,1\}^{d} \to\{0,1\}^{m}, \qquad d \le2m + O(\log(n/\eta_0)). H : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m , d ≤ 2 m + O ( log ( n / η 0 )) . For every normalized cq state ρ X E \rho_{XE} ρ X E X ∈ { 0 , 1 } n X \in\{0,1\}^{n} X ∈ { 0 , 1 } n W ∼ U d W \sim U_d W ∼ U d Z = H ( X , W ) Z = H(X,W) Z = H ( X , W )
min σ W E Δ ( ρ Z W E , τ m ⊗ σ W E ) ≤ 3 η 0 + 1 2 2 m − H min η 0 ( X ∣ E ) ρ ( 2 / η 0 2 + 1 ) , (63) \min_{\sigma_{WE}} \Delta(\rho_{ZWE},\tau_m \otimes\sigma_{WE}) \le3\eta_0 + \frac{1}{2}\sqrt{2^{m-H_{\min}^{\eta_0}(X|E)_\rho}(2/\eta_0^2+1)}, \tag*{(63)} σ W E min Δ ( ρ Z W E , τ m ⊗ σ W E ) ≤ 3 η 0 + 2 1 2 m − H m i n η 0 ( X ∣ E ) ρ ( 2/ η 0 2 + 1 ) , (63) where the minimum ranges over normalized states on $WE.
Proof of Lemma 5.2. Apply Theorem B.4 with η 0 = η / 16 \eta_0=\eta/16 η 0 = η /16 ρ X E \rho_{XE} ρ X E k = H min ( X ∣ E ) ρ k=H_{\min}(X\mid E)_\rho k = H m i n ( X ∣ E ) ρ W ∼ U d W\sim U_d W ∼ U d Z = H ( X , W ) Z=H(X,W) Z = H ( X , W ) σ W E \sigma_{WE} σ W E Z Z Z
Δ ( ρ W E , σ W E ) ≤ Δ ( ρ Z W E , τ m ⊗ σ W E ) . \Delta(\rho_{WE},\sigma_{WE}) \le\Delta(\rho_{ZWE},\tau_m \otimes\sigma_{WE}). Δ ( ρ W E , σ W E ) ≤ Δ ( ρ Z W E , τ m ⊗ σ W E ) . The triangle inequality gives
Δ ( ρ Z W E , τ m ⊗ ρ W E ) ≤ Δ ( ρ Z W E , τ m ⊗ σ W E ) + Δ ( τ m ⊗ σ W E , τ m ⊗ ρ W E ) = Δ ( ρ Z W E , τ m ⊗ σ W E ) + Δ ( σ W E , ρ W E ) ≤ 2 Δ ( ρ Z W E , τ m ⊗ σ W E ) . \begin{aligned}
\Delta(\rho_{ZWE},\tau_m \otimes\rho_{WE}) &\le\Delta(\rho_{ZWE},\tau_m \otimes\sigma_{WE})+\Delta(\tau_m \otimes\sigma_{WE},\tau_m \otimes\rho_{WE}) \\
&= \Delta(\rho_{ZWE},\tau_m \otimes\sigma_{WE})+\Delta(\sigma_{WE},\rho_{WE}) \\
&\le2\Delta(\rho_{ZWE},\tau_m \otimes\sigma_{WE}).
\end{aligned} Δ ( ρ Z W E , τ m ⊗ ρ W E ) ≤ Δ ( ρ Z W E , τ m ⊗ σ W E ) + Δ ( τ m ⊗ σ W E , τ m ⊗ ρ W E ) = Δ ( ρ Z W E , τ m ⊗ σ W E ) + Δ ( σ W E , ρ W E ) ≤ 2Δ ( ρ Z W E , τ m ⊗ σ W E ) . Since H min η 0 ( X ∣ E ) ρ ≥ k H_{\min}^{\eta_0}(X\mid E)_\rho\ge k H m i n η 0 ( X ∣ E ) ρ ≥ k
Δ ( ρ Z W E , τ m ⊗ ρ W E ) ≤ 6 η 0 + 2 m − k ( 2 / η 0 2 + 1 ) ≤ η \Delta(\rho_{ZWE},\tau_m \otimes\rho_{WE}) \le6\eta_0+\sqrt{2^{m-k}(2/\eta_0^2+1)} \le\eta Δ ( ρ Z W E , τ m ⊗ ρ W E ) ≤ 6 η 0 + 2 m − k ( 2/ η 0 2 + 1 ) ≤ η whenever k ≥ m + 4 log ( 1 / η ) + 12 k\ge m+4\log(1/\eta)+12 k ≥ m + 4 log ( 1/ η ) + 12 W W W X E XE X E ρ W E = τ d ⊗ ρ E \rho_{WE}=\tau_d\otimes\rho_E ρ W E = τ d ⊗ ρ E d ≤ 2 m + O ( log ( n / η ) ) d\le2m+O(\log(n/\eta)) d ≤ 2 m + O ( log ( n / η ))
The hash family in Theorem B.4 consists of polynomial evaluation followed by two-universal hashing. Polynomial evaluation and two-universal hashing run in polynomial time. The required finite field can be constructed in fixed characteristic using [44 ] .
