{"ID":2854161,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.15721","arxiv_id":"2510.15721","title":"Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication","abstract":"Worst-case to average-case reductions are a cornerstone of complexity theory, providing a bridge between worst-case hardness and average-case computational difficulty. While recent works have demonstrated such reductions for fundamental problems using deep tools from ad- ditive combinatorics, these approaches often suffer from substantial complexity and suboptimal overheads. In this work, we focus on the quantum setting, and provide a new reduction for the Matrix-Vector Multiplication problem that is more efficient, and conceptually simpler than previous constructions. By adapting hardness self-amplification techniques to the quantum do- main, we obtain a quantum worst-case to average-case reduction with improved dependence on the success probability, laying the groundwork for broader applications in quantum fine-grained complexity.","short_abstract":"Worst-case to average-case reductions are a cornerstone of complexity theory, providing a bridge between worst-case hardness and average-case computational difficulty. While recent works have demonstrated such reductions for fundamental problems using deep tools from ad- ditive combinatorics, these approaches often suf...","url_abs":"https://arxiv.org/abs/2510.15721","url_pdf":"https://arxiv.org/pdf/2510.15721v1","authors":"[\"Divesh Aggarwal\",\"Dexter Kwan\"]","published":"2025-10-17T15:11:13Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}