{"id":"e267f8f0-d453-4be3-8c92-6ebf5f659bd0","arxiv_id":"1908.05251","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A DQC1-based algorithm estimates α-Rényi entropies of non-singular quantum states to additive or multiplicative precision using purified access, at expected cost O(1/(xε)^2) measurements.","lead":"This paper designs a quantum algorithm that estimates the Rényi entropy of an unknown quantum state when given access to a circuit that prepares the state. It trades deep circuits for many simple measurements, which the authors argue makes it easier to run on near-term noisy quantum hardware.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Normalized-trace denominator in DQC1 is 2^{a+2s+2}=4·2^a d^2, not d; Theorem 1's O(1/(xε)^2) measurement bound is missing a d-dependent factor.","rationale":"The central claim of the paper is the measurement complexity in Theorem 1. All other results (Theorem 2, comparisons in Table I, and the purported advantage over sample-complexity models) depend on it. The proof's Section IV.B says the normalized trace from DQC1 is only a constant rescaling away from x. That statement is false: the denominator is the dimension of Uα, which is quadratic in d and linear in the purification ancilla dimension. I checked both estimation routes described in the paper. The postselection route (mentioned in §III C and §IV B) has acceptance probability d/N, yielding a factor A d in the number of runs. The phase-trick route yields (A d)^2. In neither case is the factor independent of d. The reader's weakest_assumption identified the same issue; however, I believe it is more severe than 'addressable in a revision.' The theorem as stated is false, not merely missing an analysis. The only way to restore the theorem would be to either (a) find a block encoding of ρ^α on O(d) dimensions (not provided) or (b) change the complexity to O((2^a d/(xε))^2), which forfeits the claimed improvement over [19]. The Appendix B stopping-time inequality has a typo ('x_r > x' should be 'x_r < x'), but the probability bound still holds for ε_rel<2, so it is not a substantive concern. I therefore recommend REJECT, though the algorithmic idea of combining QSVT with DQC1 may be salvageable with a corrected analysis.","tokens_in":16954,"tokens_out":22205,"duration_ms":214909,"concrete_test":"Re-derive the measurement count from the dimensions of Lemma 4 and Lemma 6. Let A=2^a be the purification ancilla dimension and d=2^s. Lemma 4 yields a block encoding of ρ on a+2s qubits; Lemma 6 yields Uα on a+2s+2 qubits, so N=4A d^2. The ρ^α block contributes d x/N = x/(4A d) to the normalized trace. For the postselection variant, the acceptance probability is d/N, so M=O(A d/(γ^2 x^2)); for the V-trick variant, M=O((N/(d γ x))^2)=O(A^2 d^2/(γ^2 x^2)). Since a full-rank purification requires A≥d, both bounds are Ω(d^2/(γ^2 x^2)) or worse. Check whether the claimed O(1/(xε)^2) appears anywhere in this calculation.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 1's measurement complexity rests on estimating x=Tr(ρ^α)/d via DQC1. The unitary Uα is built by Lemma 4 then Lemma 6. Lemma 4's block encoding of ρ from a purification Uρ on a+s qubits acts on a+2s qubits: it contains an extra s-qubit system register. Lemma 6 adds two ancillas. Hence Uα acts on n=a+2s+2 qubits, N=2^n=4·2^a d^2. DQC1 outputs the normalized trace Re(Tr(Uα))/N. The desired ρ^α submatrix contributes Tr(ρ^α)/N = x/(4·2^a d). The paper's claim that a multiplicative approximation is unaffected by constant rescaling (Section IV.B) treats this factor as a constant; it is not. Even with ideal postselection onto the ρ^α block, the acceptance probability is d/N=1/(4·2^a d), so M=O(2^a d/(γ^2 x^2)) runs are needed for relative error γ. For a full-rank purification, the ancilla dimension is at least d, so 2^a≥d and M=Ω(d^2/(γ^2 x^2)). The V-trick alternative (§IV.B) requires M=O((2^a d/(γ x))^2)=Ω(d^4/(γ^2 x^2)). Either way the stated O(1/(xε)^2) is understated by at least d^2. This invalidates the advertised improvement over the Θ(d^2/ε^2) sample complexity of [19].","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a quantum algorithm for estimating the α-Rényi entropy of an unknown d-dimensional density matrix in the purified quantum query access model. The method combines block encodings of ρ^α obtained via quantum singular value transformations with DQC1 normalized-trace estimation, and uses an iterative procedure of Chowdhury et al. to convert additive trace estimates into multiplicative ones. The central claim, Theorem 1, is that for α>0, α≠1, an additive ε-approximation to S_α(ρ) can be obtained with high probability using an expected O(1/(xε)^2) independent applications of a circuit that queries the purification oracle U_ρ and U_ρ^† O((1/δ)log(d/ε)) times, with a single qubit measurement per run, where x=(1/d)Tr(ρ^α). Theorem 2 extends this to multiplicative precision with an additional logarithmic-in-d overhead. The paper compares this favorably with the Θ(d^2/ε^2) sample complexity of copy-based estimation.","tokens_in":17291,"tokens_out":11910,"duration_ms":124772,"significance":"If the central complexity bound were correct, the paper would make a useful conceptual contribution: it would show that in a purified-oracle model, Rényi entropies can be estimated using shallow circuits and many single-qubit measurements, without the long coherent control required by quantum amplitude estimation. The combination of QSVT block encodings with DQC1 trace estimation is natural and not, to my knowledge, previously explored, and the use of the iterative expected-runtime analysis of Chowdhury et al. is a genuine attempt to go beyond worst-case bounds. The paper is also honest about its limitations, noting that the decision version of entropy estimation is not placed in DQC1. However, the main theorem's measurement bound is not supported: the DQC1 normalized trace of the constructed block-encoding unitary is scaled by a d-dependent factor that the manuscript treats as constant. This invalidates the advertised comparison with Θ(d^2/ε^2) and, as stated, the algorithm does not achieve the claimed improvement.","major_comments":[{"comment":"The central complexity claim is not supported because the DQC1 measurement does not estimate x=(1/d)Tr(ρ^α) up to a d-independent constant factor. By Lemma 4, the block encoding of ρ acts on a+2s qubits, where s=log d and a is the purification ancilla size; after Lemma 6, the unitary U_α acts on n=a+2s+2 qubits, so DQC1 returns Tr(U_α)/2^n with 2^n=4·2^a d^2. The ρ^α block contributes Tr(ρ^α)/2^n = x/(4·2^a d) to this normalized trace. The sentence in Section IV.B that a multiplicative approximation is unaffected when the estimate is scaled by a constant treats 4·2^a d as a constant, but this factor depends on d and on a; since δI ≼ ρ implies ρ is full rank, any purification requires 2^a ≥ d. Therefore the number of DQC1 runs needed to estimate x to relative error γ is O((2^a d/(γ x))^2) = Ω(d^4/(γ^2 x^2)), not O(1/(γ x)^2). This invalidates Theorem 1 as stated, and Theorem 2 and Equation (13) inherit the same missing factor.","section":"Section IV.B and Theorem 1"},{"comment":"The subtraction trick with the controlled-phase unitary V does not repair the normalization problem. Both Re(Tr(U_α)) and Re(Tr(U_α′)) are normalized by the same denominator 2^n, so the difference estimates the normalized block contribution Tr(ρ^α)/2^n, not Tr(ρ^α). The statement that an estimate of (1/d)Tr(ρ^α) to multiplicative precision is also a valid estimate of Tr(ρ^α) to the same precision conflates the normalized and unnormalized traces and ignores the dimension-dependent factor 2^n/d.","section":"Section IV.B"},{"comment":"The stopping-time analysis contains a reversed inequality. With q defined by x_max/2^{q−1} > x > x_max/2^q, for r ≥ q+1 one has x_r = x_max/2^r < x, whereas the text states that r ≥ q+1 implies x_r > x. Consequently the claimed bound Pr(˜x_r < x_r) ≤ 1−c′ does not follow from the stated premise. In addition, the comment in Algorithm B.1 that AdditiveEstimate returns ˜x_r with Pr(|x_r−˜x_r| < ε_r) > c′ is incorrect as written, since the subroutine estimates the unknown quantity x, not the known threshold x_r. The expected-measurement formula (B4) may be salvageable with a corrected argument, but the proof given in the manuscript is not valid as it stands.","section":"Appendix B"},{"comment":"The parenthetical proposal for α<1, which claims that scaling up the block encoding of ρ^α by d using pre-amplification makes 'the normalized trace larger than unity,' is not correct: a normalized trace of a unitary cannot exceed unity, and Lemma 7 amplifies eigenvalues only while they remain below 1, so it cannot be used to multiply the block by d when the resulting operator norm exceeds 1. As written, this passage does not provide a valid alternative complexity bound.","section":"Section IV.C"}],"minor_comments":[{"comment":"The notation C^{d+a} for the input unitary is ambiguous: it is not clear whether a is an ancilla dimension or a number of ancilla qubits, and the total dimension of the block-encoding unitary U_α is never stated explicitly. The construction in Lemma 4 implies U_α acts on 2^{a+2s+2} dimensions, which should be stated in the theorem.","section":"Theorem 1"},{"comment":"The phrase 'normalised trace of this d+a-dimensional unitary U_α' is inconsistent with the block-encoding construction, which acts on a+2s+2 qubits; the dimension should be written as 2^{a+2s+2}.","section":"Section IV.B"},{"comment":"The comment inside Algorithm B.1 defining the additive estimate should read Pr(|x−˜x_r| < ε_r) > c′, not Pr(|x_r−˜x_r| < ε_r) > c′; as printed, the condition refers to the known quantity x_r and is not meaningful.","section":"Algorithm B.1"},{"comment":"The column 'E[#mmts]' in Table I omits the dimension-dependent normalization factor identified in the major comments; if the corrected bound is used, the comparison with the sample-complexity results of [19] must be revisited.","section":"Table I"},{"comment":"The sentence about the α<1 case and pre-amplification should be rewritten or removed, since it appears to claim that a normalized trace can exceed unity and is not supported by the cited lemma.","section":"Section IV.C"}],"recommendation":"reject","confidential_remarks":"The normalization error in Section IV.B is, in my reading, fatal to the main theorem as stated. The corrected measurement count is Ω(d^4/(γ^2 x^2)) rather than O(1/(γ x)^2), which destroys the advertised improvement over the Θ(d^2/ε^2) sample complexity. This is not a local fix: recovering the claimed bound would require a fundamentally different block-encoding construction with unitary dimension O(d), which is not provided. The Appendix B proof issues are secondary but would also need correction in any revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. The good news: the paper has a genuinely new idea—combining QSVT block encodings with DQC1 trace estimation to estimate α-Rényi entropies in the purified query access model, including a multiplicative-precision iteration. That combination hasn't been done before, and the presentation is clear. The bad news: the central complexity theorem is wrong as stated because the DQC1 normalization factor is not a constant.\n\nIn Section IV.B they argue that since they want a multiplicative approximation, the fact that DQC1 gives a normalized trace 'does not pose any issue' because scaling by a constant doesn't affect multiplicative factors. But the normalization is 1/N, where N is the dimension of the full block-encoding unitary Uα. Using Lemma 4 and Lemma 6, Uα acts on a+2s+2 qubits (s=log d, a purification qubits), so N=4·2^a d^2. The ρα submatrix contributes Tr(ρα)/N = x/(4·2^a d) to the normalized trace. That factor depends on d (and for a full-rank purification, 2^a≥d), so it's not constant. To estimate x to relative error γ you need to estimate a quantity of size x/(4·2^a d) to absolute precision γx/(4·2^a d), which costs O((4·2^a d)^2 / (γx)^2) measurements. Even with a minimal one-qubit purification this is Ω(d^4/(γ^2 x^2))—far from the advertised O(1/(xε)^2). The comparison with the Θ(d^2/ε^2) sample-complexity bound of Acharya et al. does not hold.\n\nThere is a second, smaller issue: in Appendix B the stopping-time analysis states that r≥q+1 implies x_r > x, but from their own Eq. (B3) it's the other way. The failure-probability inequality direction is reversed. Probably fixable, but as written it doesn't hold.\n\nTo be fair, the algorithm might still work if the normalization is handled and the complexity re-derived; the phase-trick to isolate Tr(ρα) is plausible, and the multiplicative iteration is a real contribution. But with Theorem 1 unsupported, the paper is not publishable in its current form. It deserves a serious referee: the idea is worth exploring, and the errors are fixable. I'd send it to review with a request for a corrected normalization analysis and a revised comparison with existing results.","headline":"The main complexity claim overlooks a dimension-dependent DQC1 normalization factor, so the advertised O(1/(xε)^2) bound does not hold; the QSVT+DQC1 idea is still worth a serious referee.","tokens_in":17804,"tokens_out":10855,"would_cite":false,"duration_ms":98864,"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":"A quantum algorithm estimates Rényi entropies of unknown states using one-clean-qubit trace estimation and block encodings, with measurement counts that can beat copy-based sample complexity.","keywords":["Rényi entropy","quantum singular value transformations","block encodings","DQC1 one-clean-qubit model","trace estimation","purified quantum query access","multiplicative approximation","quantum query complexity"],"falsifier":"Construct the full block-encoding unitary from Lemma 4 for a purification with $a$ ancilla qubits and compare the exact normalized trace of its top-left block with $\\mathrm{Tr}(\\rho^\\alpha)/2^{a+2s}$; if the rescaling factor is not constant in $a$, then simulating the paper's prescribed measurement schedule on a state with known spectrum will show the error exceeding $\\epsilon$ at the claimed number of measurements.","tokens_in":16724,"feed_emoji":"⚛️","tokens_out":12335,"duration_ms":109404,"temperature":0.7,"pith_summary":"This paper proposes a quantum algorithm to estimate the $\\alpha$-Rényi entropy $S_\\alpha(\\rho)=\\frac{1}{1-\\alpha}\\log\\mathrm{Tr}(\\rho^\\alpha)$ of an unknown density matrix, under the purified quantum query access model: access is given to a unitary that prepares a purification of $\\rho$. The main claim is that an additive-$\\epsilon$ estimate can be obtained with an expected $O(1/(x\\epsilon)^2)$ independent runs of a circuit that measures a single qubit and invokes the purification oracle $O(\\frac{1}{\\delta}\\log(d/\\epsilon))$ times, where $x=\\frac{1}{d}\\mathrm{Tr}(\\rho^\\alpha)$ and $\\delta$ is a lower bound on the smallest eigenvalue. This is a different resource profile from the $\\Theta(d^2/\\epsilon^2)$ copies needed in the standard independent-copies model, and it avoids amplitude estimation, replacing deep circuits with many shallow measurements. The same iterative routine also yields multiplicative approximations to the entropy with overhead that is at most logarithmic in the dimension.","feed_headline":"Estimate Renyi entropies with one clean qubit","feed_subtitle":"One clean qubit estimates Renyi entropies to additive or multiplicative precision without amplitude estimation.","key_machinery":"The load-bearing mechanism is the combination of block encodings with one-clean-qubit trace estimation. A block encoding is a unitary whose top-left block is a rescaled copy of the matrix of interest; quantum singular value transformations convert the purification oracle into an $\\epsilon$-approximate block encoding $U_\\alpha$ of $\\rho^\\alpha$, with the transformation cost controlled by $\\delta$ and $\\alpha$. The DQC1 circuit then obtains the normalized trace of $U_\\alpha$ by reading the Pauli expectation values of a single clean qubit, and a conditional-phase trick isolates the real trace contribution of the $\\rho^\\alpha$ submatrix. The identity doing the work is $S_\\alpha(\\rho)=\\frac{1}{1-\\alpha}\\log x$ with $x=\\frac{1}{d}\\mathrm{Tr}(\\rho^\\alpha)$: a multiplicative estimate of $x$ becomes an additive estimate of $S_\\alpha$, and the iterative routine of [25] achieves that multiplicative precision with expected cost $O(1/(x\\epsilon)^2)$.","core_discovery":"The central claim is that Rényi entropies can be estimated from a purification oracle using only shallow circuits and many single-qubit measurements. The algorithm first builds a block encoding of $\\rho^\\alpha$ from the purification oracle via quantum singular value transformations, then estimates the normalized trace of that block-encoding unitary in the one-clean-qubit (DQC1) model, and finally feeds the result into an iterative routine that upgrades additive estimates to multiplicative ones. Theorem 1 states that for $\\alpha>0$, $\\alpha\\ne 1$, and $\\delta I \\preceq \\rho \\preceq I$, the procedure outputs $\\tilde S$ with $|\\tilde S-S_\\alpha(\\rho)|\\le \\epsilon$ with high probability, using an expected $O(1/(x\\epsilon)^2)$ single-qubit measurements, each on a circuit that invokes the oracle $m=O(\\frac{1}{\\delta}\\log(d/\\epsilon))$ times; when $\\alpha$ is an integer, $m=\\alpha$ and the circuit depth is independent of $d$. Theorem 2 iterates this to give a multiplicative approximation $(1-\\epsilon_{\\rm rel})S_\\alpha \\le \\hat S \\le (1+\\epsilon_{\\rm rel})S_\\alpha$ in $R=O(\\log(\\log d/\\delta))$ rounds. The paper also notes that when $\\alpha<1$, the block encoding can be pre-amplified by a factor $d$, making any additive estimate effectively multiplicative.","pith_inferences":["A natural extension not stated in the paper is to replace the monomial $\\rho^\\alpha$ with other smooth matrix functions $f(\\rho)$; the same block-encoding-plus-DQC1 pipeline would estimate $\\mathrm{Tr}(f(\\rho))$ whenever quantum singular value transformations can implement a polynomial approximation of $f$.","The advantage over copy-based sample complexity is tied to the purified oracle model; for states provided only as repeated copies, the $\\Theta(d^2/\\epsilon^2)$ sample bound remains the relevant benchmark, so the algorithm's benefit depends on whether the preparation unitary is actually available.","The unanalyzed normalization factor connecting the DQC1 output to $\\mathrm{Tr}(\\rho^\\alpha)$ is a gap that explicit computation could close; if the factor depends on $d$, the claimed measurement count would degrade and the comparison to the sample-complexity model would need revisiting.","A small-scale implementation on a known few-qubit state could map the constant factors in $O(1/(x\\epsilon)^2)$ and clarify when the shallow-circuit/many-measurements tradeoff actually beats amplitude estimation."],"forward_implications":["With purified access, estimating the $\\alpha$-Rényi entropy has measurement cost $O(1/(x\\epsilon)^2)$ instead of the $\\Theta(d^2/\\epsilon^2)$ samples needed in the independent-copies model, so for large $d$ the saving can be substantial when $x$ is not too small.","For integer $\\alpha$, each circuit uses exactly $\\alpha$ oracle calls, so the circuit depth does not grow with the dimension $d$, at the price of a large number of repetitions.","Multiplicative approximations to the entropy are obtained by iterating the additive procedure, with at most $O(\\log(\\log d/\\delta))$ rounds, a regime not previously covered in the quantum algorithm literature.","The scheme needs only one clean qubit while the rest can be maximally mixed, making the resource requirements compatible with near-term NMR or linear-optics experiments rather than full fault-tolerant hardware.","For $\\alpha<1$, pre-amplifying the block encoding by $d$ makes any additive trace estimate effectively multiplicative, bringing the measurement cost down to $O(1/\\epsilon^2)$."],"supporting_citations":[{"why":"Supplies the block-encoding and quantum singular value transformation lemmas used to construct the $\\epsilon$-approximate block encoding of $\\rho^\\alpha$ from the purification oracle.","marker":"[27]"},{"why":"Provides the power-of-block-encoded-matrix results for implementing power functions of Hermitian matrices with controlled oracle calls.","marker":"[26]"},{"why":"Gives the iterative routine that converts additive trace estimates into multiplicative estimates, including the expected-runtime analysis the paper adapts.","marker":"[25]"},{"why":"Introduces the one-clean-qubit model and establishes normalized trace estimation as a DQC1-complete problem, the measurement primitive at the core of the algorithm.","marker":"[28]"},{"why":"Provides the $\\Theta(d^2/\\epsilon^2)$ sample-complexity results for estimating Rényi entropies from independent copies, the benchmark the paper compares against.","marker":"[19]"},{"why":"Defines the purified quantum query access model and gives prior amplitude-estimation-based query complexity bounds that the paper's DQC1 approach avoids.","marker":"[22]"},{"why":"Explains how the DQC1 model can estimate traces of submatrices of a larger unitary, which is needed to isolate the trace of the $\\rho^\\alpha$ submatrix.","marker":"[36]"},{"why":"Shows DQC1 can estimate traces of submatrices whose size is an inverse-polynomial fraction of the whole unitary, supporting the submatrix-trace step.","marker":"[41]"}],"fun_headline_variants":["Estimate Renyi entropies via one-clean-qubit traces","Shallow circuits for Renyi entropy to additive precision","Efficient Renyi entropy estimation with purification oracles","From additive to multiplicative Renyi entropy estimates","Renyi entropy without amplitude estimation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The measurement-count bound assumes that the normalization factor between the one-clean-qubit circuit's estimate and the true value of $\\mathrm{Tr}(\\rho^\\alpha)$ is independent of the dimension $d$; the paper does not analyze how the purification ancilla dimension contributes to that factor, so the stated $O(1/(x\\epsilon)^2)$ count stands only if that factor is truly $d$-independent.","fun_headline_variants_meta":{"raw":{"variants":["Estimate Renyi entropies via one-clean-qubit traces","Shallow circuits for Renyi entropy to additive precision","Efficient Renyi entropy estimation with purification oracles","From additive to multiplicative Renyi entropy estimates","Renyi entropy without amplitude estimation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000656,"raw_usage":{"total_tokens":3081,"prompt_tokens":1101,"completion_tokens":1980,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":717,"completion_tokens_details":{"reasoning_tokens":1905}},"tokens_in":717,"tokens_out":1980,"duration_ms":17133,"temperature":1.0,"reasoning_tokens":1905,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:22:53.639275+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct the full block-encoding unitary from Lemma 4 for a purification with $a$ ancilla qubits and compare the exact normalized trace of its top-left block with $\\mathrm{Tr}(\\rho^\\alpha)/2^{a+2s}$; if the rescaling factor is not constant in $a$, then simulating the paper's prescribed measurement schedule on a state with known spectrum will show the error exceeding $\\epsilon$ at the claimed number of measurements.","supporting_citations":[{"cited_title":"Valiant, Testing symmetric properties of distributions , SIAM Journal on Computing 40, 1927 (2011)","cited_arxiv_id":null,"evidence_quote":"Provides the power-of-block-encoded-matrix results for implementing power functions of Hermitian matrices with controlled oracle calls."},{"cited_title":"Brassard, P","cited_arxiv_id":null,"evidence_quote":"Gives the iterative routine that converts additive trace estimates into multiplicative estimates, including the expected-runtime analysis the paper adapts."},{"cited_title":"Valiant and P","cited_arxiv_id":null,"evidence_quote":"Provides the $\\Theta(d^2/\\epsilon^2)$ sample-complexity results for estimating Rényi entropies from independent copies, the benchmark the paper compares against."},{"cited_title":"Implementing smooth functions of a Hermitian matrix on a quantum computer","cited_arxiv_id":"1806.06885","evidence_quote":"Explains how the DQC1 model can estimate traces of submatrices of a larger unitary, which is needed to isolate the trace of the $\\rho^\\alpha$ submatrix."},{"cited_title":"Fujii, H","cited_arxiv_id":null,"evidence_quote":"Shows DQC1 can estimate traces of submatrices whose size is an inverse-polynomial fraction of the whole unitary, supporting the submatrix-trace step."}],"review_version":1}