Pith. sign in

REVIEW 2 major objections 5 minor 67 references

Quantum algorithm for estimating volumes of convex bodies

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

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

desk verdict Solid first quantum speedup for volume estimation; main claims hold up, the Lemma 4.3 truncation worry misfires, and the paper deserves peer review. read the letter →

arxiv 1908.03903 v3 pith:H4AVLWGQ submitted 2019-08-11 quant-ph cs.DSmath.OC

Shouvanik Chakrabarti , Andrew M. Childs , Shih-Han Hung , Tongyang Li , Chunhao Wang , Xiaodi Wu This is my paper · ORCID
classification quant-phcs.DSmath.OC MSC 68Q1268Q1768W2052A38 PACS 03.67.Ac
keywords volumeestimationconvexbodiesquantumquerycomplexitywalkssimulatedannealingChebyshevcoolingMarkovchainMonteCarlomembershiporacle
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

2 major / 5 minor

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.

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 (2)
  1. [Section 4.3.3 (Lemma 4.3) with Section 2.3 (Theorem 2.3)] 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.
  2. [Section 3.1 (Lemma 3.1 and Theorem 3.1)] 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.
minor comments (5)
  1. [Section 6, Algorithm 6] 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'.
  2. [Section 4.3.1 (Lemma 4.1)] 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.
  3. [Section 4.3.3 (Lemma 4.3)] 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.
  4. [Section 4.3.3 (Lemma 4.6)] 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.
  5. [Section 4.2] In the first bullet, 'queries to the membership oracle fora the well-rounded convex body' contains a typo ('fora' should be 'for').

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the volume estimate is an unbiased telescoping product, and all load-bearing lemmas come from external work or are independently derived.

full rationale

The derivation chain is self-contained. The estimate ~Vol(K') is the product over i of ~V_i, each an epsilon-relative estimate of E_{pi_i}[V_i] = Z(a_{i+1})/Z(a_i) (Eq. 4.7). This equality is a definitional identity of the estimator, not a fitted parameter: V_i is defined as e^{(a_i-a_{i+1})X_0} with X_0 drawn from pi_i, so E[V_i] equals the ratio of the two partition functions by direct integration. The Chebyshev cooling schedule and the sample count are fixed by the variance bound E[V_i^2]/E[V_i]^2 < 8 (Proposition 4.2, from [45, Lemma 4.1]), which is independent of Vol(K). The inner-product lower bound (Lemma 4.2) follows from the log-concavity of a^{n+1}Z(a) ([45, Lemma 3.2]). The stationary-state preparation uses the quantum MCMC framework of [65] and the classical hit-and-run mixing time of [44] (Theorem 2.5); Proposition 4.3, which transfers mixing to a spectral-gap lower bound, is proved from the paper's own continuous-space quantum walk analysis. Rounding uses [43, Lemma 2.2] and [29, Lemma 4.3], with Lemma 4.6 proved in the paper from [45, Lemma 3.2]. The lower bound (Theorem 6.1) is a reduction from search. The only self-citation, [12], appears in the introduction for comparison and is not load-bearing. The footnote about delta(0) (Section 3.1) flags a rigor gap in the continuous-space walk theory, but it is a mathematical-technical issue, not circularity: the claimed reduction does not rely on the target volume. No equation is defined in terms of the final answer, and no fitted parameter is renamed as a prediction.

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

The paper introduces no free parameters fitted to data; the schedule step size and constants are chosen to satisfy variance and error bounds, not to fit the target volume. It relies on four background groups: classical hit-and-run mixing time, quantum Chebyshev inequality, Szegedy's quantum walk framework, and Lovasz-Vempala's pencil/Chebyshev cooling construction. No new physical entities are postulated.

assumptions (4)
  • domain assumption Classical hit-and-run walk mixes in O-tilde(n^3) steps from a warm start for well-rounded log-concave densities (Theorem 2.4 and Theorem 2.5 of [44]).
    Invoked in Section 4.3.4 and Lemma 4.8 to argue that a density mixed in t steps has small overlap with low-eigenvalue eigenvectors, giving a large effective spectral gap.
  • domain assumption Quantum Chebyshev inequality (Theorem 2.3 of [27]) supplies multiplicative mean estimation with O-tilde(1/epsilon) calls to a quantum sampler.
    Used in Lemma 4.3 and Lemma 4.9 to estimate each telescoping ratio E[V_i] with relative error epsilon using O-tilde(sqrt(n)/epsilon) copies.
  • standard math The Szegedy correspondence between a reversible Markov chain's spectral gap and the phase gap of its quantum walk extends to continuous state spaces (Section 3).
    This is the paper's own technical development, but it relies on the general framework of Szegedy [62] and the assumption that the discriminant operator has discrete spectrum via compactness.
  • domain assumption The pencil construction and the Chebyshev cooling schedule of [45] yield bounded variance ratios (Proposition 4.2, Eq. (4.8)).
    This is a classical result from Lovasz and Vempala that the paper uses wholesale; it underpins the middle-level sample complexity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum algorithm for estimating volumes of convex bodies." pith.science (2026). https://pith.science/paper/H4AVLWGQ

@misc{pith2026190803903,
  author       = {Pith},
  title        = {Pith review of: Quantum algorithm for estimating volumes of convex bodies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H4AVLWGQ}},
  note         = {Machine review of arXiv:1908.03903}
}
abstract

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an $n$-dimensional convex body within multiplicative error $\epsilon$ using $\tilde{O}(n^{3}+n^{2.5}/\epsilon)$ queries to a membership oracle and $\tilde{O}(n^{5}+n^{4.5}/\epsilon)$ additional arithmetic operations. For comparison, the best known classical algorithm uses $\tilde{O}(n^{4}+n^{3}/\epsilon^{2})$ queries and $\tilde{O}(n^{6}+n^{5}/\epsilon^{2})$ additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of "Chebyshev cooling", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requires $\Omega(\sqrt n+1/\epsilon)$ quantum membership queries, which rules out the possibility of exponential quantum speedup in $n$ and shows optimality of our algorithm in $1/\epsilon$ up to poly-logarithmic factors.

Figures

Figures reproduced from arXiv: 1908.03903 by the authors.

Figure 1
Figure 1. The structure of our quantum volume estimation algorithm. The four purple frames represent the [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. The quantum circuit for amplitude estimation. [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. The quantum circuit for Algorithm 3 (assuming well-roundedness). Here [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: The quantum circuit for nondestructive BasicEst. Large effective spectral gap Consider an ergodic, reversible Markov chain (Ω, p) with tran￾sition matrix P and a unique stationary distribution with density π. Let a(x) be a probability measure over Ω such that the Marko…
Figure 5
Figure 5. Figure 5: The quantum phase estimation circuit. Here [PITH_FULL_IMAGE:figures/full_fig_p038_5.png]
Figure 6
Figure 6. Figure 6: Constructing a hyperpyramid. The inner circle represents the unit ball and the outer circle [PITH_FULL_IMAGE:figures/full_fig_p044_6.png]
Figure 7
Figure 7. Figure 7: A demonstration of the 2-level discretization of K. The thicker grid represents the coarser dis [PITH_FULL_IMAGE:figures/full_fig_p045_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 43 canonical work pages

  1. [1]

    50– 59, 2001, arXiv:quant-ph/0012090

    Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani, Quantum walks on graphs, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 50– 59, 2001, arXiv:quant-ph/0012090

    arXiv 2001

  2. [2]

    20– 29, 2003, arXiv:quant-ph/0301023

    Dorit Aharonov and Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 20– 29, 2003, arXiv:quant-ph/0301023

    arXiv 2003

  3. [3]

    Gorjan Alagic and Alexander Russell, Decoherence in quantum walks on the hypercube, Physical Review A 72 (2005), 062304, arXiv:quant-ph/0501169

    work page Pith review arXiv 2005

  4. [4]

    37–49, 2001

    Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous, One- 52 dimensional quantum walks , Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 37–49, 2001

    work page 2001

  5. [5]

    Joran van Apeldoorn, Andr´ as Gily´ en, Sander Gribling, and Ronald de Wolf,Convex optimiza- tion using quantum oracles , 2018, arXiv:1809.00643

    arXiv 2018

  6. [6]

    156–163, 1991

    David Applegate and Ravi Kannan, Sampling and integration of near log-concave functions , Proceedings of the 23nd Annual ACM Symposium on Theory of Computing, pp. 156–163, 1991

    work page 1991

  7. [7]

    4, 319–326

    Imre B´ ar´ any and Zolt´ an F¨ uredi,Computing the volume is difficult , Discrete & Computational Geometry 2 (1987), no. 4, 319–326

    work page 1987

  8. [8]

    Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, Strengths and weaknesses of quantum computing , SIAM Journal on Computing 26 (1997), no

    Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, Strengths and weaknesses of quantum computing , SIAM Journal on Computing 26 (1997), no. 5, 1510–1523, arXiv:quant-ph/9701001

    arXiv 1997

Show all 67 references
  1. [9]

    Somma, Quantum algorithms for simulated annealing , 2015, arXiv:1512.03806

    Sergio Boixo and Rolando D. Somma, Quantum algorithms for simulated annealing , 2015, arXiv:1512.03806

    2015 arXiv

  2. [10]

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplifica- tion and estimation, Contemporary Mathematics 305 (2002), 53–74, arXiv:quant-ph/0005055

    2002 arXiv

  3. [11]

    820–831, 1998, arXiv:quant-ph/9805082

    Gilles Brassard, Peter Høyer, and Alain Tapp, Quantum counting , Proceedings of the 25th International Colloquium on Automata, Languages, and Programming, pp. 820–831, 1998, arXiv:quant-ph/9805082

    1998 arXiv

  4. [12]

    Childs, Tongyang Li, and Xiaodi Wu,Quantum algorithms and lower bounds for convex optimization , 2018, arXiv:1809.01731

    Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu,Quantum algorithms and lower bounds for convex optimization , 2018, arXiv:1809.01731

    2018 arXiv

  5. [13]

    Shantanav Chakraborty, Kyle Luh, and J´ er´ emie Roland,On analog quantum algorithms for the mixing of Markov chains , 2019, arXiv:1904.11895

    2019 arXiv

  6. [14]

    Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A

    Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman, Exponential algorithmic speedup by quantum walk , Proceedings of the 35th ACM Symposium on Theory of Computing, pp. 59–68, 2003, quant-ph/0209131

    2003 arXiv

  7. [15]

    1215–1228, 2014, arXiv:1306.5829

    Ben Cousins and Santosh Vempala, A cubic algorithm for computing Gaussian volume , Pro- ceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1215–1228, 2014, arXiv:1306.5829

    2014 arXiv

  8. [16]

    539– 548, 2015, arXiv:1409.6011

    Ben Cousins and Santosh Vempala, Bypassing KLS: Gaussian cooling and an O∗(n3) volume algorithm, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pp. 539– 548, 2015, arXiv:1409.6011

    2015 arXiv

  9. [17]

    Dawson and Michael A

    Christopher M. Dawson and Michael A. Nielsen, The Solovay-Kitaev algorithm , Quantum Information & Computation 6 (2006), no. 1, 81–95, arXiv:quant-ph/0505030

    2006 arXiv

  10. [18]

    Martin Dyer and Alan Frieze, Computing the volume of convex bodies: a case where randomness provably helps, Probabilistic Combinatorics and its Applications 44 (1991), 123–170

    1991

  11. [19]

    Martin Dyer, Alan Frieze, and Ravi Kannan, A random polynomial-time algorithm for approx- imating the volume of convex bodies , Journal of the ACM 38 (1991), no. 1, 1–17. 53

    1991

  12. [20]

    Dyer and Alan M

    Martin E. Dyer and Alan M. Frieze,On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing 17 (1988), no. 5, 967–974

    1988

  13. [21]

    4, 289–292

    Gy¨ orgy Elekes,A geometric inequality and the complexity of computing volume , Discrete & Computational Geometry 1 (1986), no. 4, 289–292

    1986

  14. [22]

    2, 915–928, arXiv:quant-ph/9706062

    Edward Farhi and Sam Gutmann, Quantum computation and decision trees , Physical Review A 58 (1998), no. 2, 915–928, arXiv:quant-ph/9706062

    1998 arXiv

  15. [23]

    1, 14–26

    Alan Frieze and Ravi Kannan, Log-Sobolev inequalities and sampling from log-concave distri- butions, The Annals of Applied Probability 9 (1999), no. 1, 14–26

    1999

  16. [24]

    2, Springer Science & Business Media, 2012

    Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver,Geometric algorithms and combi- natorial optimization, vol. 2, Springer Science & Business Media, 2012

    2012

  17. [25]

    Lov Grover and Terry Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions, 2002, arXiv:quant-ph/0208112

    2002 arXiv

  18. [26]

    Grover, A different kind of quantum search , 2005, arXiv:quant-ph/0503205

    Lov K. Grover, A different kind of quantum search , 2005, arXiv:quant-ph/0503205

    2005 arXiv

  19. [27]

    Yassine Hamoudi and Fr´ ed´ eric Magniez,Quantum Chebyshev’s inequality and applications , Proceedings of the 46th International Colloquium on Automata, Languages, and Program- ming, Leibniz International Proceedings in Informatics, vol. 132, pp. 69:1–69:16, 2019, arXiv:1807.06456

    2019 arXiv

  20. [28]

    Harrow and Annie Y

    Aram W. Harrow and Annie Y. Wei, Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions , To appear in the Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, 2020, arXiv:1907.09965

    2020 arXiv

  21. [29]

    Kalai and Santosh Vempala, Simulated annealing for convex optimization , Mathe- matics of Operations Research 31 (2006), no

    Adam T. Kalai and Santosh Vempala, Simulated annealing for convex optimization , Mathe- matics of Operations Research 31 (2006), no. 2, 253–266

    2006

  22. [30]

    Ravi Kannan, L´ aszl´ o Lov´ asz, and Mikl´ os Simonovits,Random walks and an O∗(n5) volume algorithm for convex bodies , Random Structures & Algorithms 11 (1997), no. 1, 1–50

    1997

  23. [31]

    Khachiyan, On the complexity of computing the volume of a polytope , Izvestia Akad

    Leonid G. Khachiyan, On the complexity of computing the volume of a polytope , Izvestia Akad. Nauk SSSR, Engineering Cybernetics 3 (1988), 216–217

    1988

  24. [32]

    Khachiyan, The problem of computing the volume of polytopes is NP-hard , Uspekhi Mat

    Leonid G. Khachiyan, The problem of computing the volume of polytopes is NP-hard , Uspekhi Mat. Nauk 44 (1989), no. 3, 199–200

    1989

  25. [33]

    Vempala, Efficient convex optimization with membership oracles, Proceedings of the 31st Conference on Learning Theory, Proceedings of Machine Learning Research, vol

    Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala, Efficient convex optimization with membership oracles, Proceedings of the 31st Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 75, pp. 1292–1294, 2018, arXiv:1706.07357

    2018 arXiv

  26. [34]

    1049–1065, 2015, arXiv:1508.04874

    Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong, A faster cutting plane method and its implications for combinatorial and convex optimization , Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 1049–1065, 2015, arXiv:1508.04874

    2015 arXiv

  27. [35]

    Yin Tat Lee and Santosh S. Vempala, Eldan’s stochastic localization and the KLS hyperplane conjecture: An improved lower bound for expansion , Proceedings of the 58th Annual Sympo- sium on Foundations of Computer Science, pp. 998–1007, 2017, arXiv:1612.01507. 54

    2017 arXiv

  28. [36]

    Vempala, Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation , Proceedings of the 50th Annual Symposium on Theory of Computing, pp

    Yin Tat Lee and Santosh S. Vempala, Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation , Proceedings of the 50th Annual Symposium on Theory of Computing, pp. 1115–1121, 2018, arXiv:1710.06261

    2018 arXiv

  29. [37]

    Vempala, The Kannan-Lov´ asz-Simonovits conjecture, 2018, arXiv:1807.03465

    Yin Tat Lee and Santosh S. Vempala, The Kannan-Lov´ asz-Simonovits conjecture, 2018, arXiv:1807.03465

    2018 arXiv

  30. [38]

    Levin, Yuval Peres, and Elizabeth L

    David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times , American Mathematical Society, 2017

    2017

  31. [39]

    5, 2899–2921, arXiv:1710.06025

    Tongyang Li and Xiaodi Wu, Quantum query complexity of entropy estimation , IEEE Trans- actions on Information Theory 65 (2019), no. 5, 2899–2921, arXiv:1710.06025

    2019 arXiv

  32. [40]

    3, 443–461

    L´ aszl´ o Lov´ asz,Hit-and-run mixes fast, Mathematical Programming 86 (1999), no. 3, 443–461

    1999

  33. [41]

    346–354, 1990

    L´ aszl´ o Lov´ asz and Mikl´ os Simonovits,The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume , Proceedings of the 31st Annual Symposium on Foun- dations of Computer Science, pp. 346–354, 1990

    1990

  34. [42]

    4, 359–412

    L´ aszl´ o Lov´ asz and Mikl´ os Simonovits,Random walks in a convex body and an improved volume algorithm, Random Structures & Algorithms 4 (1993), no. 4, 359–412

    1993

  35. [43]

    57–68, 2006

    L´ aszl´ o Lov´ asz and Santosh Vempala,Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization , Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 57–68, 2006

    2006

  36. [44]

    4, 985–1005

    L´ aszl´ o Lov´ asz and Santosh Vempala,Hit-and-run from a corner, SIAM Journal on Computing 35 (2006), no. 4, 985–1005

    2006

  37. [45]

    2, 392–417, prelimi- nary version in 44th Annual IEEE Symposium on Foundations of Computer Science, pp

    L´ aszl´ o Lov´ asz and Santosh Vempala,Simulated annealing in convex bodies and an O∗(n4) vol- ume algorithm, Journal of Computer and System Sciences 72 (2006), no. 2, 392–417, prelimi- nary version in 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 650- 659, 2003

    2006

  38. [46]

    3, 307–358

    L´ aszl´ o Lov´ asz and Santosh Vempala,The geometry of logconcave functions and sampling al- gorithms, Random Structures Algorithms 30 (2007), no. 3, 307–358

    2007

  39. [47]

    1, 142–164, arXiv:quant-ph/0608026

    Fr´ ed´ eric Magniez, Ashwin Nayak, J´ er´ emie Roland, and Miklos Santha,Search via quantum walk, SIAM Journal on Computing 40 (2011), no. 1, 142–164, arXiv:quant-ph/0608026

    2011 arXiv

  40. [48]

    2, 645–646

    George Marsaglia, Choosing a point from the surface of a sphere , The Annals of Mathematical Statistics 43 (1972), no. 2, 645–646

    1972

  41. [49]

    2181, 20150301, arXiv:1504.06987

    Ashley Montanaro, Quantum speedup of Monte Carlo methods , Proceedings of the Royal So- ciety A 471 (2015), no. 2181, 20150301, arXiv:1504.06987

    2015 arXiv

  42. [50]

    Muller, A note on a method for generating points uniformly on n-dimensional spheres, Communications of the ACM 2 (1959), no

    Mervin E. Muller, A note on a method for generating points uniformly on n-dimensional spheres, Communications of the ACM 2 (1959), no. 4, 19–20

    1959

  43. [51]

    Briegel, and Vedran Dunjko, Faster quantum mixing for slowly evolv- ing sequences of Markov chains , Quantum 2 (2018), 105, arXiv:1503.01334

    Davide Orsucci, Hans J. Briegel, and Vedran Dunjko, Faster quantum mixing for slowly evolv- ing sequences of Markov chains , Quantum 2 (2018), 105, arXiv:1503.01334. 55

    2018 arXiv

  44. [52]

    3, 1037–1069, arXiv:cs/0608054

    Luis Rademacher and Santosh Vempala, Dispersion of mass and the complexity of ran- domized geometric algorithms , Advances in Mathematics 219 (2008), no. 3, 1037–1069, arXiv:cs/0608054

    2008 arXiv

  45. [53]

    Richter, Almost uniform sampling via quantum walks , New Journal of Physics 9 (2007), no

    Peter C. Richter, Almost uniform sampling via quantum walks , New Journal of Physics 9 (2007), no. 3, 72, arXiv:quant-ph/0606202

    2007 arXiv

  46. [54]

    Richter, Quantum speedup of classical mixing processes, Physical Review A 76 (2007), no

    Peter C. Richter, Quantum speedup of classical mixing processes, Physical Review A 76 (2007), no. 4, 042306, arXiv:quant-ph/0609204

    2007 arXiv

  47. [55]

    1, 60–72, arXiv:math/9608208

    Mark Rudelson, Random vectors in the isotropic position , Journal of Functional Analysis 164 (1999), no. 1, 60–72, arXiv:math/9608208

    1999 arXiv

  48. [56]

    3, McGraw-Hill, 1964

    Walter Rudin, Principles of mathematical analysis , vol. 3, McGraw-Hill, 1964

    1964

  49. [57]

    Jun John Sakurai and Jim Napolitano, Modern quantum mechanics, Pearson Harlow, 2014

    2014

  50. [58]

    Smith, Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions, Operations Research 32 (1984), no

    Robert L. Smith, Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions, Operations Research 32 (1984), no. 6, 1296–1308

    1984

  51. [59]

    Somma, Sergio Boixo, and Howard Barnum, Quantum simulated annealing, 2007, arXiv:0712.1008

    Rolando D. Somma, Sergio Boixo, and Howard Barnum, Quantum simulated annealing, 2007, arXiv:0712.1008

    2007 arXiv

  52. [60]

    Somma, Sergio Boixo, Howard Barnum, and Emanuel Knill, Quantum simula- tions of classical annealing processes , Physical Review Letters 101 (2008), no

    Rolando D. Somma, Sergio Boixo, Howard Barnum, and Emanuel Knill, Quantum simula- tions of classical annealing processes , Physical Review Letters 101 (2008), no. 13, 130504, arXiv:0804.1571

    2008 arXiv

  53. [61]

    3, 1–36, arXiv:cs/0612058

    Daniel ˇStefankoviˇ c, Santosh Vempala, and Eric Vigoda,Adaptive simulated annealing: A near- optimal connection between sampling and counting, Journal of the ACM 56 (2009), no. 3, 1–36, arXiv:cs/0612058

    2009 arXiv

  54. [62]

    32–41, 2004

    Mario Szegedy, Quantum speed-up of Markov chain based algorithms , Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 32–41, 2004

    2004

  55. [63]

    Osborne, Karl G

    Kristan Temme, Tobias J. Osborne, Karl G. Vollbrecht, David Poulin, and Frank Verstraete, Quantum Metropolis sampling, Nature 471 (2011), no. 7336, 87–90, arXiv:0911.3635

    2011 arXiv

  56. [64]

    52, MSRI, 2005, pp

    Santosh Vempala, Geometric random walks: a survey , Combinatorial and Computational Ge- ometry, Mathematical Sciences Research Institute Publications, vol. 52, MSRI, 2005, pp. 573– 612

    2005

  57. [65]

    4, 042336, arXiv:0804.4259

    Pawel Wocjan and Anura Abeyesinghe, Speedup via quantum sampling, Physical Review A 78 (2008), no. 4, 042336, arXiv:0804.4259

    2008 arXiv

  58. [66]

    2, 022340, arXiv:0811.0596

    Pawel Wocjan, Chen-Fu Chiang, Daniel Nagaj, and Anura Abeyesinghe, Quantum algo- rithm for approximating partition functions , Physical Review A 80 (2009), no. 2, 022340, arXiv:0811.0596

    2009 arXiv

  59. [67]

    3, 754–759, arXiv:1011.1468

    Man-Hong Yung and Al´ an Aspuru-Guzik, A quantum–quantum Metropolis algorithm , Pro- ceedings of the National Academy of Sciences 109 (2012), no. 3, 754–759, arXiv:1011.1468. 56

    2012 arXiv

Pith tools

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