{"id":"6e778fe9-1bb2-4c86-8ca5-673f12feebbc","arxiv_id":"2411.17816","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Partition functions can be estimated from the success probability of a block-encoded imaginary-time propagator, with sample complexity O(2^n e^β/(Z_β ε_r²)).","lead":"This paper presents a quantum algorithm that estimates a system's partition function by repeatedly flipping a 'quantum coin': a post-selected circuit block-encoding e^{-βH/2}. The method needs no phase estimation or amplitude amplification, and the required number of runs scales with N/Z_β, quadratically better than earlier no-subroutine approaches.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (A4) assumes the approximate block-encoding is diagonal in H's eigenbasis, which Eq. (1) does not guarantee; a trace-norm argument repairs the bound, so the central sample-complexity claim survives after a proof fix.","rationale":"The reader's weakest assumption correctly identifies the invalid eigenvalue-wise step in Eq. (A4). This is the most load-bearing concern because it directly supports the bias control in Theorems 1 and 3, which in turn fixes the parameter ε' and hence the QSP circuit cost. However, the concern does not overturn the central claim: a simple trace-norm argument, using only the spectral-norm closeness from Eq. (1) and the fact that block-encodings have norm at most 1, gives |p̃_suc − p_suc| ≤ 2ε'. This is the same order as the paper's 3ε', so the algorithm's sample complexity O(2^n e^β/(Z_β ε_r²)) and the relative-error guarantee remain valid after replacing the erroneous line with the correct argument. The paper also discusses a QSP implementation where f̃[H] is a polynomial in H and hence diagonal in the eigenbasis, but the theorem is stated for generic block-encodings, so the proof must be fixed. Other concerns, such as the reliance on an external iterative scheme for Algorithm 1 and the heuristic noise model in the experiment, are secondary and do not threaten the theoretical contribution. Therefore the reader's CONDITIONAL verdict is appropriate: the paper is publishable after a minor proof revision. My agreement with the reader is full on the weakest assumption, and I recommend no change to the verdict.","tokens_in":17297,"tokens_out":8319,"duration_ms":72391,"concrete_test":"Replace the derivation in Eq. (A4) with the trace-norm argument: define A = α f̃[H], B = α e^{−βH/2}, ρ = I/2^n. Show |p̃_suc − p_suc| = |Tr[ρ(A†A − B†B)]| ≤ ||A†A − B†B|| ≤ (||A||+||B||)||A−B|| ≤ 2ε'. Then verify that choosing ε' = ε_r/(4 e^β 2^n) keeps the bias below ε_r/2 and that the sample complexity S = 8 z_δ²/ε_r² · 2^n e^β/Z_β still satisfies the theorem. If the bound holds, Theorem 1 stands with a corrected constant; if a counterexample with |p̃_suc − p_suc| ≫ ε' is found, the central claim fails. The Hölder argument shows the former, so the test confirms the fix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 in Appendix A bounds the bias |p̃_suc − p_suc| by writing (e^{−β/2} f̃_β(λ))² as if f̃_β[H] were diagonal in the eigenbasis of H, with eigenvalue-wise error ε'. However, Eq. (1) only guarantees ||α f̃ − α f|| ≤ ε' in spectral norm for the full matrices; it does not imply that the top-left block of the block-encoding unitary is a function of H, nor that it commutes with H. A generic V_f can produce off-diagonal components in the eigenbasis of H, so the third line of Eq. (A4) is not justified from the stated assumption. This is load-bearing because the theorem's relative-error guarantee and the resulting ε' choice (ε' = ε_r/(6 e^β 2^n)) depend on this bound. The concern is repairable: a standard trace-norm/Hölder argument gives |p̃_suc − p_suc| = |(1/N)Tr[A†A − B†B]| ≤ ||A†A − B†B|| ≤ (||A||+||B||)||A−B|| ≤ 2ε', where A = α f̃, B = α f, N = 2^n, using ||A||,||B|| ≤ 1. This yields the same order of bias, so the sample complexity and ε' scaling remain valid with only a constant adjustment. The paper's use of the invalid eigenvalue-wise step is a genuine proof gap, not a fatal flaw in the algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces a quantum algorithm for estimating the partition function Z_β = Tr(e^{-βH}) of a bounded-spectrum Hamiltonian H up to relative error, using a \"quantum coin toss.\" The coin is the outcome of a post-selected block-encoding of the imaginary-time propagator e^{-βH/2} applied to the maximally mixed state. The authors propose two estimators: the success-probability (Bernoulli) and the waiting-time (geometric) processes, and prove sample-complexity bounds O(2^n e^β/(Z_β ε_r^2)) for both, claiming a quadratic improvement in 2^n e^β/Z_β over previous no-QPE/no-QAE algorithms. They also provide a QSP implementation cost, a fragmented cooling-schedule variant, and a 9-qubit proof-of-concept experiment on IonQ Aria-1 with variational block-encodings and a simple depolarizing-noise error-mitigation scheme.","tokens_in":17581,"tokens_out":27676,"duration_ms":226795,"significance":"If the results hold, the algorithm is a simple and resource-light approach to partition function estimation, avoiding QPE and QAE, and is well suited to early fault-tolerant hardware. The Bernoulli/geometric analysis is elegant and the practical demonstration with error mitigation is valuable. The central sample-complexity claim is interesting and the comparison with prior work is transparent. However, the proof of Theorem 1 in Appendix A contains a gap that must be repaired; the underlying claim appears correct and the gap is fixable. Overall, this is a worthwhile contribution that requires revision.","major_comments":[{"comment":"The bound on |p̃_suc − p_suc| is derived by expanding the trace difference as a sum over eigenvalues of H with a per-eigenvalue error ε'. This step is not justified by the block-encoding condition Eq. (1), which only ensures ||α f̃ − α f|| ≤ ε' in spectral norm for the full operators and does not imply that f̃[H] is diagonal in the eigenbasis of H. The eigenvalue-wise expansion is therefore not a consequence of the stated assumptions. This is load-bearing because Theorem 1's relative-error guarantee and the choice ε' = Z_β/(6 e^β 2^n) ε_r rely on this bound. The claim itself is correct: a trace-norm argument using A = e^{-β/2} f̃ and B = e^{-β/2} f gives |p̃_suc − p_suc| ≤ (1/N)|Tr(A†A − B†B)| ≤ ||A†A − B†B|| ≤ (||A||+||B||)||A−B|| ≤ 3ε', so the theorem remains valid after a corrected proof. The authors should replace the invalid step with such an argument.","section":"Appendix A, Eq. (A4)"}],"minor_comments":[{"comment":"The cooling schedule is defined with β_l = β/2, but the subsequent identity p(Δ_1)...p(Δ_l) = Z_β/(e^β 2^n) is only consistent with β_l = β. Please correct this inconsistency.","section":"Sec. V B"},{"comment":"The proof of Theorem 1 uses the Agresti-Coull interval, whose coverage is approximate for finite S. For a formal theorem with confidence 1−δ, the proof should either state the asymptotic nature of the confidence or use a rigorous concentration inequality (e.g., Hoeffding or Chernoff), which would yield the same scaling with slightly changed constants.","section":"Appendix A 1, Theorem 1"},{"comment":"The phrase \"runtime scaling as O(N/Z_β)\" in the abstract refers to the number of coin tosses; the actual runtime also includes the QSP circuit depth O(√β(β+n+log(1/ε_r))) per toss. Please state this distinction explicitly.","section":"Abstract / Sec. III"},{"comment":"The equation contains typographical errors (e.g., \"e−βe−βλ\" and malformed exponents) that should be corrected.","section":"Eq. (A4)"},{"comment":"The variational block-encoding error is reported only as ε' < 10^-2. Reporting the actual trained ε' values per Hamiltonian instance and inverse temperature would allow readers to verify the bias bound used in the main theorems.","section":"Sec. V C"},{"comment":"The depolarizing-noise strength ξ is fitted with a relative uncertainty over 75%; the paper should note that the agreement in Fig. 3 is qualitative given these uncertainties.","section":"Sec. IV / Fig. 3"}],"recommendation":"major_revision","confidential_remarks":"The main technical issue is the proof gap in Appendix A, which is repairable via a trace-norm argument as described in the report. The experimental section is heuristic but acceptable as a proof-of-concept. The paper's central claim is likely correct, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core trick is simple: with ρ = I/2^n, the success probability of postselecting a block-encoding of e^{-βH/2} is p_suc = Zβ/(2^n e^β). The paper's real contribution is treating the postselection outcomes as a Bernoulli process and proving sample complexity O(2^n e^β/(Zβ ε_r^2)) for relative-error estimation, quadratically better in 2^n e^β/Zβ than the previous no-QPE/no-QAE algorithms [25,27]. That is a genuine improvement, and the analysis in Theorems 1 and 3 is correct under the ideal-error assumption. The second variant, estimating the mean number of trials to success, is a nice touch because it avoids knowing Zβ a priori, at the cost of a 1/δ dependence instead of log(1/δ).\n\nWhat it does well: the comparison table is honest, the paper correctly identifies that the identity is elementary and focuses on the estimator analysis, and the QSP cost scaling is stated. The fragmented cooling schedule discussion is thoughtful, noting the open problem of determining a schedule in practice.\n\nThe soft spot is real but not fatal. The proof of Theorem 1's bias bound in Eq. (A4) assumes the approximate block-encoding f̃β[H] is diagonal in H's eigenbasis with per-eigenvalue error ε'. Equation (1) only gives spectral-norm closeness of the full matrix, which does not imply commutativity with H. This is a genuine proof gap, but it is repairable: a trace-norm/Hölder argument gives |p̃_suc − p_suc| ≤ 3ε' without needing f̃ to be a function of H, as your stress-test note shows. The central sample-complexity claim survives with a corrected proof, and the paper should add that argument.\n\nOther concerns are minor. Algorithm 1's bias choice requires knowing Zβ; the paper acknowledges this and points to the iterative scheme of [25], but the tight bound is not usable in a single shot. The experimental section is a proof-of-concept on 9 qubits with a variational block-encoding rather than QSP, and it ships no code or data. The single-parameter depolarizing noise model is fitted to one baseline circuit and then applied to all circuits; it works for the few points shown, but this is not systematic validation. I would treat the experiment as a demonstration of the error-mitigation heuristic, not as evidence for the algorithm's scaling.\n\nThe citation pattern looks fine; the baseline [27] includes one of the authors, but it is the direct predecessor and the comparison is explicit.\n\nBottom line: the theoretical result is sound after a proof fix. This paper is for researchers working on partition function estimation, thermal state preparation, and early fault-tolerant algorithms. It deserves a serious referee; I would send it to review with a request to fix the bias proof, ideally by adding the trace-norm argument. I would cite it if I were working on quantum PFE.","headline":"A clean Bernoulli-process sample-complexity analysis for partition function estimation via postselected block-encoding of e^{-βH/2}, with a repairable proof gap in the bias bound and a modest proof-of-concept experiment.","tokens_in":18196,"tokens_out":2230,"would_cite":true,"duration_ms":19056,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A quantum coin from post-selected $e^{-\\beta H/2}$ estimates the partition function with $O(2^n e^{\\beta}/(Z_{\\beta} \\varepsilon_r^2))$ tosses.","keywords":["partition function","quantum algorithm","block-encoding","post-selection","Bernoulli process","imaginary-time evolution","sample complexity","error mitigation"],"falsifier":"For a two-qubit Hamiltonian with known eigenbasis, construct an approximate block-encoding whose error matrix is purely off-diagonal in that basis and has spectral norm $\\varepsilon'$; then measure the success probability and compare the deviation from the ideal $p_{\\mathrm{suc}}$ to the claimed bound $|\\tilde{p}_{\\mathrm{suc}}-p_{\\mathrm{suc}}| \\le 3\\varepsilon'$. Exceeding that bound would disprove the per-eigenvalue bias analysis.","tokens_in":1551,"feed_emoji":"🪙","tokens_out":11414,"duration_ms":213819,"temperature":0.7,"pith_summary":"This paper shows that the partition function of a generic Hamiltonian can be estimated by flipping a quantum coin: the coin is defined by the probability of successfully post-selecting a block-encoding of the imaginary-time propagator $e^{-\\beta H/2}$ applied to the maximally mixed state. Because that success probability is proportional to $Z_{\\beta}$, the problem reduces to estimating the bias of a Bernoulli coin, which requires only $O(2^n e^{\\beta}/(Z_{\\beta} \\varepsilon_r^2))$ tosses for a given relative error $\\varepsilon_r$. This is quadratically better in $2^n e^{\\beta}/Z_{\\beta}$ than previous general-purpose algorithms that also avoid quantum phase estimation and amplitude amplification. The method is simple enough to run on current hardware; the authors demonstrate it on a 9-qubit processor and use a simple global-depolarizing noise model to recover exact results.","feed_headline":"Quantum coin toss cuts partition-function sample cost quadratically","feed_subtitle":"The algorithm needs quadratically fewer samples than previous methods that also avoid phase estimation.","key_machinery":"The central object is the quantum coin: a unitary $V_f$ that block-encodes a Hamiltonian function $f[H]$ on a system register and an ancillary register, where measuring the ancillas in the computational basis yields heads if all ancillas are in $|0^a\\rangle$. The heads probability is $p_{\\mathrm{suc}} = \\alpha^2 \\mathrm{Tr}[\\tilde{f}[H]\\rho\\tilde{f}[H]^\\dagger]$, with $\\alpha$ the subnormalization and $\\tilde{f}[H]$ the approximate function. For partition-function estimation one takes $\\rho$ to be the maximally mixed state and $f[H]=e^{-\\beta H/2}$ with $\\alpha=e^{-\\beta/2}$, so that $p_{\\mathrm{suc}} = Z_{\\beta}/(e^{\\beta} 2^n)$. This identity turns the hard problem of estimating a sum over an exponential number of energy levels into the simple task of estimating the bias of a Bernoulli coin. The coin is implemented either by quantum signal processing or by a variational circuit, and the Bernoulli-process viewpoint is what allows the use of standard tools for binomial proportions and geometric distributions to obtain the sample-complexity bounds.","core_discovery":"The central claim is that, given a block-encoding of $e^{-\\beta H/2}$ with approximation error $\\varepsilon'$, the partition function $Z_{\\beta} = \\mathrm{Tr}[e^{-\\beta H}]$ can be estimated to relative error $\\varepsilon_r$ and confidence $1-\\delta$ by treating the post-selection as a Bernoulli coin. Setting $\\rho = 1/2^n$ and $f[H]=e^{-\\beta H/2}$ gives $Z_{\\beta} = e^{\\beta} 2^n p_{\\mathrm{suc}}$, where $p_{\\mathrm{suc}}$ is the heads probability. Two statistical estimators are proved: one based on the empirical heads fraction (Theorem 1), with sample complexity $O(z_\\delta^2 2^n e^{\\beta}/(Z_{\\beta} \\varepsilon_r^2))$, and one based on the number of trials until success (Theorem 3), with average sample complexity $O(2^n e^{\\beta}/(\\delta \\varepsilon_r^2 Z_{\\beta}))$. Both scalings are quadratic improvements over the $O((2^n e^{\\beta}/Z_{\\beta})^2)$ sample complexity of prior Hamiltonian-agnostic algorithms that also do not use QPE or QAE. The proof models the coin tosses as a Bernoulli process and uses binomial-confidence-interval and geometric-distribution analysis; the circuit implementation uses quantum signal processing, whose query complexity per toss is $O(\\sqrt{\\beta}(\\beta+n+\\log(1/\\varepsilon_r)))$.","pith_inferences":["A rigorous trace-norm argument would likely repair the bias proof in Appendix A, since the bound $|\\tilde{p}_{\\mathrm{suc}}-p_{\\mathrm{suc}}| \\le 3\\varepsilon'$ can be derived from spectral-norm closeness of the full matrices without assuming per-eigenvalue errors; thus the main conclusion is probably robust to the technical gap in the paper.","The quantum-coin architecture extends beyond partition functions: any normalization constant that can be written as $\\mathrm{Tr}[f[H]\\rho]$ for a known $\\rho$ and a block-encodable $f[H]$ could be sampled in the same way, turning other hard counting problems into single-observable measurements.","The trials-to-success estimator suggests an adaptive protocol that draws coin tosses until a stopping rule is met; since the variance of the geometric distribution is known, one could in principle achieve the same relative error with a data-dependent stopping time that may be smaller in practice.","The noise model used in the experiment assumes a single global depolarizing parameter per layer; testing the same error-mitigation protocol on a device with correlated or non-unital noise would reveal how far the simplicity of the method extends."],"forward_implications":["Relative-error sample complexity for partition-function estimation without QPE/QAE becomes $O(2^n e^{\\beta}/(Z_{\\beta} \\varepsilon_r^2))$ instead of the previous $O((2^n e^{\\beta}/Z_{\\beta})^2 / \\varepsilon_r^2)$ scaling.","Because only a block-encoding of $e^{-\\beta H/2}$ is required, the algorithm inherits the query complexity of the chosen block-encoding method; with QSP, the total query cost per coin toss is polylogarithmic in the approximation error.","The trials-to-success variant yields a relative-precision estimate without any prior knowledge of $Z_{\\beta}$, and its average sample complexity depends on the failure probability only linearly.","The success-probability variant has a milder dependence on confidence (through the normal quantile $z_\\delta$) at the cost of setting the block-encoding error to a value that depends on $Z_{\\beta}$, which requires a separate relative-error conversion procedure.","The method is naturally compatible with error mitigation by zero-noise extrapolation because the partition function is a single observable expectation; in the 9-qubit proof-of-concept experiment, a simple global-depolarizing noise model suffices to bring the estimates into agreement with exact calculations."],"supporting_citations":[{"why":"Supplies the one-clean-qubit algorithm and the $O(N^2/Z^2)$ baseline that this paper aims to improve, as well as the iterative additive-to-relative conversion method.","marker":"[25]"},{"why":"Provides the randomized semi-quantum baseline with the same quadratic scaling and the Jacobi-Anger approximation used for the QSP cost analysis.","marker":"[27]"},{"why":"Gives a binomial confidence interval robust for small probabilities, used to convert the success-probability estimate into a relative-error bound.","marker":"[43]"},{"why":"Introduces qubitization and quantum signal processing for implementing functions of a Hamiltonian via block-encoding, which underlies the coin circuit.","marker":"[36]"},{"why":"Generalizes to quantum singular value transformation, providing the polynomial approximation error bounds that set the QSP degree.","marker":"[37]"}],"fun_headline_variants":["Coin toss squares sample efficiency for partition functions","Quantum coin flip delivers quadratic win for partition estimation","Partition function estimates get a quadratic boost from coin toss","Simple quantum coin toss makes partition estimates quadratically faster"],"cache_read_input_tokens":20096,"weakest_assumption_plain":"The proof that the approximate circuit only changes the success probability by a small amount assumes that the approximation error can be assigned per energy level, but the circuit guarantee is only that the whole matrix is close in the usual matrix sense, so the per-energy-level picture is an extra assumption that the paper does not derive.","fun_headline_variants_meta":{"raw":{"variants":["Coin toss squares sample efficiency for partition functions","Quantum coin flip delivers quadratic win for partition estimation","Partition function estimates get a quadratic boost from coin toss","Simple quantum coin toss makes partition estimates quadratically faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000305,"raw_usage":{"total_tokens":1829,"prompt_tokens":1102,"completion_tokens":727,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":718,"completion_tokens_details":{"reasoning_tokens":665}},"tokens_in":718,"tokens_out":727,"duration_ms":11279,"temperature":1.0,"reasoning_tokens":665,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:50:19.510011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a two-qubit Hamiltonian with known eigenbasis, construct an approximate block-encoding whose error matrix is purely off-diagonal in that basis and has spectral norm $\\varepsilon'$; then measure the success probability and compare the deviation from the ideal $p_{\\mathrm{suc}}$ to the claimed bound $|\\tilde{p}_{\\mathrm{suc}}-p_{\\mathrm{suc}}| \\le 3\\varepsilon'$. Exceeding that bound would disprove the per-eigenvalue bias analysis.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the one-clean-qubit algorithm and the $O(N^2/Z^2)$ baseline that this paper aims to improve, as well as the iterative additive-to-relative conversion method."},{"cited_title":"heads” if 4 the measurement returns only zeros and “tails","cited_arxiv_id":null,"evidence_quote":"Provides the randomized semi-quantum baseline with the same quadratic scaling and the Jacobi-Anger approximation used for the QSP cost analysis."},{"cited_title":"Tosta, T","cited_arxiv_id":null,"evidence_quote":"Introduces qubitization and quantum signal processing for implementing functions of a Hamiltonian via block-encoding, which underlies the coin circuit."}],"review_version":1}