Improved Quantum Random Self-Reduction for Linear Problems
Abstract
We study quantum random self-reductions for linear problems over finite fields. Let M∈𝔽n× n be an arbitrary matrix, and let 𝒪 be an oracle that agrees with the linear map x↦ Mx on an ε-fraction of inputs x∼𝔽n. Given coherent access to 𝒪 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 Õ(nT1/3), for n≤ T≤ n3/2 and constant field size and ε, where T is the cost of one coherent query to 𝒪. In particular, when T=Õ(n), the reduction runs in time Õ(n4/3), improving the Õ(n3/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.
Related
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- Random dimension reduction and learning symmetric properties of quantum states
- Schrödingerization for quantum linear systems problems
- A 2+1-dimensional extended Dym equation: moving boundary problems solvable via Painlevé II symmetry reduction
- An Extended 2+1-Dimensional Gardner Equation: On Moving Boundary Problems Solvable via Ermakov-Painlevé II Symmetry Reduction
BibTeX
@misc{asadi2026improved,
title = {{Improved Quantum Random Self-Reduction for Linear Problems}},
author = {Vahid R. Asadi and Shuichi Hirahara and Nobutaka Shimizu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39823},
eprint = {2609.39823},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39823},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved Quantum Random Self-Reduction for Linear Problems
AU - Vahid R. Asadi
AU - Shuichi Hirahara
AU - Nobutaka Shimizu
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39823
UR - https://arxiv.org/abs/2609.39823
AB - We study quantum random self-reductions for linear problems over finite fields. Let M∈𝔽^n× n be an arbitrary matrix, and let 𝒪 be an oracle that agrees with the linear map x↦ Mx on an ε-fraction of inputs x∼𝔽^n. Given coherent access to 𝒪 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 Õ(nT^1/3), for n≤ T≤ n^3/2 and constant field size and ε, where T is the cost of one coherent query to 𝒪. In particular, when T=Õ(n), the reduction runs in time Õ(n^4/3), improving the Õ(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.
ER -