Classical Hardness of Learning Functions of Hamiltonians
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 Tr[f(H)ρ] from classical descriptions of a Hamiltonian H and a quantum state ρ, 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 fcos,π(λ)=cos(πλ) and fexp,β(λ)=e−βλ 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.
Related
- Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
- Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
- Exact Work Characteristic Functions for Time-Dependent Bosonic Quadratic Hamiltonians
- Learning SYK Hamiltonians
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
BibTeX
@misc{hashimoto2026classical,
title = {{Classical Hardness of Learning Functions of Hamiltonians}},
author = {Sota Hashimoto and Akinori Kawachi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01141},
eprint = {2610.01141},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01141},
}
RIS
TY - UNPB
TI - Classical Hardness of Learning Functions of Hamiltonians
AU - Sota Hashimoto
AU - Akinori Kawachi
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01141
UR - https://arxiv.org/abs/2610.01141
AB - Morohoshi, Nakayama, Manabe, and Mitarai proposed a physically motivated quantum machine learning problem in which the goal is to predict quantities of the form Tr[f(H)ρ] from classical descriptions of a Hamiltonian H and a quantum state ρ, 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_cos,π(λ)=cos(πλ) and f_exp,β(λ)=e^−βλ 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.
ER -