{"id":"3a744289-e421-4b21-9c61-391318da134f","arxiv_id":"2504.16370","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A quantum computer can provably learn to predict expectation values of unknown functions of Hamiltonians using Fourier-based features, demonstrated on up to 40 qubits.","lead":"The paper proposes a quantum machine learning task: predict a number computed from an unknown function of a quantum system's energy operator. It proves a quantum computer can learn this from examples and demonstrates the idea on up to 40 qubits.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1 fails for Lipschitz f with f(-C)≠f(C): for f(x)=x and p on H=±I, the Fourier features coincide while labels differ, so the expected loss cannot go below 1.","rationale":"The reader identified the Fourier-expandability assumption as the weakest point, which is the right area, but did not pinpoint the decisive failure: Lipschitz continuity alone does not imply uniform trigonometric approximation on [-C,C] unless f is 2C-periodic (or the support is away from the endpoints). The explicit H=±I counterexample shows that Corollary 1, as stated, is false. This is not merely a missing technical assumption in a corner case; it invalidates the central 'provable quantum easiness' claim for the general Lipschitz class and also means the experimental target e^{-βH} is not covered by the theorem with C=3. The experimental mismatch flagged by the reader (AutoML models, failed 40-qubit run, no error bars) remains a secondary concern. Because the main theoretical guarantee is false as stated, the paper in its current form should be rejected; a substantial revision that adds the correct periodicity or interior-support assumption and adjusts the claims and experiments accordingly could make the argument valid.","tokens_in":17220,"tokens_out":15100,"duration_ms":159314,"concrete_test":"Construct the two-point dataset: C=1, f(x)=x, ρ=|0⟩⟨0|, and p uniform over H=+I and H=-I. For any K, compute the Hamiltonian Fourier features from Eqs. (3)-(5); they are identical for H=+I and H=-I. Train the proposed linear model with any w and verify the expected squared loss is at least 1, contradicting Corollary 1 for ε<1. As a second analytical check, compute the degree-K Fourier partial sums of f(x)=x on [-1,1] and note that the endpoint error |S_K(±1)-f(±1)|=1, independent of K, confirming that the missing periodicity condition is the cause.","verdict_should_be":"REJECT","load_bearing_attack":"Corollary 1 claims that for every Lipschitz f and every distribution p(H,ρ) with ∥H∥≤C, K=O(log(1/ε)/ε) and Nd=O((W∥f∥∞ log(1/ε)/ε)^4) suffice to reach expected squared loss ≤ε. This is false as stated. Take C=1, f(x)=x, ρ=|0⟩⟨0|, and p uniform over H=+I and H=-I. Equations (3)-(5) give xcos,k=Tr[cos(kπ(±I))ρ]=cos(kπ)=(-1)^k and xsin,k=Tr[sin(kπ(±I))ρ]=0 for both signs, so x(+I,ρ)=x(-I,ρ). Every linear model g(H,ρ;w)=w·x therefore outputs the same value v for both Hamiltonians, while the labels are y=Tr[Hρ]=±1. The expected squared loss is ((v-1)^2+(v+1)^2)/2=v^2+1≥1 for every w, every K, and every Nd. Thus the conclusion R(w*)≤ε fails for ε<1. The root cause is that every trigonometric polynomial of period 2C satisfies p(-C)=p(C), so the hypothesis class cannot uniformly approximate Lipschitz functions with f(-C)≠f(C). The cited O(logK/K) Fourier approximation of Lipschitz functions applies to periodic functions; it does not hold on the closed interval for arbitrary Lipschitz functions. The experimental target f(H)=e^{-βH} with C=3 also has e^{-3}≠e^3, so it is outside the stated assumption of Theorem 1. A corrected statement needs a 2C-periodicity condition on f or an assumption that the distribution's spectral support is strictly inside (-C,C).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a supervised quantum machine learning task: predict y = Tr[f(H)ρ] for an unknown scalar function f, given classical descriptions of an n-qubit Hamiltonian H and state ρ. The proposed learner constructs Hamiltonian Fourier features x_k(H,ρ) = Tr[e^{-ikπH/C}ρ] and fits a linear model g(H,ρ;w) = w·x. The main theoretical result, Theorem 1, is a Rademacher-complexity generalization bound; Corollary 1 claims that for Lipschitz f, K = O(log(1/ε)/ε) features and N_d = O((W∥f∥∞ log(1/ε)/ε)^4) samples suffice to reach expected squared loss ε. Appendix B extends the result to noisy feature estimates. The paper reports experiments on IBM Quantum processors with 12, 32, and 40 qubits for f(H) = e^{-βH}, using a protocol that avoids controlled time evolution.","tokens_in":17633,"tokens_out":9278,"duration_ms":84960,"significance":"If the learnability claim is stated correctly, the task is an interesting candidate for a practically relevant learning problem that is provably easy for quantum computers under a Fourier-expandability assumption. The paper's strengths include a self-contained proof via standard Rademacher-complexity tools, an explicit analysis of finite-shot noise, a hardware demonstration with a useful feature-estimation trick, and publicly available code. However, the current statement of Corollary 1 overreaches because it omits the periodicity condition needed for uniform trigonometric approximation, and the experimental section partially validates a different model class at large sizes. With targeted revisions the central idea is sound and the paper could make a solid contribution.","major_comments":[{"comment":"The claim that Lipschitz continuity implies ε_K = O(log K / K) uniformly on [-C,C] is false for functions with f(-C) ≠ f(C), because every 2C-periodic trigonometric polynomial p satisfies p(-C) = p(C). Concretely, take C = 1, f(x) = x, ρ = |0⟩⟨0|, and p uniform over H = +I and H = -I. Equations (3)-(5) give x_{cos,l} = cos(lπ) = (-1)^l and x_{sin,l} = 0 for both H, so the features coincide. Every linear model g(H,ρ;w) = w·x outputs the same value v for both Hamiltonians, while the labels are y = Tr[Hρ] = ±1. The expected squared loss is v² + 1 ≥ 1 for every w, every K, and every N_d, so Corollary 1's conclusion R(w*) ≤ ε fails for any ε < 1. The experimental target f(H) = e^{-βH} with C = 3 also has e^{-3} ≠ e^3 and therefore falls outside the stated assumption. A corrected statement should either require f to be 2C-periodic, or assume that the distribution's spectral support is strictly inside (-C,C) with a margin δ > 0 and make the bound depend explicitly on δ.","section":"Section II, paragraph after Theorem 1 and Corollary 1"},{"comment":"The definition of W is dimensionally inconsistent with its use. The theorem defines W = (1/(2C))∫_{-C}^{C} |f(x)|² dx, which has units of f², but then imposes the weight constraint w^T w ≤ W² and uses W linearly in the bound (7). Under a global scaling f → α f, the right-hand side of (7) would scale as α³ instead of the correct α². The consistent definition is W = sqrt((1/(2C))∫_{-C}^{C} |f(x)|² dx), or another suitable norm of f, and this correction propagates to the sample-complexity expression in Corollary 1 and to Lemma 3. This appears to be a typographical slip, but it must be fixed for the quantitative claims to be meaningful.","section":"Theorem 1, Section II; Appendix A, Lemma 3"},{"comment":"The experimental validation of the proposed linear model (6) is limited to 12 qubits. At 32 and 40 qubits, the QPU regression method selected by PyCaret is ExtraTreesRegressor, which is not of the form g(H,ρ;w) = w·x and for which no learning-theoretic guarantee is given in the paper. The 32-qubit QPU result (R² = 0.889) therefore demonstrates that a non-linear classical regressor can fit the data, not that the Hamiltonian Fourier feature model works at that scale. Moreover, the 40-qubit QPU result has R² = -0.430, which the text itself describes as not providing a meaningful prediction. The abstract and introduction state the method is demonstrated 'up to 40 qubits'; this should be qualified to indicate that the linear feature model is validated on hardware only at 12 qubits, while the larger runs are validated in noiseless MPS simulation and fail under current device noise at 40 qubits.","section":"Section III, Table I and Fig. 2"}],"minor_comments":[{"comment":"The subscript notation in Eq. (3), e.g., 'xcos,k/2', is ambiguous; it should be typeset as x_{cos,k/2} for even k and x_{sin,(k+1)/2} for odd k.","section":"Eq. (3)"},{"comment":"The coefficient sequence {c_k}_{k=0}^{2K} is used as c_{2k} and c_{2k+1}, but the indexing is unclear. It would be cleaner to define two separate sequences {a_k}_{k=0}^{K} and {b_k}_{k=0}^{K-1} for the cosine and sine coefficients.","section":"Theorem 1 statement"},{"comment":"The statement that the TEBD bond dimension χ=100 'gives values essentially equivalent to the exact value with an error less than 10^{-6} at 12 qubits' verifies only the 12-qubit case; for 32 and 40 qubits, no comparison against exact values is provided, so the accuracy of the labels y_j is not established to the same standard.","section":"Section III.B"},{"comment":"The phrase 'strongly believed to be a hard task' understates the status of Hamiltonian simulation: estimating Tr[e^{-itH}ρ] is BQP-complete in the worst case. The genuinely open issue, which the paper correctly identifies, is the average-case hardness needed for the learning separation.","section":"Section II, classical hardness paragraph"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for the journal and the core idea is worth publishing after revision. The main technical blocker is the incorrect Lipschitz-to-Fourier step in Corollary 1; this is fixable by adding a periodicity or spectral-margin condition. The W typo in Theorem 1 should be corrected, and the experimental claims should be aligned with the model actually tested. I would be willing to review a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Good to see this one. The core idea is genuinely new: learning an unknown function f in y = Tr[f(H)rho] from Hamiltonian descriptions, using time-evolved features and a linear model with a Rademacher generalization bound. That's a clean QML task with a polynomial sample guarantee, and the authors are honest that classical hardness remains open. The noise-robustness appendix is a plus, and the code is released.\n\nBut there is a load-bearing error in the statement of Corollary 1. The feature map is 2C-periodic in the eigenvalues of H, so any linear model over these features is 2C-periodic when viewed as a function of those eigenvalues. For a Lipschitz f with f(-C) != f(C), the truncated Fourier series cannot approximate f uniformly on [-C,C]; the classic O(log K/K) convergence applies to periodic functions, not to arbitrary Lipschitz functions on a closed interval. The counterexample is concrete: take C=1, f(x)=x, rho=|0><0|, and p uniform over H=+I and H=-I. Then x_cos,k = cos(k pi) = (-1)^k and x_sin,k = 0 for both H, so the two samples have identical features but labels +1 and -1. No linear model can get expected squared loss below 1, contradicting Corollary 1 for epsilon < 1. This is not cosmetic; it undermines the headline claim of provable easiness for arbitrary Lipschitz f. The fix is standard: assume f is 2C-periodic, or assume the spectral support of H under p is strictly inside (-C,C). The experimental target f(H)=e^{-beta H} on [-3,3] violates the periodicity condition, though it might still satisfy the second condition if the eigenvalue spectra avoid the endpoints.\n\nOther soft spots are minor. The definition of W in Theorem 1 looks dimensionally off: it defines W as an integral of |f|^2 rather than a square root, so the constraint sum c_k^2 <= W^2 is mismatched. Easy to repair, but needs a correction. The 32- and 40-qubit experiments use ExtraTrees, not the linear model from the proof, so the QPU results do not actually demonstrate the proved model. The 40-qubit failure is reported transparently, which I credit. The citation pattern is fine; prior separation tasks use different oracles and different targets, so the novelty claim holds.\n\nOverall: a serious paper with a fixable but real flaw in the central claim. I'd send it to peer review with a request for major revision. Once the periodicity condition is added and the experiments are aligned with the model class, this becomes a citeable contribution.","headline":"A genuinely new QML task with a clean Rademacher bound, but the headline corollary overclaims: the Fourier feature map is periodic, so Lipschitz functions without matching endpoint values break the guarantee.","tokens_in":18173,"tokens_out":2998,"would_cite":false,"duration_ms":29403,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The paper proves that learning an unknown function of a Hamiltonian inside the expression $\\mathrm{Tr}[f(H)\\rho]$ is provably easy for quantum computers, with explicit polynomial feature and sample counts, and demonstrates the linear…","keywords":["quantum machine learning","Hamiltonian Fourier features","linear regression","Fourier series approximation","sample complexity","Hamiltonian simulation","superconducting qubits","generalization bound"],"falsifier":"A direct test is to seek a classical polynomial-time algorithm that estimates $\\mathrm{Tr}[\\cos(tH)\\rho]$ for random few-body Hamiltonians with $t=\\mathrm{poly}(n)$; if such an algorithm exists, the argued quantum advantage collapses. A second test is to find a Lipschitz $f$ satisfying the theorem's hypotheses whose actual required $K$ and $N_d$ outgrow the stated polynomial bounds, which would contradict Corollary 1.","tokens_in":17014,"feed_emoji":"⚛️","tokens_out":17078,"duration_ms":153192,"temperature":0.7,"pith_summary":"This paper proposes a machine-learning task, predicting $y=\\mathrm{Tr}[f(H)\\rho]$ from descriptions of $H$ and $\\rho$ when $f$ is unknown, and claims that the task is provably easy for a quantum computer whenever $f$ has a rapidly converging Fourier series on $[-C,C]$. The learner uses Hamiltonian Fourier features, the real and imaginary parts of $\\mathrm{Tr}[e^{-il\\pi H/C}\\rho]$, and fits a linear model by regression. The main theorem bounds expected squared loss by a Fourier truncation term plus a sample-size term; for Lipschitz $f$ this gives $K=O(\\log(1/\\varepsilon)/\\varepsilon)$ features and $N_d=O((W\\|f\\|_\\infty \\log(1/\\varepsilon)/\\varepsilon)^4)$ samples to reach error $\\varepsilon$. The same guarantee is shown to survive bounded measurement noise with polynomially many shots, and the paper reports experimental regressions on a superconducting processor at 12, 32, and 40 qubits, with the two smaller systems reaching high test $R^2$ and the 40-qubit run dominated by device noise. The practical interest is that this is one of the few concrete learning problems with a polynomial quantum sample-complexity proof and a plausible, though not rigorous, classical-hardness argument.","feed_headline":"Provably easy: a Fourier feature map learns functions of Hamiltonians","feed_subtitle":"A Fourier-style feature map turns the task into linear regression with polynomial sample cost.","key_machinery":"The load-bearing object is the Hamiltonian Fourier feature vector $x(H,\\rho)=(x_0,\\ldots,x_{2K})$, whose even entries are $\\mathrm{Re}\\,\\mathrm{Tr}[e^{-il\\pi H/C}\\rho]$ and odd entries are $\\mathrm{Im}\\,\\mathrm{Tr}[e^{-il\\pi H/C}\\rho]$ for $l=0,\\ldots,K$. These features are the Fourier coefficients of the spectral measure of $H$ against $\\rho$, so the linear model $g=w\\cdot x$ is a truncated Fourier series in the eigenvalues of $H$. The key properties that make the proof work are that each feature has magnitude at most 1, so the feature Gram matrix has trace at most $(2K+1)N_d$, and that the constrained weight class $\\{w^Tw\\le W^2\\}$ has a tractable generalization bound; this separates the approximation error, controlled by the Fourier truncation $\\varepsilon_K$, from the estimation error, controlled by the sample count $N_d$. The same machinery extends to noisy features by adding a deterministic term linear in the per-feature noise level $\\eta$.","core_discovery":"The central discovery is that $f(H)$ inside a trace can be learned by expanding it as a Fourier series in the eigenvalues of $H$ and using quantum-evolution expectation values as features. Concretely, Theorem 1 states that for any $f$ admitting a uniform Fourier approximation on $[-C,C]$ with coefficient norm bound $W$, the minimizer of empirical squared loss over the linear model $g(H,\\rho;w)=w\\cdot x(H,\\rho)$ with $x(H,\\rho)$ built from real and imaginary parts of $\\mathrm{Tr}[e^{-ik\\pi H/C}\\rho]$ achieves expected loss bounded by $\\varepsilon_K^2$ plus generalization terms that go to zero as the sample count $N_d$ grows. Corollary 1 specializes this to Lipschitz $f$, where $\\varepsilon_K=O(\\log K/K)$, so $K=O(\\log(1/\\varepsilon)/\\varepsilon)$ and $N_d=O((W\\|f\\|_\\infty\\log(1/\\varepsilon)/\\varepsilon)^4)$ suffice for expected loss at most $\\varepsilon$. The proof bounds every feature by 1, uses a standard generalization bound for constrained linear models, and notes that the empirical loss at the Fourier coefficients is at most $\\varepsilon_K^2$. Theorem 2 extends the result to noisy features, requiring $O(\\log(K/\\delta)/\\eta^2)$ shots per feature, and the hardware experiments with $f(H)=e^{-\\beta H}$ use a reference-eigenstate identity to measure features without controlled time evolution.","pith_inferences":["Editorial inference: the feature vector defines a kernel $K((H,\\rho),(H',\\rho'))=x(H,\\rho)^T x(H',\\rho')$, so the same construction could be reused for kernel-based learning of other Hamiltonian-dependent targets; the paper does not pursue this.","Editorial inference: the $W^4$ dependence in the sample bound is the quantity most likely to become impractical as $f$ becomes less smooth; testing the method on a sharp-cornered Lipschitz function with a large Fourier coefficient norm would map where the provable-easiness guarantee stops being useful in practice.","Editorial inference: the classical-hardness argument is informal because it relies on worst-case simulation hardness, so a rigorous separation would need average-case hardness over the training distribution; a concrete route is to instantiate the task with Hamiltonians that encode a quantum computation believed hard on average, a direction the paper mentions but leaves open."],"forward_implications":["For Lipschitz-continuous $f$, any target error $\\varepsilon$ is reached with $K=O(\\log(1/\\varepsilon)/\\varepsilon)$ features and $N_d=O((W\\|f\\|_\\infty\\log(1/\\varepsilon)/\\varepsilon)^4)$ samples, placing the task among the few supervised learning problems with a polynomial quantum sample-complexity guarantee.","Because the features are values of time evolution generated by $H$, choosing $f(H)=\\cos(tH)$ or $\\sin(tH)$ makes the learned label a Hamiltonian-simulation output; if simulation of such Hamiltonians is classically hard, the task provides a learning separation with practical-looking instances.","The reference-eigenstate identity used in the experiments lets features be obtained without controlled time evolution for Hamiltonians with a known eigenstate orthogonal to the input state, which is what allows near-term demonstrations on current devices.","The noise analysis says that estimating each feature with $O(\\log(K/\\delta)/\\eta^2)$ shots is enough to keep the expected-loss guarantee polynomial, so the protocol remains learnable under finite measurement statistics.","In the reported demonstrations, the 12- and 32-qubit regressions achieve test $R^2$ above 0.8, while the 40-qubit run gives no meaningful prediction, indicating device noise rather than the learning model as the practical bottleneck."],"supporting_citations":[{"why":"Supplies the Fourier truncation rate $\\varepsilon_K=O(\\log K/K)$ for Lipschitz functions, fixing the feature count $K$ in Corollary 1.","marker":"[12]"},{"why":"Provides the Rademacher-complexity and generalization lemmas used in Appendix A to prove Theorem 1 and its noisy-feature extension.","marker":"[24]"},{"why":"Gives the reference-eigenstate identity (Eq. 8) used to estimate Hamiltonian Fourier features without controlled time evolution, enabling the hardware demonstrations.","marker":"[15]"},{"why":"Cited as the basis for believing Hamiltonian simulation is classically hard, which underlies the argued quantum advantage for $f(H)=\\cos(tH)$ and $\\sin(tH)$.","marker":"[13]"},{"why":"Recent Hamiltonian-simulation complexity results cited alongside [13] to support the informal classical hardness of the task.","marker":"[14]"}],"fun_headline_variants":["Fourier features turn Hamiltonian learning into easy linear regression","Provably easy quantum ML: Fourier features learn functions of Hamiltonians","Hamiltonian Fourier features: quantum-easy learning, near-term feasible","Learn f(H) with Fourier features: provably easy for quantum computers","Fourier feature map learns Hamiltonian functions with provable ease"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The quantum-easiness guarantee holds only for functions $f$ whose expansion into sine and cosine waves on $[-C,C]$ converges quickly and has bounded total squared weight; for functions with slowly decaying expansion coefficients, neither the stated feature count nor the stated sample count is guaranteed to be enough.","fun_headline_variants_meta":{"raw":{"variants":["Fourier features turn Hamiltonian learning into easy linear regression","Provably easy quantum ML: Fourier features learn functions of Hamiltonians","Hamiltonian Fourier features: quantum-easy learning, near-term feasible","Learn f(H) with Fourier features: provably easy for quantum computers","Fourier feature map learns Hamiltonian functions with provable ease"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000397,"raw_usage":{"total_tokens":2076,"prompt_tokens":941,"completion_tokens":1135,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":1046}},"tokens_in":557,"tokens_out":1135,"duration_ms":8343,"temperature":1.0,"reasoning_tokens":1046,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:06:31.058406+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct test is to seek a classical polynomial-time algorithm that estimates $\\mathrm{Tr}[\\cos(tH)\\rho]$ for random few-body Hamiltonians with $t=\\mathrm{poly}(n)$; if such an algorithm exists, the argued quantum advantage collapses. A second test is to find a Lipschitz $f$ satisfying the theorem's hypotheses whose actual required $K$ and $N_d$ outgrow the stated polynomial bounds, which would contradict Corollary 1.","supporting_citations":[{"cited_title":"KX k=0 w2k cos(kπλi,l/C) + K−1X k=0 w2k+1 sin(kπλi,l/C) # pl !2 (A7) = 1 Nd NdX i=1","cited_arxiv_id":null,"evidence_quote":"Provides the Rademacher-complexity and generalization lemmas used in Appendix A to prove Theorem 1 and its noisy-feature extension."},{"cited_title":"Salem and A","cited_arxiv_id":null,"evidence_quote":"Supplies the Fourier truncation rate $\\varepsilon_K=O(\\log K/K)$ for Lipschitz functions, fixing the feature count $K$ in Corollary 1."},{"cited_title":"Kyriienko, npj Quantum Information 6, 7 (2020)","cited_arxiv_id":null,"evidence_quote":"Gives the reference-eigenstate identity (Eq. 8) used to estimate Hamiltonian Fourier features without controlled time evolution, enabling the hardware demonstrations."}],"review_version":1}