Skip to content
Preprint

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

Oct 2026 · 0 citations · 60 references
Computer Science Physics

TL;DR

An equivalence between matrix samplers and quantum-proof randomness extractors is established and explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity are constructed via constructing quantum-proof extractors.

Abstract

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler--extractor equivalence is established by a seminal work of Zuckerman (Random Structures&Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $\delta\leq\varepsilon$, our matrix sampler uses $m+O_\alpha(\log(D/\delta))$ random bits and $O_\alpha(\varepsilon^{-2-\alpha}\log^{1+\alpha}(D/\delta))$ samples, for any constant $\alpha>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under the same optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1-\gamma} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_\alpha(a+\log(1/\eta))$ and seed length at most $(1+\alpha)\log a+(2+\alpha)\log(1/\eta)+O_\alpha(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $\eta$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-\Omega(n)}$, having optimal seed length $O(\log(n/\eta))$ and output length $\Omega(n)$, improving previous constructions.

View source

Similar papers

Preprint Sep 2026

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

A multiplicative-adversary derivation that tracks the progress produced by individual oracle queries and proves that unique OR on bits with success probability $1/2+\zeta$ requires $\Omega(\sqrt{\zeta n})$ queries, and reduces unique OR to the two-weight counting problem.

Albert Lin, Han-Hsuan Lin · 0 citations
Sep 2026

Planted Cliques and Quantum Symmetry-Adapted Measurements

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For...

Vojtěch Havlíček, Jordan Docter, Subhash Khot · 0 citations
Sep 2026

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

The main idea behind the algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches.

Srinivasan Arunachalam, Qi-Zhao Huang, Makrand Sinha · 0 citations
Preprint Oct 2026

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

In the quantum query model, it is shown that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness and proves an earlier conjecture for Haar-random states and extends it to Fourier sampling.

Keshav Bhateja, Mehdi Esmaili, A. Mantri · 0 citations
Preprint Oct 2026

Efficient Quantum State Identity Testing

This work presents two quantum algorithms with complementary guarantees on circuit depth and sample complexity and proves a matching sample complexity lower bound of $\Omega(\log(n/\delta))$ for any quantum algorithm with failure probability at most $\delta\le 1/2-c$.

Shih-Han Hung, Ming-Hsien Tsai · 0 citations
Preprint Oct 2026

On State Distinguishing Without Inverse Queries

In the quantum state distinguishing problem, an algorithm is given copies of a state $|\psi\rangle$ or $|\phi\rangle$ separated by trace distance $\varepsilon$, and tasked with deciding which is the case. It is a standard result that $\Theta(\varepsilon^{-2})$ copies are required, while having access to a unitary state...

Emma Wang, Joseph Carolan, Andrew M. Childs · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.