Classical Hardness of Learning Functions of Hamiltonians

The gist: This paper rigorously proves that for two specific distribution-dependent Hamiltonian function learning problems, an efficient classical randomized learner under squared loss implies an average-case classical polynomial-time algorithm for factoring random RSA moduli

Problem Formulation and Context

The problem studied is Hamiltonian function learning, where the goal is to predict quantities of the form Tr[f(H)ρ] from a classical description of a Hamiltonian H and a quantum state ρ, given labeled examples The authors focus on two specific functions: fcos,π(λ) = cos(πλ) and fexp,β(λ) = e−βλ. These problems are framed as distribution-specific regression problems where the target function is Fn(x):= Tr[f(Hx)ρx]. The construction involves inputs x ∈ Xn being a polynomial-length classical description of a pair of a Hamiltonian Hx and a density operator ρx on m(n) = poly(n) qubits.

The Reduction Strategy

The proof establishes hardness by reducing the efficient learnability of either problem to the average-case hardness of integer factorization. The reduction follows the strategy of Kearns and Valiant. Specifically, given a challenge modulus N ∼ Dn, an efficient classical learner A is used to obtain a hypothesis g from i.i.d. training samples drawn from Den. The algorithm B then uses this hypothesis to recover the factors of N by comparing outputs on inputs constructed from N.

Construction of Hard Instances

The construction for the hard instances involves relating the target function values to a bit, zj:= bit(L(n))j(min[p, q]). For fcos,π-HFL, the target value is defined as ycos,π:= 1 − 2i[b = zj]. For fexp,β-HFL, the target is yexp,β:= 1 − (1 − ecβ,n)i[b = zj]. The input space Xn is defined as Xn:= xN,j,b: N ∈ supp(Dn), j ∈ [L(n)], b ∈ 0, 1. The distributions Pcos,π and Pexp,β are constructed such that they share the same marginal distribution µn on Xn.

Verification of Hardness

Lemma 3.2 establishes the efficiency and target-separation properties required for the reduction. It shows that both Pcos,πn and Pexp,βn are efficiently samplable by classical randomized polynomial-time algorithms. Furthermore, it provides bounds on the target function differences: Fcos,πn(xN,j,b) − 1 − 2i[b = zj] ≤ 2ν(n) and Fexp,βn(xN,j,b) − 1 − (1 − e−β)i[b = zj] ≤ (1 − e−β)ν(n), where ν is a negligible function.

Conclusion of the Proof

The final step involves running the learner A and using Markov’s inequality to show that if Rµn(g) ≤ τ(n), then Pr[N∼Dn,S,A[pb = min[p, q]] ≥ 99/100 > 2/3. This demonstrates that neither problem is efficiently learnable by a classical randomized algorithm under squared loss under the assumption of average-case factoring hardness. The reduction is noted to be more general than stated, applying to problems where recovery of a polynomial-length witness from an input is hard on average for classical randomized polynomial-time algorithms. The paper concludes that under Assumption 2.5, neither problem is efficiently learnable by a classical randomized algorithm under squared loss in the sense of Definition 2.3.

--- Page 9 ---

The final divisibility check succeeds and B outputs p, bNpb = (min[p, q], max[p, q]) >

--- Page 8 ---

The algorithm B runs in classical randomized polynomial time. Since ε(n)−1 = poly(n) and δ(n−1) = 200, the sample size in Step 1 is polynomial in n. Each sample and each challenge input can be generated in polynomial time by Lemma 3.2. By Definition 2.3, A runs in polynomial time and the hypothesis g is evaluable in polynomial time. Since L(n) = poly(n), the reconstruction and divisibility check also take polynomial time. Whenever RN (g) ≤ τ(n), we have pb = min[p, q]. Consequently, Pr(N,p,q)∼Den,S,A[pb = min[p, q]] ≥ 99/100 > 2/3. Whenever pb = min[p, q], the final divisibility check succeeds and B outputs p, bNpb = (min[p, q], max[p, q]) >

--- Page 7 ---

By construction, the two distributions have the same marginal distribution µn on Xn. Define the target functions on Xn by Fcos,πn(x):= Tr[cos(πHx)ρx], Fexp,βn(x):= Tr[e−βHx ρx]. We then set Lcos,π:= (Xn, Fcos,πn,Pcos,πn)n∈N and Lexp,β:= (Xn, Fexp,βn,Pexp,βn)n∈N. By construction these are fcos,π-HFL and fexp,β-HFL problems, respectively in the sense of Definition 2.2.

--- Page 6 ---

We now construct two f-HFL problems with these properties. Fix n ∈ N. Draw (N, p, q) ∼ Den, and choose a bit position j ∈ [L(n)] and a bit b ∈ 0, 1 independently and uniformly at random. Let zj:= bit(L(n))j(min[p, q]). From N, j, b, we construct a polynomial-size quantum circuit UN,j,b based on Shor’s factoring algorithm [Sho97] with success-probability amplification. Any classical random bits used in the factoring procedure are generated coherently using ancillary qubits and retained as part of the workspace, so that UN,j,b is a fixed unitary circuit determined by N, j, b. The circuit coherently performs the factoring procedure with designated registers containing candidate factors (p′, q′) and a designated one-qubit output register o that indicates acceptance or rejection. If the verification succeeds, it computes z:= min[p′, q′] and checks whether b = bit(L(n))j(z). The circuit accepts if this condition is satisfied in at least one repetition, and rejects otherwise. Since N = pq with distinct primes p and q, every valid nontrivial factorization of N yields the same value min[p′, q′].

1. The AI system can be used to break classical randomized polynomial-time algorithms for integer factorization by leveraging an efficient classical learner for Hamiltonian function learning problems. The proof shows that if a classical randomized learner exists under squared loss, it yields a classical randomized polynomial-time algorithm B for factoring a random modulus drawn from Dn.

2. The system can perform quantum advantage demonstrations in machine learning tasks related to predicting quantities of the form Tr[f(H)ρ] from classical descriptions of a Hamiltonian H and a quantum state ρ, specifically for functions like cos(tλ) and exp,β(λ). This is achieved by constructing distribution-specific problems where the target functions are approximated up to negligible error.

3. The AI system can be used to design quantum circuits based on Shor’s factoring algorithm to construct specific projector Hamiltonians, such as HN,j,b:= U†N,j,bΠaccUN,j,b, which are then used as inputs for the Hamiltonian function learning task.

4. The system can identify and exploit structural properties of the target functions that ensure separation between hypotheses; for example, the construction ensures that the target values for b = 0 and b = 1 are separated by a constant: when b equals the j-th bit of min[p, q], the two target values are close to-1 and e − β, respectively.

5. The system can generate training samples from i.i.d. triples sampled from the RSA modulus distribution (Den) to train classical learners for Hamiltonian function learning problems, enabling a reduction to the average-case hardness of factoring random RSA moduli under Assumption 2.5.