Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917022172971008 |
|---|---|
| author | Aggarwal, Divesh Kwan, Dexter |
| author_facet | Aggarwal, Divesh Kwan, Dexter |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_15721 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication Aggarwal, Divesh Kwan, Dexter Quantum Physics Computational Complexity Data Structures and Algorithms 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. |
| title | Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.15721 |