Source-linked AI summary
Classical Hardness of Learning Functions of Hamiltonians
Sota Hashimoto, Akinori Kawachi
TL;DR
Hamiltonian function learning asks whether labeled Hamiltonian–state descriptions suffice to predict Tr[f(H)ρ], but rigorous average-case classical hardness had remained open. This paper constructs two distribution-specific problems and proves that an efficient classical learner would yield a polynomial-time factoring algorithm, assuming average-case RSA factoring hardness.
Problem
Morohoshi et al.'s Hamiltonian function learning task had an efficient quantum learner under suitable conditions, but a rigorous proof of average-case classical hardness remained open.
Source: §1 · pp. 1–2Method
Results
A learner with sufficiently small inverse-polynomial squared loss enables recovery of all bits of min{p, q} with probability at least 2/3, yielding a factoring algorithm for either constructed problem.
Source: §1 · pp. 2–3Takeaways & Limitations
Under average-case RSA factoring hardness, the two distribution-specific problems are not efficiently classically learnable under squared loss with classically polynomial-time evaluable hypotheses, even when f is fixed and known.
Source: §1 · p. 2, §3 · p. 5The RSA generator is idealized as always returning a valid triple; bounded-time implementations may fail with negligible probability, adding only a negligible term to probability bounds.
Source: §2 · p. 5
Abstract
from arXiv · showhide
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.
1 Introduction
This paper closes an open question by proving average-case classical hardness for two distribution-specific Hamiltonian function learning problems, assuming random RSA moduli are hard to factor. Its reduction turns an efficient learner into a factoring algorithm by encoding bits of a hidden factor in Hamiltonian predictions.
1 Introduction
- Morohoshi et al. [MNMM25] introduced Hamiltonian function learning to predict Tr[f(H)ρ] from labeled Hamiltonian–state descriptions and gave an efficient quantum learner under suitable conditions.They also implemented the exponential-function case on a superconducting device using up to 40 qubits.Source: §1 · pp. 1–2
- The result adds an average-case hardness proof to earlier arguments that predicting Tr[cos(tH)ρ] should be classically hard for polynomial t, while distinguishing computational hardness from sample-complexity advantages.The introduction contrasts this result with prior learning separations, including work requiring pointwise accuracy, and notes that the present result uses expected squared loss.Source: §1 · pp. 1–2
- Under average-case factoring hardness, neither constructed problem is classically efficiently learnable under squared loss when hypotheses must be classically polynomial-time evaluable.The result applies even when f is fixed and known, using succinct projector Hamiltonians specified by polynomial-size quantum circuits.Source: §1 · p. 2
- The reduction uses a Shor-based verification circuit whose projector Hamiltonian makes the target values for the two bit guesses differ by a constant.For the correct bit, the cosine target is close to −1 and the exponential target is close to e^-β; otherwise both are close to 1.Source: §1 · p. 3
- A learner with sufficiently small inverse-polynomial squared loss lets a classical algorithm recover every bit of min{p, q} from its predictions, factoring the challenge modulus with probability at least 2/3.Training labels come from independently sampled factored RSA moduli, whereas the challenge provides only N.Source: §1 · p. 3
2 Preliminaries
The preliminaries define the regression and Hamiltonian-function-learning models, the RSA modulus distribution, and the average-case factoring assumption used in the hardness result.
2 Preliminaries
- The paper defines f(H) spectrally by applying f to each eigenvalue and retaining its associated projector; cos(tH) and e^-βH are examples.The latter is described as the unnormalized Gibbs operator.Source: §2 · p. 3
- A distribution-specific regression problem has finite instance spaces, a target function, and a labeled-example distribution; learner performance is measured by expected squared loss.Labels need not equal the target value on each instance.Source: §2 · p. 4
- An f-Hamiltonian function learning problem predicts Tr[f(H_x)ρ_x] from classical descriptions of Hamiltonians and states, with Hamiltonian spectra restricted to [0, 1].The paper considers f_cos,t(λ)=cos(tλ) and f_exp,β(λ)=e^-βλ.Source: §2 · p. 4
- Efficient classical learnability requires a randomized polynomial-time learner whose output hypothesis can be evaluated by a deterministic polynomial-time algorithm and achieves the specified squared-loss guarantee.The evaluation requirement is essential because the reduction queries the hypothesis on inputs built from the challenge modulus.Source: §2 · p. 4
- The RSA generator samples triples (N,p,q), while the factoring challenge distribution contains only N; access to sampled factors supports training-label generation but does not factor a challenge modulus.The factors are distinct odd primes and N=pq.Source: §2 · p. 5
- The assumed average-case hardness is that no classical randomized polynomial-time algorithm factors a random RSA modulus with non-negligible probability.The paper idealizes the RSA generator as always returning a valid triple; bounded-time implementations may fail with negligible probability.Source: §2 · p. 5
3 Main Result
Under the average-case hardness assumption for factoring random RSA moduli, the paper proves that two constructed Hamiltonian function learning problems are not efficiently learnable classically under squared loss. The reduction turns an accurate learner into a polynomial-time factoring algorithm.
3 Main Result
- Under the random-RSA factoring assumption, neither constructed problem is efficiently learnable by a classical randomized algorithm under squared loss.An efficient learner for either problem would yield a classical randomized polynomial-time factoring algorithm.Source: §3 · p. 5
- The reduction compares a learner’s predictions on paired inputs for each bit, recovers min{p, q}, and verifies the resulting factorization.The paired inputs can be constructed from the challenge modulus and bit position without knowing its factors.Source: §3 · pp. 5–6
- The construction uses a Shor-based circuit to test whether b matches the corresponding bit of min{p, q}, encoding its acceptance probability in a projector Hamiltonian.The input state is the all-zero state, and each classical input describes the circuit and acceptance projector.Source: §3 · p. 6
- Both problems have efficiently samplable examples and labels, while their target values separate the two choices of b enough to identify each factor bit.The two problems use f(λ) = cos(πλ) and f(λ) = e^(-βλ) for fixed rational β > 0.Source: §3 · pp. 6–7
- The reduction extends beyond factoring to unique polynomial-length witnesses that are quantum-recoverable and classically verifiable, when their recovery is classically hard on average.The paper notes that this framework also applies to suitable injective one-way functions.Source: §3 · p. 9