Classical Hardness of Learning Functions of Hamiltonians
Hashimoto and Kawachi study Hamiltonian function learning: predicting $\operatorname{Tr}[f(H)\rho]$ from classical descriptions of a Hamiltonian $H$ and state $\rho$ when the function $f$ is fixed and known. Their core result is a rigorous average-case classical hardness proof for two explicit instances—$f_{\cos,\pi}(\lambda)=\cos(\pi\lambda)$ and $f_{\exp,\beta}(\lambda)=e^{-\beta\lambda}$—obtained by reducing from the hardness of factoring random RSA moduli via Shor's algorithm embedded in projector Hamiltonians. This settles an open problem left by Morohoshi et al. and gives a computational quantum advantage in a quantum machine learning task that has already been demonstrated experimentally on superconducting devices.
The paper delivers a clean cryptographic reduction proving average-case classical hardness for two specific Hamiltonian function learning problems under the standard hardness of factoring assumption. The construction is technically careful and closes an open problem from prior work, though the quantum-classical separation is achieved only under the strong restriction that the classical learner must output a hypothesis evaluable in deterministic polynomial time, and the hard Hamiltonians are highly non-local projectors defined by factoring circuits rather than physically natural local interactions.
The reduction follows the Kearns-Valiant strategy faithfully but adapts it cleverly to the Hamiltonian learning setting by encoding the witness bits of an RSA factorization into the acceptance probability of a quantum circuit, then lifting that probability into the target quantity via a projector Hamiltonian. The target-separation analysis is tight: because $H_{N,j,b}$ is a projector, both $\operatorname{Tr}[\cos(\pi H_{N,j,b})\rho_{0}]$ and $\operatorname{Tr}[e^{-\beta H_{N,j,b}}\rho_{0}]$ become affine functions of the acceptance probability, yielding a constant gap that survives noisy labels and allows bit extraction by comparing $g(x_{N,j,0})$ and $g(x_{N,j,1})$.
The hardness result hinges critically on the requirement that the classical learner output a hypothesis evaluable in deterministic polynomial time; without this, the reduction cannot query the hypothesis on the challenge-derived inputs $x_{N,j,b}$. A second limitation is that the constructed Hamiltonians are non-local projectors defined by Shor-type factoring circuits, so the separation does not apply to the local Hamiltonians more commonly studied in condensed-matter physics or the original experimental demonstration.
The evidence supports the hardness claims because the factoring-to-learning reduction is tight: any efficient classical learner with polynomial-time evaluable hypotheses would immediately yield a polynomial-time factoring algorithm with success probability $2/3$, contradicting Assumption 2.5. Comparisons to related work are fair and informative: the authors correctly note that P\'{e}rez-Guijarro et al. demand pointwise accuracy whereas they need only expected squared loss, that Yamasaki et al. require hardness against $\mathsf{HeurFBPP/rpoly}$ while they need only uniform randomized algorithms, and that Molteni et al. obtain a distribution-free separation under $\mathsf{BQP}\not\subseteq\mathsf{P/poly}$ rather than an explicit average-case distribution under standard factoring.
As a purely theoretical cryptography paper, no code, datasets, or experimental scripts are provided. Nevertheless, the proof is reproducible in principle because the construction is fully explicit: the loss parameters are set to $\gamma_{\beta}:=\beta/(1+\beta)$, $\tau(n):=\gamma_{\beta}^{2}/(128L(n))$, $\varepsilon(n):=\tau(n)/200$, and $\delta(n):=1/200$, and the projector Hamiltonian $H_{N,j,b}$ is defined by a reversible amplified Shor circuit $U_{N,j,b}$ whose classical description has polynomial length. Reproduction therefore requires only verifying the polynomial bounds and the gap analysis in Lemma 3.2, which are laid out in full detail.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.