A survey on the complexity of learning quantum states

Huaiguang Wu, Jiahui Zhang, Lijie Wang +3 more

Anurag Anshu, Srinivasan Arunachalam

We survey various recent results that rigorously study the complexity of learning quantum states. These include progress on quantum tomography, learning physical quantum states, alternate learning models to tomography and learning classical functions encoded as quantum states. We highlight how these results are paving the way for a highly successful theory with a range of exciting open questions. To this end, we distill 25 open questions from these results.

Juan Carrasquilla

Dongsu Bak A, Su-Hyeong Kim, Sangnam Park +1 more

Jun Hai Zhao, Wenhan Yu

This paper presents a comprehensive survey of Quantum Multi-Agent Reinforcement Learning (QMARL), a nascent field at the intersection of quantum computing and multi-agent systems. The survey begins by introducing the fundamentals of quantum computing, highlighting its potential to revolutionize computational capabilities. We then delve into the principles of multi-agent reinforcement learning (MARL), examining how quantum computing can enhance learning efficiency and decision-making processes in complex environments. The core of the survey focuses on the current state of QMARL, reviewing existing literature, methodologies, and case studies that demonstrate the integration of quantum algorithms with MARL frameworks. The paper also addresses the unique challenges and opportunities presented by quantum technologies in multi-agent systems, such as quantum entanglement and superposition, and their implications for agent coordination and learning dynamics. Additionally, the survey explores the practical applications of QMARL in various domains, including cybersecurity, finance, and robotics, underscoring its transformative potential. The paper concludes by identifying key research gaps and proposing future directions for the development of QMARL. This includes the need for scalable quantum algorithms, the exploration of quantum-resistant strategies in adversarial settings, and the integration of quantum principles in agent communication and collaboration. Overall, this survey serves as a foundational guide for researchers and practitioners interested in the emerging field of QMARL, offering insights into its current achievements and future possibilities.

Sagnik Chatterjee

This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems.