Improved Quantum Random Self-Reduction for Linear Problems

Abstract

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/3$ in time $\tilde{O}(n{T}^{1/3})$, for $n\le T\le n^{3/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/3})$, improving the $\tilde{O}(n^{3/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.