{"id":"arxiv/2609.39823","url":"https://arxiv.org/abs/2609.39823","tags":["quant-ph","cs.CC"],"score":0,"title":"Improved Quantum Random Self-Reduction for Linear Problems","domain":"quant-ph","source":"arxiv","authors":["Vahid R. Asadi","Shuichi Hirahara","Nobutaka Shimizu"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}