Advantage of Entangled Learning Rules in Quantum Measurement Class Learning

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 inverse can improve the query-complexity dependence on the accuracy parameter in realizable learning. However, it has remained unclear whether forward-only access allows such an improvement. In this work, taking the worst case over compatible state-preparation unitaries and their finite ambient dimensions, we show that the optimal forward-only query complexities of realizable and agnostic learning are, respectively, $Θ((d+\log(1/δ))/\varepsilon)$ and $Θ((d+\log(1/δ))/\varepsilon^2)$, where $d$ is the VC dimension of the concept class, $\varepsilon$ the accuracy parameter, and $δ$ the failure probability. These bounds match the optimal sample complexities with classical data or quantum data copies. To prove them, we establish a reduction using $q$ copies of the prepared state to approximate the Haar-averaged output of any $q$-query forward-only algorithm. These results show that forward-only access cannot provide an asymptotic query-complexity advantage over learning from classical data or quantum data copies in this worst-case setting, and establish the essential role of inverse access in the known realizable-setting improvement. Our reduction also provides a new framework for analyzing limitations of forward state-preparation access via state-copy lower bounds.

Structured quantum-state learning not only depends on an expressive ansatz but also on an operational certificate that stays meaningful with finite measurements and imperfect implementation. We study pure one dimensional states learning by an inverse binary multiscale entanglement renormalization ansatz (MERA). In the learning procedure, the qubits removed during coarse graining are controlled coherently and measured together at the terminal register. We confirm that an ideal sequential and terminal measurement schedule delivers the same complete bit string distribution under matched causal operations, while normalized postselection can amplify perturbations inversely with prefix acceptance. A noise aware theorem introduces an individual calibrated total variation implementation budget to the finite shot certificate. The protocol is estimated on an open boundary transverse field Ising ground state. A frozen 8-qubit schedule using $560$ million simulated training measurements per run achieves fidelity above $0.99$ in all $60$ held-out runs, with a mean fidelity of $0.996886$. 1080 circuit-noise cells and 6480 confidence-coverage rows are covered by fixed-circuit robustness validation without a locked soundness violation. We then address architectural fairness at $n=16$ using three new studies. In a 120-run exact-gradient multistart diagnostic, MERA has higher fidelity in 58/60 paired restarts and lower long-range error in 60/60, although no run met the prespecified stationarity criterion. Finally, a causal cone-complete, parameter matched local circuit achieves $2.62\times$ greater aggregate gate exposure yet loses all 30 paired comparisons in fidelity, long-range error, energy, and entropy.

Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.