{"id":"1e0fb9ac-ef60-4bbd-8dca-18289b4bf88e","arxiv_id":"1908.03903","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.","lead":"This paper presents the first quantum algorithm for estimating the volume of a convex body, reducing the query complexity from roughly n^4 to n^3 for constant precision. It also proves a quantum lower bound that rules out exponential speedup.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.3's truncation parameter H is O(µ_i), but V_i has support up to e^{Θ(n)}; with H=O(µ_i) the quantum Chebyshev estimate can miss a constant fraction of E[V_i], so the claimed O~(n^{2.5}/ε) query bound is not justified as written.","rationale":"The reader's weakest assumption (delta(0) in Section 3.1) is acknowledged in footnote 11 and is fixable by a limit argument or by working with L2 densities; moreover the algorithm is ultimately discretized in Section 5, so that issue is not the main threat. The truncation issue, by contrast, sits at the middle level of the proof: Lemma 4.3 and Lemma 4.4 directly produce the O~(n^{2.5}/ε) mean-estimation cost, and an uncorrected n^3 factor from log^3(H/µ) would remove or reverse the claimed quantum speedup. I am not claiming the theorem is false; a modest modification (H = Θ(µ/ε)) may restore the stated bound. But as written, the proof of Lemma 4.3 does not justify the application of Theorem 2.3, so the manuscript should be accepted only after this step is repaired and the resulting count is verified. The agreement with the reader's verdict is partial at best: we agree the paper is promising but the load-bearing weakness differs.","tokens_in":50070,"tokens_out":49231,"duration_ms":487041,"concrete_test":"Recompute Lemma 4.3 with the truncation threshold set to H = C µ̂_i/ε for a sufficiently large constant C (so the tail E[V_i 1_{V_i>H}] ≤ ε µ_i via E[V_i²]≤8 E[V_i]²), and count the sampler calls required by Theorem 2.3 for this H. If the count is still O~(log(1/δ)/ε_1) up to O(log^3(1/ε)) factors, then the main complexity survives with a corrected proof; if instead the correct H must be the true support bound e^{Θ(n)} (or if the theorem's guarantee fails for H=Θ(µ_i)), the n^{2.5}/ε term in Theorem 1.1 is not established. A concrete instantiation of the failure mode is the two-point distribution X=0 with probability 0.99 and X=100 with probability 0.01 (mean 1, variance 98): BasicEst with H=2 cannot detect the mass at 100 and cannot return a 1±0.1 estimate, showing the current H choice is insufficient for unbounded variables.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 4.3 (Section 4.3.3) invokes the quantum Chebyshev inequality (Theorem 2.3) to estimate µ_i = E_{π_i}[V_i] from copies of |π_{i-1}>. The proof sets H = µ̂_i/(1−c) = Θ(µ_i) and asserts this satisfies the theorem's hypothesis H > µ_U. However, in the pencil construction K' = ([0,2D]×K)∩C, V_i = e^{(a_i−a_{i+1})x0} has support up to e^{Θ(n)}: x0 ≤ 2D = O(√n) and a_i−a_{i+1} = Θ(√n), while µ_i = Z(a_{i+1})/Z(a_i) ≈ (a_i/a_{i+1})^{n+1} = e^{Θ(√n)}. Theorem 2.3's BasicEst truncates outcomes above H (or assumes them absent); with H=Θ(µ_i), the second-moment bound (4.8) only controls the tail contribution by ∫_{H}∞ P(V_i>t) dt ≤ 8µ_i²/H = Θ(µ_i), a constant fraction of the mean. Hence the estimate can fail the required 1±ε relative error. If H is instead taken to be the true support bound e^{Θ(n)}, then the log^3(H/µ_U) factor in Theorem 2.3 is Θ(n^3), which the paper's O-tilde (footnote 1, hiding only poly(log n, log R/r, log 1/ε)) does not absorb; plugging this into Lemma 4.4 changes the per-iteration cost from O~(n^{3/2}/ε_1) to O~(n^{9/2}/ε_1), and the total query complexity no longer matches Theorem 1.1. A correct repair likely takes H = Θ(µ̂_i/ε), making tail contribution ≤ ε µ_i and keeping log^3(H/µ)=O(log^3(1/ε)); but that repair is not what Lemma 4.3 writes. The concern is therefore localized but load-bearing.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a quantum algorithm for estimating the volume of an n-dimensional convex body given by a membership oracle, with query complexity O~(n^3 + n^{2.5}/ε) and arithmetic complexity O~(n^5 + n^{4.5}/ε), improving over the classical O~(n^4 + n^3/ε^2) query bound. The algorithm combines simulated annealing with Chebyshev cooling, a continuous-space quantum hit-and-run walk, nondestructive quantum mean estimation via the quantum Chebyshev inequality, and interlaced rounding of log-concave densities. It also proves an Ω(√n) quantum query lower bound by reduction from search and gives a detailed discretization analysis of the quantum hit-and-run walk with conductance bounds.","tokens_in":50579,"tokens_out":19323,"duration_ms":209224,"significance":"If correct, this is the first quantum speedup for volume estimation, and the framework for quantizing Chebyshev-cooling simulated annealing may be useful beyond this problem. The paper contains an unusually detailed proof infrastructure: spectral analysis of continuous-space walks, error analysis of discretized walks, nondestructive mean estimation, and a lower bound that is optimal in 1/ε up to polylogarithms. The main caveats are the rigor of the continuous-space spectral arguments and a gap in the application of the quantum Chebyshev inequality.","major_comments":[{"comment":"The stress-test concern about Lemma 4.3 lands. The proof sets H = μ̂_i/(1−c) = Θ(μ_i) and asserts that the hypotheses of Theorem 2.3 are satisfied. However, the proof of Theorem 2.3 shows that in the unbounded case BasicEst truncates outcomes at a threshold and the algorithm must search over thresholds b for which b/Δ_U^2 ≈ μ_U; since Δ_U ≈ √8 here, the relevant threshold is Θ(μ_i), not Θ(μ_i). Equivalently, the tail bound E[V_i 1_{V_i>H}] ≤ E[V_i^2]/H ≤ 8μ_i^2/H is only O(μ_i) when H = Θ(μ_i), so truncating at H changes the mean by a constant fraction. The random variable V_i genuinely has support up to e^{Θ(n)} in early annealing steps, so this is not a vacuous concern. As written, Lemma 4.3 does not justify the O~(log(1/δ)/ε) copy bound, and the per-iteration count in Lemma 4.4 and Theorem 1.1 is not established. A repair with H = Θ(μ̂_i/ε) would make the tail contribution at most εμ_i and would keep log^3(H/μ) polylogarithmic, but that repair is not what Lemma 4.3 writes and the subsequent error analysis must be adjusted accordingly.","section":"Section 4.3.3 (Lemma 4.3) with Section 2.3 (Theorem 2.3)"},{"comment":"The continuous-space spectral theory is not fully rigorous as written. Equations (3.11)–(3.17) manipulate ⟨λ|λ⟩ = δ(0) as if it were a finite positive constant, and the footnote defers to an unspecified limit argument. The spectral decomposition obtained in Theorem 3.1 and the construction of |π_W⟩ in Section 3.2 are then used in Lemma 4.8 and Proposition 4.3 to justify the O~(n^{3/2}) phase-gap bound that drives the main query complexity. The paper should either carry out the limiting argument, or define and analyze the walk on a finite grid first and take the continuum limit, or reorganize the proof so that only the discretized walk of Section 5 is used for the algorithmic claims.","section":"Section 3.1 (Lemma 3.1 and Theorem 3.1)"}],"minor_comments":[{"comment":"The condition on line 5, 'if |y|Ham ≥ 1 then Return 0', contradicts the later case 'if |y|Ham = 1' and the surrounding text, which correctly require rejection only when |y|Ham > 1. The displayed pseudocode should be changed to 'if |y|Ham > 1'.","section":"Section 6, Algorithm 6"},{"comment":"The proof refers to 'an approximately uniform sample from K′ = [0, 2D]×K'; the pencil construction K′ is not the cylinder [0,2D]×K. The notation and the sequence of bodies K̂_i should distinguish the cylinder used for the Monte Carlo ratio from the pencil body used for volume estimation.","section":"Section 4.3.1 (Lemma 4.1)"},{"comment":"The displayed bound '√(σ_i^2−μ_i^2)/μ_i ≤ √8' appears to be a typo for '√(σ_i^2+μ_i^2)/μ_i ≤ √8', which is the quantity needed for the hypothesis of Theorem 2.3; as written the minus sign makes the bound trivially true and not what is used later.","section":"Section 4.3.3 (Lemma 4.3)"},{"comment":"Equation (4.44) has a malformed fraction: the right-hand side displays 'Z(2a_{i+1}−a_i)Z(a_i)/Z(a_{i+1})^2' with an extra duplicated integral symbol in the denominator. The intended formula should be checked and rewritten cleanly.","section":"Section 4.3.3 (Lemma 4.6)"},{"comment":"In the first bullet, 'queries to the membership oracle fora the well-rounded convex body' contains a typo ('fora' should be 'for').","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be an important contribution if the local but load-bearing truncation issue in Lemma 4.3 is fixed and the continuous-space spectral arguments are tightened. I see no grounds for concern about novelty or attribution; the gate is purely technical."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: this is the real thing—the first quantum speedup for volume estimation, and the main claims are supported. The paper quantizes Lovász–Vempala's hit-and-run algorithm using a continuous-space quantum walk, a nondestructive quantum Chebyshev mean estimator, and interlaced rounding. The query complexity Õ(n^3 + n^{2.5}/ε) improves on the classical Õ(n^4 + n^3/ε^2) in both n and ε, and the Ω(√n) lower bound via search reduction is clean. The proofs are dense but genuine; the overlap lemma, the error analysis, and the discretized conductance bound in Section 5 are real work. The citation pattern is honest: the classical framework and the quantum MCMC tools are clearly attributed, and the new techniques are separated from the borrowed ones.\n\nSoft spots are minor. Section 3 treats δ(0) as a finite positive number and defers rigor to a limit argument. Since the algorithm is eventually discretized, this is a presentation issue, not a load-bearing flaw. Second, the abstract claims Ω(√n + 1/ε) in the lower bound, but Section 6 as written proves only Ω(√n) for ε < √2−1; the 1/ε component should be proven explicitly or the abstract adjusted. Third, the nondestructive uncompute circuit had a bug in an earlier version (the acknowledgements say so); the current fix using sine-square and median is plausible but deserves a referee's attention. There is also heavy reliance on Hamoudi–Magniez's quantum Chebyshev theorem, and the authors use it as a black box, so a referee should verify the exact preconditions.\n\nThe stress-test note about Lemma 4.3 does not survive a close reading. It argues that H = Θ(µ) makes the tail above H a constant fraction of the mean, so the estimate fails. That conflates the full theorem with its BasicEst subroutine. BasicEst assumes bounded support; the full theorem uses binary search over truncation thresholds and does not require support bounded by H. The condition H > µ is the only requirement, and log³(H/µ) is O(1) when H is a constant multiple of the mean. So the query bound in Lemma 4.3 is justified as written.\n\nThis paper is for quantum algorithm researchers and anyone working on convex geometry. It deserves a serious referee—the central claims are novel, the reductions are careful, and the residual gaps are cosmetic or explicitly flagged. I recommend sending it out with the expectation of minor revisions.","headline":"Solid first quantum speedup for volume estimation; main claims hold up, the Lemma 4.3 truncation worry misfires, and the paper deserves peer review.","tokens_in":51084,"tokens_out":13290,"would_cite":true,"duration_ms":133063,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q17","68W20","52A38"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"This paper presents a quantum algorithm that estimates the volume of a convex body within multiplicative error, achieving the first quantum speedup for volume estimation and proving no exponential speedup is possible.","keywords":["volume estimation","convex bodies","quantum query complexity","quantum walks","simulated annealing","Chebyshev cooling","Markov chain Monte Carlo","membership oracle"],"falsifier":"An independent, fully rigorous Gaussian-limit computation of the discriminant operator $D$ for the hit-and-run transition density on the unit ball would settle the key spectral claim: if the phase gap is not $\\tilde{\\Omega}(n^{-3/2})$, then Lemma 4.8 and the $\\tilde{O}(n^{1.5})$ query count per annealing step fail. Equivalently, simulating the discretized walk at grid spacing $\\epsilon=1/n$ and checking whether the conductance bound (5.5) holds would test the implementation theorem directly.","tokens_in":49914,"feed_emoji":"🧊","tokens_out":8702,"duration_ms":82867,"temperature":0.7,"pith_summary":"The paper tries to establish that quantum computers estimate the volume of an $n$-dimensional convex body faster than classical computers: for multiplicative error $\\epsilon$, its algorithm uses $\\tilde{O}(n^3+n^{2.5}/\\epsilon)$ membership queries, against the classical $\\tilde{O}(n^4+n^3/\\epsilon^2)$. A sympathetic reading takes this as the first quantum speedup for volume estimation, a problem in convex geometry that acts as a continuous analogue of counting. The speedup comes from quantizing the hit-and-run walk as a continuous-space quantum walk, moving between simulated-annealing temperatures with fixed-point amplitude amplification, and estimating each ratio of the telescoping product with a nondestructive quantum mean estimator under Chebyshev cooling. The paper also proves an $\\Omega(\\sqrt{n})$ quantum query lower bound for constant precision and gives a discretized implementation with bounded error, so the result is meant to be more than a query-counting abstraction.","feed_headline":"First quantum speedup for convex-body volume estimation","feed_subtitle":"A quantum hit-and-run walk cuts membership queries from O~(n^4) to O~(n^3) at constant precision.","key_machinery":"The load-bearing object is the continuous-space discrete-time quantum walk, a generalization of Szegedy's quantum walk to state spaces with transition densities. For a reversible chain with density $p_{x\\to y}$, the walk operator is $W=S(2\\Pi-I)$ built from states $|\\varphi_x\\rangle=|x\\rangle\\int_\\Omega \\sqrt{p_{x\\to y}}|y\\rangle\\,dy$, and its eigenvalues are $\\lambda\\pm i\\sqrt{1-\\lambda^2}$ for eigenvalues $\\lambda$ of the discriminant operator $D=\\int\\int \\sqrt{p_{x\\to y}p_{y\\to x}}|x\\rangle\\langle y|\\,dx\\,dy$. The stationary distribution of the classical walk becomes a unit eigenvector of $W$, so the cost of preparing that state is governed by the phase gap, which is at least $2\\sqrt{\\delta}$ for spectral gap $\\delta$. For the hit-and-run walk in a well-rounded body the paper combines classical conductance bounds to argue the effective phase gap is $\\tilde{\\Omega}(n^{-3/2})$, turning a classical mixing time of $\\tilde{O}(n^3)$ into $\\tilde{O}(n^{1.5})$ membership queries per annealed sample. Around this core sit the Chebyshev cooling schedule, the nondestructive quantum Chebyshev mean estimator, and interlaced rounding by affine transformations.","core_discovery":"The central claim is Theorem 1.1: there is a quantum algorithm that, given a membership oracle for a convex body $K$ with $B_2(0,r)\\subseteq K\\subseteq B_2(0,R)$, returns a value $\\widetilde{\\mathrm{Vol}}(K)$ with $1/(1+\\epsilon)\\operatorname{Vol}(K)\\le \\widetilde{\\mathrm{Vol}}(K)\\le(1+\\epsilon)\\operatorname{Vol}(K)$ using $\\tilde{O}(n^3+n^{2.5}/\\epsilon)$ queries and $\\tilde{O}(n^5+n^{4.5}/\\epsilon)$ arithmetic operations. Compared with the best classical algorithm's $\\tilde{O}(n^4+n^3/\\epsilon^2)$ queries and $\\tilde{O}(n^6+n^5/\\epsilon^2)$ operations, this is the first quantum speedup for volume estimation, improving both query complexity and total gate count. The proof works by replacing the classical hit-and-run walk with a quantum hit-and-run walk, carrying the volume through a telescoping product of ratios $Z(a_{i+1})/Z(a_i)$ with bounded variance, and estimating each ratio with a nondestructive quantum version of Chebyshev's inequality. The paper also proves that any quantum volume estimator needs $\\Omega(\\sqrt{n})$ membership queries when $\\epsilon=\\Theta(1)$, showing that no exponential speedup is possible.","pith_inferences":["An implication the authors leave implicit is that the same framework should give quantum speedups for partition-function estimation and Bayesian evidence integrals, wherever Chebyshev cooling and a conductance bound are available.","The large gap between $\\tilde{O}(n^3)$ and $\\Omega(\\sqrt n)$ suggests that the true quantum query complexity may be substantially lower; a shorter annealing schedule or a sharper conductance analysis would be the natural next step rather than a new algorithmic idea.","Because the continuous-space spectral proof has a formal gap around $\\delta(0)$, the discretized analysis of Section 5 may prove to be the safer foundation; the continuous picture functions as a clean explanation, not necessarily the only route."],"forward_implications":["Volume estimation becomes quantumly faster than classical in both membership-query count and total arithmetic operations.","For constant precision, the $\\Omega(\\sqrt n)$ lower bound rules out superpolynomial quantum speedup, while the algorithm's dependence on $1/\\epsilon$ is optimal up to polylogarithmic factors.","Any simulated-annealing problem with a Chebyshev cooling schedule and a conductance lower bound inherits the same quadratic speedup in both mixing time and precision.","The discretized quantum hit-and-run walk gives a concrete implementation path with $\\tilde{O}(n)$ gate overhead per walk step and provably small discretization error."],"supporting_citations":[{"why":"Supplies the classical $\\tilde{O}(n^4)$ simulated-annealing algorithm, the pencil construction, and the Chebyshev cooling schedule that the quantum algorithm quantizes.","marker":"[45]"},{"why":"Provides the hit-and-run conductance and mixing-time bounds that the quantum phase-gap analysis rests on.","marker":"[44]"},{"why":"Gives the classical $\\tilde{O}(n^3)$ volume algorithm for well-rounded bodies, the baseline the quantum algorithm improves upon in that regime.","marker":"[16]"},{"why":"Supplies the slowly-varying Markov-chain preparation theorem and fixed-point amplitude amplification framework used to move between annealing distributions.","marker":"[65]"},{"why":"Provides the quantum Chebyshev inequality used for nondestructive mean estimation of each telescoping ratio.","marker":"[27]"},{"why":"Supplies the fixed-point amplitude amplification primitive that implements the rotations between stationary states.","marker":"[26]"},{"why":"Provides amplitude estimation, the subroutine underlying the quantum mean estimator and the query-count speedup in $1/\\epsilon$.","marker":"[10]"},{"why":"Provides the log-concave density rounding framework and affine-transformation lemma used for interlaced rounding.","marker":"[43]"},{"why":"Provides the $\\Omega(\\sqrt n)$ quantum search lower bound that the volume-estimation lower bound reduces from.","marker":"[8]"}],"fun_headline_variants":["Quantum walks estimate convex volumes faster","First quantum speedup for convex volume counting","Quantum hit-and-run cuts volume queries","Convex volumes yield to quantum algorithm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that the continuous-space quantum hit-and-run walk has the phase gap that drives the speedup treats the Dirac delta's value at zero as a finite positive number in Lemma 3.1 and defers rigor to a limit argument; if that gap fails, the $\\tilde{O}(n^{1.5})$-per-sample cost and the main theorem collapse.","fun_headline_variants_meta":{"raw":{"variants":["Quantum walks estimate convex volumes faster","First quantum speedup for convex volume counting","Quantum hit-and-run cuts volume queries","Convex volumes yield to quantum algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000289,"raw_usage":{"total_tokens":1767,"prompt_tokens":1096,"completion_tokens":671,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":712,"completion_tokens_details":{"reasoning_tokens":620}},"tokens_in":712,"tokens_out":671,"duration_ms":7396,"temperature":1.0,"reasoning_tokens":620,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:57:38.013543+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"An independent, fully rigorous Gaussian-limit computation of the discriminant operator $D$ for the hit-and-run transition density on the unit ball would settle the key spectral claim: if the phase gap is not $\\tilde{\\Omega}(n^{-3/2})$, then Lemma 4.8 and the $\\tilde{O}(n^{1.5})$ query count per annealing step fail. Equivalently, simulating the discretized walk at grid spacing $\\epsilon=1/n$ and checking whether the conductance bound (5.5) holds would test the implementation theorem directly.","supporting_citations":[{"cited_title":"2, 392–417, prelimi- nary version in 44th Annual IEEE Symposium on Foundations of Computer Science, pp","cited_arxiv_id":null,"evidence_quote":"Supplies the classical $\\tilde{O}(n^4)$ simulated-annealing algorithm, the pencil construction, and the Chebyshev cooling schedule that the quantum algorithm quantizes."},{"cited_title":"4, 985–1005","cited_arxiv_id":null,"evidence_quote":"Provides the hit-and-run conductance and mixing-time bounds that the quantum phase-gap analysis rests on."},{"cited_title":"Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume","cited_arxiv_id":"1409.6011","evidence_quote":"Gives the classical $\\tilde{O}(n^3)$ volume algorithm for well-rounded bodies, the baseline the quantum algorithm improves upon in that regime."},{"cited_title":"Quantum Chebyshev's Inequality and Applications","cited_arxiv_id":"1807.06456","evidence_quote":"Provides the quantum Chebyshev inequality used for nondestructive mean estimation of each telescoping ratio."},{"cited_title":"57–68, 2006","cited_arxiv_id":null,"evidence_quote":"Provides the log-concave density rounding framework and affine-transformation lemma used for interlaced rounding."}],"review_version":1}