IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i2p193-d482971.html
   My bibliography  Save this article

On the Complexity of Finding the Maximum Entropy Compatible Quantum State

Author

Listed:
  • Serena Di Giorgio

    (Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais, 1049-001 Lisboa, Portugal
    Instituto de Telecomunicações, Universidade de Lisboa, Av. Rovisco Pais, 1049-001 Lisboa, Portugal
    These authors contributed equally to this work.)

  • Paulo Mateus

    (Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais, 1049-001 Lisboa, Portugal
    Instituto de Telecomunicações, Universidade de Lisboa, Av. Rovisco Pais, 1049-001 Lisboa, Portugal
    These authors contributed equally to this work.)

Abstract

Herein we study the problem of recovering a density operator from a set of compatible marginals, motivated by limitations of physical observations. Given that the set of compatible density operators is not singular, we adopt Jaynes’ principle and wish to characterize a compatible density operator with maximum entropy. We first show that comparing the entropy of compatible density operators is complete for the quantum computational complexity class QSZK, even for the simplest case of 3-chains. Then, we focus on the particular case of quantum Markov chains and trees and establish that for these cases, there exists a procedure polynomial in the number of subsystems that constructs the maximum entropy compatible density operator. Moreover, we extend the Chow–Liu algorithm to the same subclass of quantum states.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:2:p:193-:d:482971
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/2/193/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/2/193/
    Download Restriction: no
    ---><---

    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. Yuchung J. Wang, 2004. "Compatibility among marginal densities," Biometrika, Biometrika Trust, vol. 91(1), pages 234-239, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fernando L. Pelayo & Mauro Mezzini, 2022. "Preface to the Special Issue on “Quantum Computing Algorithms and Computational Complexity”," Mathematics, MDPI, vol. 10(21), pages 1-3, October.

    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. 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).
    2. Xinbiao Wang & Yuxuan Du & Zhuozhuo Tu & Yong Luo & Xiao Yuan & Dacheng Tao, 2024. "Transition role of entangled data in quantum machine learning," Nature Communications, Nature, vol. 15(1), pages 1-8, December.
    3. Ajagekar, Akshay & You, Fengqi, 2021. "Quantum computing based hybrid deep learning for fault diagnosis in electrical power systems," Applied Energy, Elsevier, vol. 303(C).
    4. 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.
    5. Nikolaos Schetakis & Davit Aghamalyan & Michael Boguslavsky & Agnieszka Rees & Marc Rakotomalala & Paul Robert Griffin, 2024. "Quantum Machine Learning for Credit Scoring," Mathematics, MDPI, vol. 12(9), pages 1-12, May.
    6. 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).
    7. Cambyse Rouzé & Daniel Stilck França & Emilio Onorati & James D. Watson, 2024. "Efficient learning of ground and thermal states within phases of matter," Nature Communications, Nature, vol. 15(1), pages 1-8, December.
    8. 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.
    9. 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).
    10. 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.
    11. 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).
    12. 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.
    13. 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.
    14. 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.
    15. Alen Senanian & Sridhar Prabhu & Vladimir Kremenetski & Saswata Roy & Yingkang Cao & Jeremy Kline & Tatsuhiro Onodera & Logan G. Wright & Xiaodi Wu & Valla Fatemi & Peter L. McMahon, 2024. "Microwave signal processing using an analog quantum reservoir computer," Nature Communications, Nature, vol. 15(1), pages 1-9, December.
    16. 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.
    17. Wang, Shaoxuan & Shen, Yingtong & Liu, Xinjian & Zhang, Haoying & Wang, Yukun, 2024. "Variational quantum entanglement classification discrimination," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 637(C).
    18. Ojas Parekh, 2023. "Synergies Between Operations Research and Quantum Information Science," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 266-273, March.
    19. 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.
    20. Xi Yang & Yuting Li & Yitao Liu & Qian Li & Tingna Yang & Hongxing Jia, 2024. "Crystal Structure Prediction and Performance Assessment of Hydrogen Storage Materials: Insights from Computational Materials Science," Energies, MDPI, vol. 17(14), pages 1-20, July.

    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:gam:jmathe:v:9:y:2021:i:2:p:193-:d:482971. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.