Pith. sign in

REVIEW 4 major objections 6 minor 21 references

Quantum Computing for Partition Function Estimation of a Markov Random Field in a Radar Anomaly Detection Problem

T0 review · 4 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Pith's one-line read 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.

desk verdict Known algorithm applied to tiny binary MRFs; plausible simulation but the load-bearing trace normalization is taken on faith and needs verification. read the letter →

arxiv 2501.01154 v1 pith:36RJHR76 submitted 2025-01-02 cs.ET quant-ph

classification cs.ETquant-ph MSC 81P6868Q12
keywords partitionfunctionestimationonecleanqubitmodelDQC1MarkovrandomfieldradaranomalydetectionChebyshevpolynomialslinearcombinationofunitariesquantumcircuitsimulation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

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.

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 (4)
  1. [Section III-D, Eqs. (20)-(24)] 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.
  2. [Section IV-A, Eq. (25)] 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.
  3. [Section V-C, Table I] 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.
  4. [Section V, Tables I and II] 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).
minor comments (6)
  1. [Section II-B, Eq. (6)] 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.
  2. [Section IV-B, Eq. (27) and Fig. 4] 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.
  3. [Section III-A, Eq. (10)] 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 δ.
  4. [Section III-C, Eq. (18)] 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))).
  5. [Section V-B] 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.
  6. [Throughout] There are numerous typos and spacing artifacts in the abstract and body (e.g., 'distribu tion', 'stat istical', 'efficiently'); a careful proofread is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

The paper's central quantitative claim is an implementation benchmark against exactly enumerated partition functions, not a reduction to fitted or self-cited inputs.

full rationale

I walked the derivation chain from the MRF partition function Z_C = Tr(e^{H_theta}) (Eqs. (25)-(28)) through the Chebyshev expansion (Eqs. (6)-(8)), the block-encoded Hamiltonian and walk operator (Eqs. (11)-(17)), and the one-clean-qubit trace estimate (Eqs. (10), (20)-(24)). The reported errors in Tables I and II compare the simulated estimate to the exact partition function of the small graph, so the error metric is not manufactured by a fit or by reusing the quantity being predicted. The comparison against the 10^9 sample-count bound in [9] is an external, falsifiable benchmark: the paper's own simulation uses 10^4 samples and an independent exact Z as ground truth. No parameter is fitted to the target partition function, and no ansatz is smuggled in by the authors' prior work. The load-bearing normalization T_k(H)=2^{n+m'}(p0-p1) in Eqs. (23)-(24) is asserted from Refs. [9] and [11] rather than derived, which is a correctness and verification risk, not a circularity: T_k(H) is defined independently in Eq. (17), and the measurement formula is imported from external papers rather than defined in terms of the desired output. The only self-citations ([3], [4]) supply the radar anomaly-detection problem, the MRF formulation, and the example graph; none of them forces the quantum estimation result. I therefore find no significant circularity; the principal open concern is the unverified imported identity in Eqs. (23)-(24), not a self-referential derivation.

Assumptions & free parameters 6 free parameters · 4 assumptions · 0 invented entities

The central claim rests on established quantum algorithms and simulation assumptions rather than new postulated entities. The listed free parameters are experimental settings and normalization choices, not constants fitted to hide a derivation gap.

free parameters (6)
  • beta = 1
    Inverse temperature set to 1 in Eq. (28). Chosen by hand, not fitted, but it is an adjustable input to the algorithm.
  • K = 3 in Table I, 1 to 5 in Table II
    Chebyshev truncation order chosen to test accuracy; theoretical Kth from Eq. (30) is 10 to 12.
  • Q = 10^3 to 10^7
    Number of measurement samples; chosen to explore error versus sample count.
  • epsilon_abs = 0.1
    Target absolute error used in Eqs. (7) and (29).
  • delta = 0.1
    Failure probability used in Eq. (29).
  • coefficient normalization = sum |theta_ij| = 1
    Chosen to satisfy the norm bound ||H|| <= 1 needed for the Chebyshev expansion; not fitted.
assumptions (4)
  • standard math The Chebyshev expansion of e^{-beta H} converges with exponentially decaying Bessel coefficients and can be truncated with a controlled error bound.
    Invoked in Eqs. (6)-(8) following [9]; the convergence and error bound are imported without re-derivation.
  • domain assumption The Hamiltonian can be represented as a linear combination of unitaries with positive coefficients summing to 1, enabling block encoding with prepare and select oracles.
    Required for Eqs. (11)-(14); the paper states negative signs can be cast into the unitaries, but the explicit decomposition is not fully given.
  • domain assumption The one-clean-qubit circuit yields a probability difference proportional to the real part of the trace of the implemented unitary.
    Imported from [9], [12], and [13]; not re-derived in this paper.
  • domain assumption The simulation is noiseless and hardware errors are ignored.
    Section V-A explicitly excludes NISQ errors from the reported results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Computing for Partition Function Estimation of a Markov Random Field in a Radar Anomaly Detection Problem." pith.science (2026). https://pith.science/paper/36RJHR76

@misc{pith2026250101154,
  author       = {Pith},
  title        = {Pith review of: Quantum Computing for Partition Function Estimation of a Markov Random Field in a Radar Anomaly Detection Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/36RJHR76}},
  note         = {Machine review of arXiv:2501.01154}
}
read the original abstract

In probability theory, the partition function is a factor used to reduce any probability function to a density function with total probability of one. Among other statistical models used to represent joint distribution, Markov random fields (MRF) can be used to efficiently represent statistical dependencies between variables. As the number of terms in the partition function scales exponentially with the number of variables, the potential of each configuration cannot be computed exactly in a reasonable time for large instances. In this paper, we aim to take advantage of the exponential scalability of quantum computing to speed up the estimation of the partition function of a MRF representing the dependencies between operating variables of an airborne radar. For that purpose, we implement a quantum algorithm for partition function estimation in the one clean qubit model. After proposing suitable formulations, we discuss the performances and scalability of our approach in comparison to the theoretical performances of the algorithm.

Figures

Figures reproduced from arXiv: 2501.01154 by the authors.

Figure 1
Figure 1. Circuit for estimating Re(Tr(U))/2 q in the one clean qubit model. time by the one clean qubit model with an error probability decreasing polynomially with the number of executions [13]. In the literature, various applications of the one clean qubit model can be found as approximation of Jones polynomials [13], spectral density estimation [14] or integrability testing [15]. Among these applications, estimating the n… view at source ↗
Figure 3
Figure 3. Circuit to implement Uk. m′ controlled-X gates are applied to restore the pure state on the ancillary qubits used in P ′ . The circuit drawn in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 17 canonical work pages

  1. [9]

    Chowdhury, A., Somma, R., & Subas ¸ı, Y . (2021). Computin g partition functions in the one-clean-qubit model. Physical Review A, 103(3)

  2. [11]

    Low, G., & Chuang, I. (2019). Hamiltonian Simulation by Qubitization. Quantum, 3, 163

  3. [1]

    LEV AILLANT, J. M. D. (1998). SYSTEME MULTI-SENSEURS RADAR ET OPTRONIQUE POUR L’A TTAQUE AU SOL E. MIGNOT DGA/SPAe. Multi-Sensor Systems and Data Fusion for Telecom muni- cations, Remote Sensing and Radar

  4. [2]

    A VIA TION, D. (2000). MIRAGE 2000 COMBA T AIRCRAFT UP- GRADE IN DASSAULT A VIA TION. Advances in V ehicle Systems Concepts and Integration

  5. [3]

    Laby, Romain & Roueff, Franc ¸ois & Gramfort, Alexandre. (2016). Anomaly Detection and Localisation using Mixed Graphical M odels. ICML 2016 Anomaly Detection Workshop, Jun 2016, New Y ork, Un ited States

  6. [4]

    Laby, Romain & Gramfort, Alexandre & Roueff, Franc ¸ois & En- derli, Cyrille & Alain, Larroque. (2015). Sparse pairwise M arkov model learning for anomaly detection in heterogeneous data . https://api.semanticscholar.org/CorpusID:55358111

  7. [5]

    Clifford, P . (1990). Markov random fields in statistics. Disorder in physical systems: A volume in honour of John M. Hammersley, 1 9-32

  8. [6]

    Sohl-Dickstein, J., & Culpepper, B. J. (2012). Hamilton ian annealed importance sampling for partition function estimation. ar Xiv preprint arXiv:1205.1925

Show all 21 references
  1. [7]

    (2016, June)

    Risteski, A. (2016, June). How to calculate partition fu nctions using con- vex programming hierarchies: provable bounds for variatio nal methods. In Conference on Learning Theory (pp. 1402-1416). PMLR

  2. [8]

    L., Siavoshani, M

    Chan, C. L., Siavoshani, M. J., Jaggi, S., Kashyap, N., & V ontobel, P . O. (2015, June). Generalized belief propagation for estimati ng the partition function of the 2d Ising model. In 2015 IEEE International Sy mposium on Information Theory (ISIT) (pp. 2261-2265). IEEE

  3. [10]

    C., & Handscomb, D

    Mason, J. C., & Handscomb, D. C. (2002). Chebyshev polyn omials. Chapman and Hall/CRC

  4. [12]

    Knill, E., & Laflamme, R. (1998). Power of one bit of quant um information. Physical Review Letters, 81(25), 5672

  5. [13]

    W., & Jordan, S

    Shor, P . W., & Jordan, S. P . (2007). Estimating Jones pol ynomials is a complete problem for one clean qubit. arXiv preprint arXiv: 0707.2831

  6. [14]

    M.V andersypen, M

    L. M.V andersypen, M. Steffen, G. Breyta, C. S. Y annoni, M. H. Sherwood, and I. L. Chuang, Experimental realization of Sho r’s quantum factoring algorithm using nuclear magnetic resonance. Nat ure 414, 883 (2001)

  7. [15]

    Poulin, R

    D. Poulin, R. Blume-Kohout, R. Laflamme, and H. Ollivier , Exponential speedup with a single bit of quantum information: measuring the average fidelity decay. Phys. Rev. Lett. 92, 177906 (2004)

  8. [16]

    Jozsa, R. (1999). Searching in Grover’s algorithm. arX iv preprint quant-ph/9901021

  9. [17]

    M., & Wiebe, N

    Childs, A. M., & Wiebe, N. (2012). Hamiltonian simulati on using linear combinations of unitary operations. arXiv preprint arXiv: 1202.5822

  10. [18]

    Cross, A. (2018). The IBM Q experience and QISKit open-s ource quantum computing software. In APS March meeting abstracts (V ol. 2018, pp. L58-003)

  11. [19]

    Preskill, J. (2018). Quantum computing in the NISQ era a nd beyond. Quantum, 2, 79

  12. [20]

    Y ., Li, J., Y u, B., & Guo, G

    Xiang, G. Y ., Li, J., Y u, B., & Guo, G. C. (2005). Remote pr eparation of mixed states via noisy entanglement. Physical Review A, 72( 1), 012315

  13. [21]

    Jones, J. A. (2001). NMR quantum computation. Progress in Nuclear Magnetic Resonance Spectroscopy, 38(4), 325-360

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.