arXiv：cs.LG（机器学习，全量分类）· Sota Hashimoto, Akinori Kawachi·· 9 小时前AI 评分39
学习哈密顿量函数的经典困难性
Classical Hardness of Learning Functions of Hamiltonians
AI 导读
针对 Morohoshi 等人提出的哈密顿量函数学习问题，本文严格证明了两个特定分布下（f_cos,π(λ)=cos(πλ) 与 f_exp,β(λ)=e^(-βλ)）的平均情况经典困难性。在随机 RSA 模数分解平均情况困难性假设下，若存在高效经典随机学习器能在平方损失下以经典多项式时间评估输出假设，则将推出随机 RSA 模数分解的经典随机多项式时间算法。
正文
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_{\cos,\pi}(\lambda)=\cos(\pi\lambda)$ and $f_{\exp,\beta}(\lambda)=e^{-\beta\lambda}$ 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.
| Comments: | 11 pages, 1 figure |
| Subjects: | Quantum Physics (quant-ph); Machine Learning (cs.LG) |
| ACM classes: | F.2.0 |
| Cite as: | arXiv:2610.01141 [quant-ph] |
| (or arXiv:2610.01141v1 [quant-ph] for this version) | |
| https://doi.org/10.48550/arXiv.2610.01141 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Akinori Kawachi [view email]
[v1]
Thu, 1 Oct 2026 06:22:26 UTC (16 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org