Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage
The widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantages are, in general, not equivalent, i.e., the additional information provid...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10374234/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832583961045368832 |
|---|---|
| author | Jordi Perez-Guijarro Alba Pages-Zamora Javier R. Fonollosa |
| author_facet | Jordi Perez-Guijarro Alba Pages-Zamora Javier R. Fonollosa |
| author_sort | Jordi Perez-Guijarro |
| collection | DOAJ |
| description | The widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantages are, in general, not equivalent, i.e., the additional information provided by a training set can reduce the hardness of some problems. This article investigates under which conditions they are found to be equivalent or, at least, highly related. This relation is analyzed by considering two definitions of learning speed-up: one tied to the distribution and another that is distribution-independent. In both cases, the existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions, although, for the distribution-independent definition, additional mild conditions must also be met. Finally, these results are applied to prove that there is a quantum speed-up for some learning tasks based on the prime factorization problem, assuming the classical intractability of this problem. |
| format | Article |
| id | doaj-art-147afefcceec456080e8f580da5711d6 |
| institution | Kabale University |
| issn | 2689-1808 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj-art-147afefcceec456080e8f580da5711d62025-01-28T00:02:17ZengIEEEIEEE Transactions on Quantum Engineering2689-18082024-01-01511710.1109/TQE.2023.334747610374234Relation Between Quantum Advantage in Supervised Learning and Quantum Computational AdvantageJordi Perez-Guijarro0https://orcid.org/0000-0002-2533-0730Alba Pages-Zamora1https://orcid.org/0000-0002-7087-7014Javier R. Fonollosa2https://orcid.org/0000-0002-0136-2586Departament de Teoria del Senyal i Comunicacions, Universitat Politécnica de Catalunya, Barcelona, SpainDepartament de Teoria del Senyal i Comunicacions, Universitat Politécnica de Catalunya, Barcelona, SpainDepartament de Teoria del Senyal i Comunicacions, Universitat Politécnica de Catalunya, Barcelona, SpainThe widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantages are, in general, not equivalent, i.e., the additional information provided by a training set can reduce the hardness of some problems. This article investigates under which conditions they are found to be equivalent or, at least, highly related. This relation is analyzed by considering two definitions of learning speed-up: one tied to the distribution and another that is distribution-independent. In both cases, the existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions, although, for the distribution-independent definition, additional mild conditions must also be met. Finally, these results are applied to prove that there is a quantum speed-up for some learning tasks based on the prime factorization problem, assuming the classical intractability of this problem.https://ieeexplore.ieee.org/document/10374234/Prime factorization problemquantum advantagequantum machine learningsupervised learning |
| spellingShingle | Jordi Perez-Guijarro Alba Pages-Zamora Javier R. Fonollosa Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage IEEE Transactions on Quantum Engineering Prime factorization problem quantum advantage quantum machine learning supervised learning |
| title | Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage |
| title_full | Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage |
| title_fullStr | Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage |
| title_full_unstemmed | Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage |
| title_short | Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage |
| title_sort | relation between quantum advantage in supervised learning and quantum computational advantage |
| topic | Prime factorization problem quantum advantage quantum machine learning supervised learning |
| url | https://ieeexplore.ieee.org/document/10374234/ |
| work_keys_str_mv | AT jordiperezguijarro relationbetweenquantumadvantageinsupervisedlearningandquantumcomputationaladvantage AT albapageszamora relationbetweenquantumadvantageinsupervisedlearningandquantumcomputationaladvantage AT javierrfonollosa relationbetweenquantumadvantageinsupervisedlearningandquantumcomputationaladvantage |