arXiv:2609.39823
Improved Quantum Random Self-Reduction for Linear Problems
Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu
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 $\varepsilon$-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 $\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$ and constant field size and $\varepsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\widetilde{O}(n)$, the reduction runs in time $\widetilde{O}(n^{4/3})$, improving the $\widetilde{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.
AI Summary
The paper studies uniform quantum worst-case-to-average-case reductions for finite-field linear maps. Given an arbitrary matrix $M\in\mathbb F_q^{n\times n}$ and an oracle agreeing with $z\mapsto Mz$ on an $\varepsilon$ fraction of uniformly random inputs, the goal is to compute $Mx$ for any prescribed $x$. The reduction assumes coherent access to both the average-case oracle and individual matrix entries. For constant $q$ and $\varepsilon$, with oracle evaluation cost $n\le T\le n^{3/2}$, the reduction succeeds with probability at least $2/3$ in time $\widetilde O(nT^{1/3})$. At $T=\widetilde O(n)$, this gives $\widetilde O(n^{4/3})$, compared with the previous $\widetilde O(T+n^{3/2})$ bound. For $T>n^{3/2}$, the cost is $\widetilde O(T)$. The guarantees extend to randomized and quantum average-case algorithms with coherent implementations and inverse access. The construction uses the existence of a low-codimension Bogolyubov–Ruzsa subspace without explicitly learning it. Candidate lists and tournament selection provide correction on an expanding hidden subspace. A consistency tree combines local additive checks with sparse leaf verification; quantum search locates failures from which certified new directions are extracted. Block Reed–Solomon fingerprints account for accessing internally generated vectors in the standard circuit model, rather than assuming free coherent coordinate access. The general running-time bound carries a factor $(q/\varepsilon)^{O(\log(1/\varepsilon))}$, so the stated exponents concern constant field size and agreement. Some matrix access is necessary in general. A separate classical warm-up achieves nearly oracle-linear time for constant parameters only in the error-less model, where incorrect outputs are forbidden.
The algorithm and proof strategy underlying the main theorem were suggested by ChatGPT 5.5. Subsequent interactions with AI were used to refine and clarify the proof.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.