2009/10/19 by Brendan Juba, Juba, Brendan · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Active learning (machine learning) #Algorithm #Artificial intelligence #Computational complexity theory #Computational learning theory #Computer science #Cryptography #Discrete mathematics #FOS: Computer and information sciences #FOS: Physical sciences #Finite state #Generator (circuit theory) #Hidden Markov model #Learning with errors #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine learning #Markov chain #Markov process #Mathematical analysis #Mathematics #Neural Networks and Applications #Noise (video) #Physics #Polynomial #Probably approximately correct learning #Quantum #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum mechanics #Quantum state #State (computer science) #Statistical physics #Statistics #Theoretical computer science #cs.LG #quant-ph
paper · pdf · doi:10.48550/arxiv.0910.3713
published in arXiv (Cornell University) (Cornell University) · 10 pages, 1 figure
arxiv created 2009/10/19 · openalex publication_date 2009/10/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We examine the complexity of learning the distributions produced by finite-state quantum sources. We show how prior techniques for learning hidden Markov models can be adapted to the quantum generator model to find that the analogous state of affairs holds: information-theoretically, a polynomial number of samples suffice to approximately identify the distribution, but computationally, the problem is as hard as learning parities with noise, a notorious open question in computational learning theory.