Lower bounds for quantum-inspired classical algorithms via communication complexity
Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In the past several years, numerous efficient algorithms for various tasks have been found, while an analysis...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-01-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-01-14-1593/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850092999463141376 |
|---|---|
| author | Nikhil S. Mande Changpeng Shao |
| author_facet | Nikhil S. Mande Changpeng Shao |
| author_sort | Nikhil S. Mande |
| collection | DOAJ |
| description | Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In the past several years, numerous efficient algorithms for various tasks have been found, while an analysis of lower bounds is still missing. Using communication complexity, in this work we propose the first method to study lower bounds for these tasks. We mainly focus on lower bounds for solving linear regressions, supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulations. For those problems, we prove a quadratic lower bound in terms of the Frobenius norm of the underlying matrix. As quantum algorithms are linear in the Frobenius norm for those problems, our results mean that the quantum-classical separation is at least quadratic. As a generalisation, we extend our method to study lower bounds analysis of quantum query algorithms for matrix-related problems using quantum communication complexity. Some applications are given. |
| format | Article |
| id | doaj-art-8aeccdcfa3454b91b578bf1df64bc9da |
| institution | DOAJ |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-8aeccdcfa3454b91b578bf1df64bc9da2025-08-20T02:42:00ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-01-019159310.22331/q-2025-01-14-159310.22331/q-2025-01-14-1593Lower bounds for quantum-inspired classical algorithms via communication complexityNikhil S. MandeChangpeng ShaoQuantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In the past several years, numerous efficient algorithms for various tasks have been found, while an analysis of lower bounds is still missing. Using communication complexity, in this work we propose the first method to study lower bounds for these tasks. We mainly focus on lower bounds for solving linear regressions, supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulations. For those problems, we prove a quadratic lower bound in terms of the Frobenius norm of the underlying matrix. As quantum algorithms are linear in the Frobenius norm for those problems, our results mean that the quantum-classical separation is at least quadratic. As a generalisation, we extend our method to study lower bounds analysis of quantum query algorithms for matrix-related problems using quantum communication complexity. Some applications are given.https://quantum-journal.org/papers/q-2025-01-14-1593/pdf/ |
| spellingShingle | Nikhil S. Mande Changpeng Shao Lower bounds for quantum-inspired classical algorithms via communication complexity Quantum |
| title | Lower bounds for quantum-inspired classical algorithms via communication complexity |
| title_full | Lower bounds for quantum-inspired classical algorithms via communication complexity |
| title_fullStr | Lower bounds for quantum-inspired classical algorithms via communication complexity |
| title_full_unstemmed | Lower bounds for quantum-inspired classical algorithms via communication complexity |
| title_short | Lower bounds for quantum-inspired classical algorithms via communication complexity |
| title_sort | lower bounds for quantum inspired classical algorithms via communication complexity |
| url | https://quantum-journal.org/papers/q-2025-01-14-1593/pdf/ |
| work_keys_str_mv | AT nikhilsmande lowerboundsforquantuminspiredclassicalalgorithmsviacommunicationcomplexity AT changpengshao lowerboundsforquantuminspiredclassicalalgorithmsviacommunicationcomplexity |