Quantum Speedup for Spectral Approximation of Kronecker Products
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909104819142656 |
|---|---|
| author | Gao, Yeqi Song, Zhao Zhang, Ruizhe |
| author_facet | Gao, Yeqi Song, Zhao Zhang, Ruizhe |
| contents | Given its widespread application in machine learning and optimization, the Kronecker product emerges as a pivotal linear algebra operator. However, its computational demands render it an expensive operation, leading to heightened costs in spectral approximation of it through traditional computation algorithms. Existing classical methods for spectral approximation exhibit a linear dependency on the matrix dimension denoted by $n$, considering matrices of size $A_1 \in \mathbb{R}^{n \times d}$ and $A_2 \in \mathbb{R}^{n \times d}$. Our work introduces an innovative approach to efficiently address the spectral approximation of the Kronecker product $A_1 \otimes A_2$ using quantum methods. By treating matrices as quantum states, our proposed method significantly reduces the time complexity of spectral approximation to $O_{d,ε}(\sqrt{n})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07027 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Speedup for Spectral Approximation of Kronecker Products Gao, Yeqi Song, Zhao Zhang, Ruizhe Data Structures and Algorithms Emerging Technologies Machine Learning Quantum Algebra Quantum Physics Given its widespread application in machine learning and optimization, the Kronecker product emerges as a pivotal linear algebra operator. However, its computational demands render it an expensive operation, leading to heightened costs in spectral approximation of it through traditional computation algorithms. Existing classical methods for spectral approximation exhibit a linear dependency on the matrix dimension denoted by $n$, considering matrices of size $A_1 \in \mathbb{R}^{n \times d}$ and $A_2 \in \mathbb{R}^{n \times d}$. Our work introduces an innovative approach to efficiently address the spectral approximation of the Kronecker product $A_1 \otimes A_2$ using quantum methods. By treating matrices as quantum states, our proposed method significantly reduces the time complexity of spectral approximation to $O_{d,ε}(\sqrt{n})$. |
| title | Quantum Speedup for Spectral Approximation of Kronecker Products |
| topic | Data Structures and Algorithms Emerging Technologies Machine Learning Quantum Algebra Quantum Physics |
| url | https://arxiv.org/abs/2402.07027 |