{"id":"arxiv/2609.38403","url":"https://arxiv.org/abs/2609.38403","tags":["quant-ph","cs.LG","stat.ML"],"score":0,"title":"Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries","domain":"quant-ph","source":"arxiv","authors":["Natsuto Isogai","Satoshi Yoshida","Mio Murao"],"reviews":0,"subject":"quant-ph","summary":"Whether quantum computation can reduce the amount of data sampled from an unknown probability distribution required to learn a prediction rule is a fundamental question in quantum machine learning. Quantum PAC learning studies this question using quantum data as a quantum state whose squared amplitudes encode the unknown distribution from which classical learning data are sampled. With only copies of such quantum data, the optimal worst-case sample complexity asymptotically matches that of classical PAC learning. In contrast, access to both a state-preparation unitary for this state and its…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}