Quantum information · Theory
Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
arXiv:2610.37122v1 ↗PDF ↗Submitted 27 October 2026
- Question
- To estimate the average of a bounded \(D\times D\) matrix-valued function in operator norm, \(O(\varepsilon^{-2}\log(2D/\delta))\) independent samples suffice, but each costs \(m\) fresh random bits. Matrix samplers try to keep nearly that sample count while using only \(m+O(\log(D/\delta))\) random bits. Classically, Zuckerman showed that averaging samplers and randomness extractors are the same objects. What kind of extractor is a matrix sampler, and can the correspondence give better constructions?
- Result
- A matrix sampler for \(D\times D\) matrices is the same thing as a seeded extractor whose output stays uniform against an adversary holding about \(\log(2D)\) qubits of side information, up to factor-two losses in the error. The paper then builds an explicit strong quantum-proof extractor with seed \((1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1)\) and output \(n-O_\alpha(a+\log(1/\eta))\) for sources of conditional min-entropy \(n-a\). Through the correspondence, this gives explicit strong matrix samplers with \(m+O_\alpha(\log(D/\delta))\) random bits and \(O_\alpha(\varepsilon^{-2-\alpha}\log^{1+\alpha}(D/\delta))\) samples, replacing a polynomial dependence on \(D\) in earlier work by a logarithmic one. It also gives quantum-proof extractors with seed \(O(\log(n/\eta))\) and output \(\Omega(n)\) for every constant entropy rate, where earlier constructions needed rate above one half.
The paper in detail
A matrix sampler \(\mathrm{Samp}:\{0,1\}^r\times[t]\to\{0,1\}^m\) must satisfy, for every \(f\) with \(\lVert f(z)\rVert\le1\), that \(\lVert\frac1t\sum_if(\mathrm{Samp}(R,i))-\mathbb E_Zf(Z)\rVert>\varepsilon\) with probability at most \(\delta\) over a uniform \(R\). The strong version allows a different test \(f_i\) at each position. A strong quantum-proof extractor \(\mathrm{Ext}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m\) must make \((\mathrm{Ext}(X,Y),Y,E)\) \(\eta\)-close to uniform\(\otimes\)uniform\(\otimes\rho_E\) whenever \(H_{\min}(X|E)\ge k\). The \(b\)-qubit-proof version only covers \(H_\infty(X)\ge k\) with \(\dim E\le2^b\).
Theorem 1.5 identifies the two notions. If too many sampler inputs \(x\) are bad, take a top eigenvector \(v_x\) of the Hermitian dilation of the deviation \(A_x\), and hand it to the adversary as side information about a uniformly random bad \(x\). Turning each test into a two-outcome measurement \(M_{i,z}=(I+\mathcal H(f_i(z)))/2\) then distinguishes the extractor output from uniform with advantage \(\tfrac12\mathbb E\lVert A_X\rVert>\varepsilon/2\). Conversely, every binary measurement on output, seed and \(E\) defines tests \(f_i(z)=2M_{i,z}-I\), and the sampler bounds the advantage by \(\varepsilon/2\) except on a set of probability at most \(2^a\delta\). Corollary 3.1: a strong quantum-proof \((n-\log(2D/\delta),\varepsilon/2)\) extractor is a strong \(D\)-dimensional \((\delta,\varepsilon)\) sampler with \(r=n\) and \(t=2^d\).
The extractor is assembled in layers. A multilinear-polynomial evaluation followed by two-universal hashing gives one short output block; a weak design reuses one seed across many blocks, each still close to uniform given earlier blocks and the quantum side information, for linear output. Seed growth through blocks chosen by quantum entropy sampling reduces the seed to \(O(\log(n/\eta))\) for any constant entropy rate (Theorem 1.8), and a quantum-proof Goldreich–Wigderson step brings the output loss to \(O(a+\log(1/\eta))\).
Finally, \(2\ell\)-wise independent candidate seeds shorten the public seed to \(d\le2\log(1/\eta)+\log\ell+a/\ell+5\) (Theorem 6.4), and choosing \(\ell\approx a/(\alpha h)\) with \(h=\log a+\log(1/\eta)\) gives Theorem 1.7. With deficiency \(a=\lceil\log(4D/\delta)\rceil\) and error \(\varepsilon/4\), the output loss becomes the sampler’s randomness overhead and \(2^d\) its sample count (Theorem 1.6). A lower bound of \(m+\log(D/\delta)-1\) random bits and \(\Omega(\varepsilon^{-2}\log(D/\delta))\) samples for strong samplers shows that the randomness is optimal up to constants. Removing the \(\alpha\) in the exponent of the sample count remains open.
Transferable methods
Hermitian dilation turns a matrix deviation into a quantum distinguisher
The operator norm of a matrix is the largest eigenvalue of its Hermitian dilation, attained on a unit vector. That vector can be handed to the adversary as quantum side information, and a test function becomes a two-outcome measurement. Concentration in operator norm and indistinguishability against quantum memory are then the same statement.
For \(\mathcal H(A)=\bigl(\begin{smallmatrix}0&A\\A^*&0\end{smallmatrix}\bigr)\), \(\mathcal H(A)^2=AA^*\oplus A^*A\), so \(\lVert\mathcal H(A)\rVert=\lVert A\rVert\); conjugation by \(I\oplus(-I)\) maps \(\mathcal H(A)\) to \(-\mathcal H(A)\), so the eigenvalues come in \(\pm\) pairs and the top one is \(\lVert A\rVert\). With \(M_{i,z}=(I+\mathcal H(f_i(z)))/2\), we have \(0\preceq M_{i,z}\preceq I\), and for the cq state uniform on the bad set \(\mathcal B\) with \(E=\ket{v_x}\bra{v_x}\),
\[\mathrm{Tr}\bigl[M(\rho_{F(X,I)IE}-\tau_m\otimes\rho_{IE})\bigr]=\tfrac12\,\mathbb E_X\langle v_X,\mathcal H(A_X)v_X\rangle=\tfrac12\,\mathbb E_X\lVert A_X\rVert>\frac{\varepsilon}{2}.\] The source has \(H_\infty(X)=\log|\mathcal B|>n-\log(1/\delta)\) and \(\dim E=2D\), and \(H_{\min}(X|E)\ge H_\infty(X)-\log\dim E\) because \(\max_x\Pr[X=x]\,I_E\) is feasible in the semidefinite form of the guessing probability. This contradicts the extractor guarantee, so \(|\mathcal B|\le\delta2^n\).
Editorial check: for a toy map \(F:\{0,1\}^6\times[4]\to\{0,1\}^2\) and random \(2\times2\) complex tests, we took the 16 inputs with the largest \(\lVert A_x\rVert\) as \(\mathcal B\). The constructed measurement gives advantage 0.23469, equal to \(\tfrac12\mathbb E\lVert A_X\rVert\) to all printed digits, and an SDP gives guessing probability 0.111 for the cq state, below the bound \(2D/|\mathcal B|=0.25\).
How to reuse it
Any derandomisation question about operator-norm concentration (matrix Chernoff, spectral sparsification, randomised linear algebra) can be recast as extraction against a quantum adversary of \(\log(2D)\) qubits, and quantum-proof extractors with short seeds give randomness-efficient matrix samplers directly. In the other direction, a matrix sampler is a privacy-amplification function secure against bounded quantum memory.
Shortening a seed with 2ℓ-wise independent candidate seeds
Instead of feeding a long seed to an extractor, part of the weak source fills the coefficients of a low-degree polynomial whose evaluations form a list of \(t\) candidate seeds; a short public index picks one. A \(2\ell\)-th moment bound shows that a random candidate works almost as well as a fresh seed, and the min-entropy deficiency enters only as \(2^{a/(2\ell)}\).
For fixed \(x\) and measurements \(M_{j,y}\), let \(A_{x,j}(z)=M_{j,\mathrm{Ext}_0(x;G(z,j))}-\mathbb E_rM_{j,\mathrm{Ext}_0(x;r)}\) and \(B_x=\tfrac1t\sum_jA_{x,j}\). Under uniform \(z\), the \(A_{x,j}\) are mean-zero, Hermitian, of norm at most one and \(2\ell\)-wise independent. In \(\mathbb E\,B_x^{2\ell}\), any product in which an index occurs exactly once has zero expectation, so only tuples with at most \(\ell\) distinct indices count:
\[t^{2\ell}\bigl\lVert\mathbb E_zB_x(z)^{2\ell}\bigr\rVert\le\sum_{q=1}^{\ell}\binom tq q^{2\ell}\le(3\ell t)^{\ell}.\] Since \(H_{\min}(XZ|E)\ge n+s-a\) gives \(\rho_E^{xz}\preceq2^{a-n-s}\omega_E\), Jensen’s inequality yields a distinguishing advantage of at most \((2^a(3\ell/t)^\ell)^{1/(2\ell)}=2^{a/(2\ell)}\sqrt{3\ell/t}\). Choosing \(t\ge12\ell\eta^{-2}2^{a/\ell}\) makes it at most \(\eta/2\), so \(d=\log t\le2\log(1/\eta)+\log\ell+a/\ell+5\), and the coefficient block costs \(O(\ell[\log a+\log(1/\eta)+\log\ell])\) output bits.
Editorial check: enumerating all \(2\ell\)-tuples over \([t]\) with no index appearing exactly once gives 65 tuples for \((t,\ell)=(5,2)\), 96 for \((6,2)\) and 664 for \((4,3)\), against intermediate bounds 165, 246 and 3304 and final bounds 900, 1296 and 46656. The counting step is loose by a factor that grows with \(\ell\) but enters the seed length only logarithmically.
How to reuse it
When an extractor or sampler needs a long seed, consider spending some source entropy on generating \(t\) limited-independence candidates and selecting one with a \(\log t\)-bit seed. The moment method only needs mean-zero, bounded, \(k\)-wise independent terms, so it works for operator-valued tests and quantum side information, and the trade-off between \(a/\ell\) in the seed and \(\ell\cdot\)polylog in the output loss can be tuned to the application.
Context & limitations
Why it matters. The matrix dimension in sampling and the dimension of the adversary’s quantum memory in privacy amplification turn out to be the same parameter. Constructions and lower bounds can move between derandomised matrix concentration, used in spectral graph theory and numerical linear algebra, and randomness extraction against quantum adversaries, used in QKD and device-independent randomness.
Limitations. The sample count is a \((1+\alpha)\) power of the optimal one, with constants depending on \(\alpha\) that are not given. The results assume \(\delta\le\varepsilon\). Theorem 1.7 is useful only at high entropy rate. The correspondence goes through the bounded-storage notion, so converting a conditional-min-entropy extractor costs \(\log(2D)\) bits of entropy. All results are asymptotic and theoretical, with no implementation.