pipette
ESEspañol

Classical Hardness of Learning Functions of Hamiltonians

Sota Hashimoto, Akinori Kawachi

Preprint

In the authors' words

Morohoshi, Nakayama, Manabe, and Mitarai proposed a physically motivated quantum machine learning problem in which the goal is to predict quantities of the form from classical descriptions of a Hamiltonian and a quantum state , where 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 and 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.

Main resultLimitation the authors admit

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 11 pages, 1 figure