IDEAS home Printed from https://ideas.repec.org/a/nat/natcom/v14y2023i1d10.1038_s41467-023-36144-5.html
   My bibliography  Save this article

Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines

Author

Listed:
  • Jonas Jäger

    (University of British Columbia
    Technische Universität Darmstadt)

  • Roman V. Krems

    (University of British Columbia
    Stewart Blusson Quantum Matter Institute)

Abstract

Machine learning is considered to be one of the most promising applications of quantum computing. Therefore, the search for quantum advantage of the quantum analogues of machine learning models is a key research goal. Here, we show that variational quantum classifiers and support vector machines with quantum kernels can solve a classification problem based on the k-FORRELATION problem, which is known to be PROMISEBQP-complete. Because the PROMISEBQP complexity class includes all Bounded-Error Quantum Polynomial-Time (BQP) decision problems, our results imply that there exists a feature map and a quantum kernel that make variational quantum classifiers and quantum kernel support vector machines efficient solvers for any BQP problem. Hence, this work implies that their feature map and quantum kernel, respectively, can be designed to have a quantum advantage for any classification problem that cannot be classically solved in polynomial time but contrariwise by a quantum computer.

Suggested Citation

  • Jonas Jäger & Roman V. Krems, 2023. "Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines," Nature Communications, Nature, vol. 14(1), pages 1-7, December.
    • Handle: RePEc:nat:natcom:v:14:y:2023:i:1:d:10.1038_s41467-023-36144-5
    DOI: 10.1038/s41467-023-36144-5
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/s41467-023-36144-5
    File Function: Abstract
    Download Restriction: no
    File URL: https://libkey.io/10.1038/s41467-023-36144-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Jacob Biamonte & Peter Wittek & Nicola Pancotti & Patrick Rebentrost & Nathan Wiebe & Seth Lloyd, 2017. "Quantum machine learning," Nature, Nature, vol. 549(7671), pages 195-202, September.
    2. Maria Schuld, 2019. "Machine learning in quantum spaces," Nature, Nature, vol. 567(7747), pages 179-181, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sofiene Jerbi & Lukas J. Fiderer & Hendrik Poulsen Nautrup & Jonas M. Kübler & Hans J. Briegel & Vedran Dunjko, 2023. "Quantum machine learning beyond kernel methods," Nature Communications, Nature, vol. 14(1), pages 1-8, December.
    2. Olawale Ayoade & Pablo Rivas & Javier Orduz, 2022. "Artificial Intelligence Computing at the Quantum Level," Data, MDPI, vol. 7(3), pages 1-16, February.
    3. Wei-Ming Li & Shi-Ju Ran, 2022. "Non-Parametric Semi-Supervised Learning in Many-Body Hilbert Space with Rescaled Logarithmic Fidelity," Mathematics, MDPI, vol. 10(6), pages 1-15, March.
    4. Johannes Herrmann & Sergi Masot Llima & Ants Remm & Petr Zapletal & Nathan A. McMahon & Colin Scarato & François Swiadek & Christian Kraglund Andersen & Christoph Hellings & Sebastian Krinner & Nathan, 2022. "Realizing quantum convolutional neural networks on a superconducting quantum processor to recognize quantum phases," Nature Communications, Nature, vol. 13(1), pages 1-7, December.
    5. Ajagekar, Akshay & You, Fengqi, 2022. "Quantum computing and quantum artificial intelligence for renewable and sustainable energy: A emerging prospect towards climate neutrality," Renewable and Sustainable Energy Reviews, Elsevier, vol. 165(C).
    6. Daniel J. Egger & Claudio Gambella & Jakub Marecek & Scott McFaddin & Martin Mevissen & Rudy Raymond & Andrea Simonetto & Stefan Woerner & Elena Yndurain, 2020. "Quantum Computing for Finance: State of the Art and Future Prospects," Papers 2006.14510, arXiv.org, revised Jan 2021.
    7. Wu, Jiang & Ou, Guiyan & Liu, Xiaohui & Dong, Ke, 2022. "How does academic education background affect top researchers’ performance? Evidence from the field of artificial intelligence," Journal of Informetrics, Elsevier, vol. 16(2).
    8. Ajagekar, Akshay & You, Fengqi, 2021. "Quantum computing based hybrid deep learning for fault diagnosis in electrical power systems," Applied Energy, Elsevier, vol. 303(C).
    9. Jurgita Bruneckiene & Robertas Jucevicius & Ineta Zykiene & Jonas Rapsikevicius & Mantas Lukauskas, 2019. "Assessment of Investment Attractiveness in European Countries by Artificial Neural Networks: What Competences are Needed to Make a Decision on Collective Well-Being?," Sustainability, MDPI, vol. 11(24), pages 1-23, December.
    10. Boualem Djehiche & Björn Löfdahl, 2021. "Quantum Support Vector Regression for Disability Insurance," Risks, MDPI, vol. 9(12), pages 1-9, December.
    11. Li, Nianqiao & Yan, Fei & Hirota, Kaoru, 2022. "Quantum data visualization: A quantum computing framework for enhancing visual analysis of data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 599(C).
    12. Elies Gil-Fuster & Jens Eisert & Carlos Bravo-Prieto, 2024. "Understanding quantum machine learning also requires rethinking generalization," Nature Communications, Nature, vol. 15(1), pages 1-12, December.
    13. Guo, Mingchao & Liu, Hailing & Li, Yongmei & Li, Wenmin & Gao, Fei & Qin, Sujuan & Wen, Qiaoyan, 2022. "Quantum algorithms for anomaly detection using amplitude estimation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 604(C).
    14. Vicente Moret-Bonillo & Samuel Magaz-Romero & Eduardo Mosqueira-Rey, 2022. "Quantum Computing for Dealing with Inaccurate Knowledge Related to the Certainty Factors Model," Mathematics, MDPI, vol. 10(2), pages 1-21, January.
    15. Gong, Li-Hua & Xiang, Ling-Zhi & Liu, Si-Hang & Zhou, Nan-Run, 2022. "Born machine model based on matrix product state quantum circuit," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 593(C).
    16. Laura Böhm & Sebastian Kolb & Thomas Plankenbühler & Jonas Miederer & Simon Markthaler & Jürgen Karl, 2023. "Short-Term Natural Gas and Carbon Price Forecasting Using Artificial Neural Networks," Energies, MDPI, vol. 16(18), pages 1-25, September.
    17. Serena Di Giorgio & Paulo Mateus, 2021. "On the Complexity of Finding the Maximum Entropy Compatible Quantum State," Mathematics, MDPI, vol. 9(2), pages 1-24, January.
    18. Sheshadri Chatterjee & Ranjan Chaudhuri & Sachin Kamble & Shivam Gupta & Uthayasankar Sivarajah, 2023. "Adoption of Artificial Intelligence and Cutting-Edge Technologies for Production System Sustainability: A Moderator-Mediation Analysis," Information Systems Frontiers, Springer, vol. 25(5), pages 1779-1794, October.
    19. Junyu Liu & Minzhao Liu & Jin-Peng Liu & Ziyu Ye & Yunfei Wang & Yuri Alexeev & Jens Eisert & Liang Jiang, 2024. "Towards provably efficient quantum algorithms for large-scale machine-learning models," Nature Communications, Nature, vol. 15(1), pages 1-6, December.
    20. Matthias C. Caro & Hsin-Yuan Huang & M. Cerezo & Kunal Sharma & Andrew Sornborger & Lukasz Cincio & Patrick J. Coles, 2022. "Generalization in quantum machine learning from few training data," Nature Communications, Nature, vol. 13(1), pages 1-11, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nat:natcom:v:14:y:2023:i:1:d:10.1038_s41467-023-36144-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.nature.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.