Improved Quantum Random Self-Reduction for Linear Problems

Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu

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 agr…