Classical Hardness of Learning Functions of Hamiltonians

arXiv:2610.01141v1 Announce Type: cross Abstract: Morohoshi, Nakayama, Manabe, and Mitarai proposed a physically motivated quantum machine learning problem in which the goal is to predict quantities of the form operatorname{Tr}[f(H)rho] from classical descriptions of a Hamiltonian H and a quantum state rho, where f is an unknown function. We call this problem Hamiltonian function learning in this paper. They constructed an efficient quantum learning algorithm under suitable conditions, while leaving a rigorous proof of average-case classical hardness open. In this paper, we rigorously prove the average-case classical hardness for two distribution-specific Hamiltonian function learning problems for f_{os,pi}(lambda)=os(pilambda) and f_{exp,eta}(lambda)=e^{-etalambda} discussed in the paper of Morohoshi et al. under the assumption of the average-case hardness of factoring random RSA moduli. More specifically, we show that an efficient classical randomized learner under squared loss whose output hypotheses are evaluable in classical polynomial time for either problem would yield a classical randomized polynomial-time algorithm for factoring random RSA moduli.

Source: arXiv cs.LG | 2026-10-02