{"id":"a6bc7f53-d6d2-4bca-aee2-c941fb7b0a49","arxiv_id":"2501.01154","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Simulations show a one-clean-qubit algorithm estimates partition functions of small binary Markov random fields, with errors matching the expected sample-size trend.","lead":"The paper applies a known quantum algorithm, the one clean qubit partition function estimator, to a binary Markov random field used for radar anomaly detection. The authors simulate the circuit in Qiskit for tiny graphs and report estimation errors that shrink as the number of samples grows.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (23)-(24) trace normalization is the load-bearing step: every reported error depends on the unmotivated factor 2^{n+m'}, so the central implementation claim stands or falls on this formula.","rationale":"The reader's weakest_assumption identifies exactly Eq. (23)-(24): the relation between the DQC1 measurement outcome and the Chebyshev matrix element is taken from [9] and [11] without derivation. I agree this is the most load-bearing point. The rest of the algorithm structure is either standard or explicitly acknowledged as unsupported: the LCU coefficient normalization is actually consistent because, after expanding each B = (I - Z)/2 and using sum |theta_ij| = 1, the sum of absolute LCU coefficients is 1; the Chebyshev approximation and sample-complexity formulas follow the cited works. The trace-normalization step, however, is where a small algebraic error would silently invalidate every quantitative result in the paper. The reported 1-10% errors in Tables I and II depend linearly on the factor 2^{n+m'}, so an off-by-one in the exponent or a wrong trace relation would make those errors meaningless. Since the paper also provides no code, no raw data, and no independent verification of the circuit-to-trace relation, the conditional verdict is the correct disposition: the central claim is plausible but not established until Eq. (23) is independently re-derived or validated by a density-matrix simulation. Therefore I do not move the reader's verdict; I only reinforce the same conditional status.","tokens_in":9017,"tokens_out":17696,"duration_ms":177045,"concrete_test":"Simulate the exact n=2 instance from Section IV in a density-matrix simulator: construct U_k from Eq. (20) as an explicit 2^{n+2m'} x 2^{n+2m'} matrix, compute p0 - p1 for the DQC1 circuit of Fig. 3, and compare with T_k(H)/2^{n+m'} obtained by exact diagonalization of H_C. Repeat for k = 1, 2, 3. If the measured difference does not equal T_k(H)/2^{n+m'} to machine precision, the normalization in Eqs. (23)-(24) is wrong and the reported errors in Table I are not estimates of the partition function. If the identity holds, the conditional acceptance can stand.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The one-clean-qubit circuit of Fig. 1 can estimate only a normalized trace: Eq. (10) gives p0 - p1 = Re(Tr(U_k))/2^q with q = n + 2m' mixed qubits. The paper's Eq. (23)-(24) instead asserts T_k(H) = 2^{n+m'}(p0 - p1), which requires the nontrivial identity Re(Tr(U_k)) = 2^{m'} T_k(H), where T_k(H) is the block-encoding matrix element in Eq. (17), not a trace. This identity is not derived in the paper; Eqs. (20)-(21) are too compressed to verify it, and it is the exact point where the algorithm's output is converted into the quantity used to build the partition function estimate. A missing factor of 2^{m'} or an incorrect construction of the Bell-pair/controlled-X register would change every chi_k and hence every partition function estimate in Table I. Since the paper's headline quantitative claim is 'error of approximately 10% for n=4 with only 10^4 samples, instead of approximately 10^9,' this normalization is the single most load-bearing assumption in the paper. No code or raw data are provided, so the reported error tables cannot independently confirm or refute the formula.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper applies the one-clean-qubit (DQC1) partition-function estimation algorithm of Chowdhury, Somma, and Subaşı [9] to a binary Markov random field used for radar anomaly detection. The authors encode a binary quadratic energy function as a Hamiltonian Hθ, expand exp(−βH) in Chebyshev polynomials, construct the qubitization walk operator WH, and estimate the terms Tr(T_k(H)) by measuring a clean control qubit after a controlled version of a unitary Uk. Numerical Qiskit simulations for n=2,3,4 graph sizes are reported, showing that average relative errors decrease with sample count Q and Chebyshev order K, and that empirically far fewer samples than the theoretical bound are needed.","tokens_in":9274,"tokens_out":12493,"duration_ms":113836,"significance":"If the implementation is correct, this is a useful concrete validation of the one-clean-qubit partition-function protocol on a problem of practical interest, and it provides a clean formulation of a binary quadratic MRF energy as a linear combination of unitaries. The paper is honest about its limitations: it uses simulation only, studies small n, and does not analyze gate cost. It also correctly benchmarks against exactly enumerated partition functions, so the reported errors are not circular. The main caveats are that the conversion from the measured probability difference to the trace of the Chebyshev operator is asserted rather than derived, and the empirical claims lack error bars and code; both issues are addressable in revision.","major_comments":[{"comment":"The conversion from the measured probability difference to Tr(T_k(H)) is the load-bearing step of the implementation, but it is not derived. From the one-clean-qubit circuit, (p0−p1) = Re(Tr(Uk))/2^{n+2m'}, so the asserted identity Tr(T_k(H)) = 2^{n+m'}(p0−p1) is equivalent to Re(Tr(Uk)) = 2^{m'} Tr(T_k(H)). The paper does not show how Uk defined by Eqs. (20)-(21) satisfies this; the sentence about controlled-X gates 'such that |1⟩ states do not contribute to the trace' is insufficient to verify it. In addition, Eq. (23) equates the operator T_k(H) to a scalar; the left-hand side should be Tr(T_k(H)). Since every entry of Tables I and II depends on this formula, a step-by-step derivation or an explicit pointer to the corresponding lemma in [9] with equation numbers is required.","section":"Section III-D, Eqs. (20)-(24)"},{"comment":"Eq. (25) defines Z_C = ∑_{x_C} F_C(x_C), which is not a partition function; the correct expression is Z_C = ∑_{x_C} exp(F_C(x_C)). Although Eq. (28) later uses the correct exponential form, the definition as written makes the normalization of p_C inconsistent with the quantity actually computed and must be corrected.","section":"Section IV-A, Eq. (25)"},{"comment":"The headline claim that 'we obtained an error of approximately 10% for n=4 with only 10^4 samples, instead of approximately 10^9 as stated in [9]' overstates the comparison. Qth in Eq. (29) is a worst-case sufficient sample-complexity bound; observing smaller empirical errors on n=2 to 4 does not contradict [9]. The claim would be trustworthy only if the authors report the definition of the empirical error, the number of random graphs used in each average, and the standard deviation or per-graph errors. Without error bars, the 10% figure is not statistically supported.","section":"Section V-C, Table I"},{"comment":"No code or raw simulation data are provided, and the tables report only averaged errors. To permit independent verification of the central empirical claim, the authors should either release the Qiskit code or provide per-instance errors and a precise description of the random graph generation procedure (including the distribution of the nonzero θij entries).","section":"Section V, Tables I and II"}],"minor_comments":[{"comment":"The Chebyshev expansion of exp(−βH) presupposes the normalization ‖H‖ ≤ 1; the text states this, but the effect of renormalization on β should be stated explicitly so readers can reproduce the parameter choices in Tables I and II.","section":"Section II-B, Eq. (6)"},{"comment":"The matrix Θ in Eq. (27) is upper triangular, while the text describes an undirected pairwise MRF; please clarify whether the lower-triangular entries are zero by convention or the graph is directed.","section":"Section IV-B, Eq. (27) and Fig. 4"},{"comment":"After Eq. (10), the statement that one can estimate the trace 'to precision ε > 0 by measuring the ancillary qubit O(1/ε^2) times' should mention the dependence on the success probability, since Eq. (29) later uses δ.","section":"Section III-A, Eq. (10)"},{"comment":"Eq. (18) writes Re(Tr(⟨0|(In⊗P′)(WH)^k(In⊗P′†)|0⟩)), but the trace is redundant: the object ⟨0|...|0⟩ is already an n-qubit operator, and the desired scalar is its trace. This notation should be cleaned up, preferably as Re(Tr(T_k(H))).","section":"Section III-C, Eq. (18)"},{"comment":"The description of preparing a maximally mixed state by applying Hadamard and controlled-X gates to each qi in |0⟩ is a purification for simulation purposes, not the actual one-clean-qubit preparation; the text should state this distinction more clearly.","section":"Section V-B"},{"comment":"There are numerous typos and spacing artifacts in the abstract and body (e.g., 'distribu tion', 'stat istical', 'efficiently'); a careful proofread is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The trace-normalization issue in Section III-D is the main barrier to accepting the implementation claim. The formula is likely correct when Eq. (23) is read as Tr(T_k(H)) = 2^{n+m'}(p0−p1), but the paper must supply the missing derivation and fix the operator/scalar mismatch. The excessive confidence in the empirical sample counts can be remedied with proper statistics. The paper fits the journal's scope as an application of quantum simulation techniques to a statistical anomaly-detection problem, and the revision path is clear."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: the paper implements a known one-clean-qubit partition function estimator from Chowdhury et al. and applies it to tiny binary MRFs via a diagonal Hamiltonian encoding. The mapping is elementary but clearly explained, and the validation against exact enumeration is honest. The whole quantitative story, however, rests on Eqs. (23)-(24), which convert the measured probability difference into T_k(H) with a 2^{n+m'} prefactor. That step is not derived; it is taken from [9] and [11]. The stress-test concern is legitimate: Eq. (10) gives p0-p1 = Re(Tr(U_k))/2^{n+2m'}, so Eq. (24) requires Re(Tr(U_k)) = 2^{m'} T_k(H), where T_k(H) is the block-encoding matrix element from Eq. (17), not a trace. This identity is not obvious, and a missing 2^{m'} would change every chi_k and every partition function estimate. No code or raw data are provided, so the reported errors cannot be independently confirmed.\n\nWhat is good: the paper is honest about its scope. It does not claim a new algorithm, it acknowledges the absence of hardware runs, and it explicitly declines to analyze computational cost. The Chebyshev truncation discussion and the comparison with the theoretical sample counts are sensible, though the \"better than theory\" claim is based on n=2-4 and worst-case bounds, so it is suggestive at best. The application context (radar anomaly detection) is a real motivation, but the paper does not show that the quantum route has any advantage over classical exact enumeration for the sizes considered.\n\nSoft spots, in order: (1) the underived normalization in Eq. (23), (2) no code/data release, (3) no classical baseline or complexity analysis, (4) the scalability discussion is mostly back-of-the-envelope. These are significant, but the paper is not incoherent; it is a plausible engineering report that needs verification.\n\nWho this is for: someone working on applications of DQC1 to statistical physics or graphical models might find the encoding useful. I would not cite it as a result until Eq. (23) is independently checked. But I would send it to a serious referee: the correctness question is real and can be resolved with a derivation or code, and the paper deserves that attention rather than a desk reject.\n\nBest.","headline":"Known algorithm applied to tiny binary MRFs; plausible simulation but the load-bearing trace normalization is taken on faith and needs verification.","tokens_in":9811,"tokens_out":11116,"would_cite":false,"duration_ms":97910,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims a one-clean-qubit quantum circuit can estimate a Markov random field's partition function to about 10% error using thousands of samples, far fewer than the theoretical bound of roughly a billion.","keywords":["partition function estimation","one clean qubit model","DQC1","Markov random field","radar anomaly detection","Chebyshev polynomials","linear combination of unitaries","quantum circuit simulation"],"falsifier":"Recompute the exact partition function for the $n=4$ graph in Eq. (27) by enumerating all 16 configurations, run the same simulated circuit with $Q=10^4$ samples, and check whether the estimate lies within about 10% of the exact value and whether the measured $p_0-p_1$ satisfies the stated identity for the exact $\\operatorname{Tr}(T_k(H))$. A systematic mismatch would settle the claim against the paper.","tokens_in":8818,"feed_emoji":"⚛️","tokens_out":9431,"duration_ms":81122,"temperature":0.7,"pith_summary":"The paper tries to establish that partition-function estimation for a binary Markov random field is within reach of a small quantum circuit, not just a theoretical construction. It implements, in a quantum circuit simulator, the one clean qubit (DQC1) algorithm that estimates $\\operatorname{Tr}(e^{-\\beta H})$ by expanding $e^{-\\beta H}$ in Chebyshev polynomials and measuring traces of the resulting walk operator. On graphs with two to four binary nodes, the simulation estimates $Z_C=\\sum_{x\\in\\{0,1\\}^n} e^{x^T\\Theta x}$ with errors around 1% to 10% using between $10^3$ and $10^7$ samples, and the authors emphasize that $10^4$ samples already give roughly 10% error for $n=4$, whereas the theoretical sample bound in the underlying algorithm is about $10^9$. The stated motivation is radar anomaly detection, where a Gibbs distribution over many operating variables needs to be normalised by its partition function, and exact enumeration is impossible for larger graphs.","feed_headline":"A quantum circuit cuts partition-function samples from 10^9 to 10^4","feed_subtitle":"Simulated one-clean-qubit estimator reaches ~10% error on small radar Markov random fields.","key_machinery":"The load-bearing object is the walk operator $W_H = (I\\otimes(2|P'\\rangle\\langle P'|-I))\\, X\\, S'$, assembled from a \"prepare\" oracle $P$, a \"select\" oracle $S$, and a zero-reflection operator of the form $2|0\\rangle\\langle0|-I$; applied $k$ times between state preparations it produces the $k$-th Chebyshev polynomial $T_k(H)$ in block-encoded form. Measuring the clean qubit that controls this operator gives $\\chi_k \\approx \\operatorname{Re}\\operatorname{Tr}(T_k(H))$, and the partition function is reconstructed from the Chebyshev expansion $Z = \\operatorname{Tr}(e^{-\\beta H}) \\approx I_0(\\beta)2^n + 2\\sum_{k=1}^K (-1)^k I_k(\\beta)\\chi_k$. The one clean qubit model is what makes the trace measurement possible: one pure control qubit plus a maximally mixed register, with the trace read off from the probability difference $p_0-p_1$.","core_discovery":"The central claim is that a binary quadratic Markov random field partition function can be estimated by (i) forming a Hamiltonian $H_C$ whose eigenvalues are the energies $x^T\\Theta x$ of every configuration, (ii) block-encoding $H_C$ as a linear combination of unitaries, and (iii) using the one clean qubit model to measure the real part of the trace of the Chebyshev-polynomial walk operator $W_H$. The reported simulations for $n=2,3,4$ show the estimate converging quickly with sample count and with Chebyshev order $K$, with errors of a few percent once $Q=10^5$; the paper reads this as evidence that the theoretical worst-case sample and gate counts are loose for these instances. It also gives a qubit-count scaling argument: on a hypothetical 1121-qubit quantum computer, ignoring hardware noise, the same construction could handle a binary MRF of roughly 186 nodes, whose partition function would have about $10^{56}$ terms.","pith_inferences":["The large gap between the theoretical sample bound and the simulated sample count suggests that the worst-case bound is driven by generic unitaries; for the diagonal, sparse Hamiltonians used here the trace estimator's variance may scale with the number of nonzero couplings rather than the full dimension, a claim the paper does not make and that could be tested by varying the sparsity of $\\Theta$.","A natural next step, not taken in the paper, is to run the same circuits for $n=2$ or $n=3$ on actual hardware with error mitigation; the paper explicitly sets hardware noise aside, so its 10% error figure is a noiseless upper bound on performance.","The same Chebyshev-trace recipe should apply to other diagonal-Hamiltonian partition functions, such as sparse Ising models, where classical methods like annealed importance sampling also struggle; comparing the two on identical instances would quantify the quantum advantage more directly."],"forward_implications":["For small binary MRFs, the one-clean-qubit estimator reaches roughly 10% error with about $10^4$ runs, so practical experiments need far fewer shots than the $10^9$-scale theoretical bound.","Chebyshev order $K$ beyond 2 or 3 changes the error by only a few tenths of a percent for $n\\le 4$, so short-depth circuits may preserve accuracy.","Ignoring hardware noise, a 1121-qubit machine could in principle represent a binary MRF with up to about 186 nodes, a partition function with roughly $10^{56}$ terms.","The Hamiltonian encoding of any binary quadratic form generalises beyond radar data, giving a recipe for estimating partition functions of arbitrary binary pairwise MRFs."],"supporting_citations":[{"why":"Supplies the one-clean-qubit partition function algorithm, the Chebyshev expansion of $e^{-\\beta H}$, and the theoretical sample bound $Q$.","marker":"[9]"},{"why":"Provides the linear-combination-of-unitaries / block-encoding construction that defines the walk operator.","marker":"[11]"},{"why":"Introduces the one clean qubit model and DQC1 trace estimation via a controlled unitary.","marker":"[12]"},{"why":"Justifies the controlled-X restoration trick used to prepare the pure-state ancillas inside $U_k$.","marker":"[13]"},{"why":"Defines the Chebyshev polynomials used to expand the Boltzmann operator.","marker":"[10]"},{"why":"Defines the mixed graphical model for radar anomaly detection whose partition function is the target.","marker":"[3]"},{"why":"Provides the sparse pairwise Markov model and graph construction for heterogeneous radar data.","marker":"[4]"},{"why":"Supplies the zero-reflection operator used in the walk operator.","marker":"[16]"},{"why":"Shows that LCU Hamiltonian simulation has polynomial gate complexity, supporting the scalability argument.","marker":"[17]"}],"fun_headline_variants":["Quantum circuit estimates radar MRF partition functions with far fewer samples","One clean qubit model speeds up MRF partition function estimation","Quantum estimator for radar Markov random field partition functions","Exponential quantum scaling for MRF partition functions in radar anomaly detection"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The weakest link is the unproved measurement identity $T_k(H)=2^{n+m'}(p_0-p_1)$, taken from the algorithm's source rather than derived here; if the circuit that builds $U_k$ or the $2^{n+m'}$ scaling is wrong, every reported error estimate is invalid.","fun_headline_variants_meta":{"raw":{"variants":["Quantum circuit estimates radar MRF partition functions with far fewer samples","One clean qubit model speeds up MRF partition function estimation","Quantum estimator for radar Markov random field partition functions","Exponential quantum scaling for MRF partition functions in radar anomaly detection"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000687,"raw_usage":{"total_tokens":3094,"prompt_tokens":906,"completion_tokens":2188,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":2119}},"tokens_in":522,"tokens_out":2188,"duration_ms":17162,"temperature":1.0,"reasoning_tokens":2119,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:34:08.303471+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the exact partition function for the $n=4$ graph in Eq. (27) by enumerating all 16 configurations, run the same simulated circuit with $Q=10^4$ samples, and check whether the estimate lies within about 10% of the exact value and whether the measured $p_0-p_1$ satisfies the stated identity for the exact $\\operatorname{Tr}(T_k(H))$. A systematic mismatch would settle the claim against the paper.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the one-clean-qubit partition function algorithm, the Chebyshev expansion of $e^{-\\beta H}$, and the theoretical sample bound $Q$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the linear-combination-of-unitaries / block-encoding construction that defines the walk operator."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the one clean qubit model and DQC1 trace estimation via a controlled unitary."},{"cited_title":"C., & Handscomb, D","cited_arxiv_id":null,"evidence_quote":"Defines the Chebyshev polynomials used to expand the Boltzmann operator."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the mixed graphical model for radar anomaly detection whose partition function is the target."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the sparse pairwise Markov model and graph construction for heterogeneous radar data."}],"review_version":1}