Improved Quantum Random Self-Reduction for Linear Problems

We study quantum random self-reductions for linear problems over finite fields. Let $M\in {\mathbb{F}}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\epsilon$-fraction of inputs $x\sim {\mathbb{F}}^n$. Given coherent access to $\mathcal{O}$ and coherent entry access to $M$, we give a uniform quantum reduction that computes $Mx$ on any prescribed input $x$ with probability at least $2\mathrm{/}3$ in time $\tilde{O}(n{T}^{1\mathrm{/}3})$, for $n\le T\le n^{3\mathrm{/}2}$ and constant field size and $\epsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\tilde{O}(n)$, the reduction runs in time $\tilde{O}(n^{4\mathrm{/}3})$, improving the $\tilde{O}(n^{3\mathrm{/}2}+T)$ reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024). Our reduction uses the Bogolyubov–Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov–Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.