PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved quantum volume estimation with transducers and amortized quantum walks

Arjan Cornelissen, Simon Apers, Sander Gribling

arXiv:2609.40217v1quant-phcs.CGcs.DS

TL;DR

The paper addresses relative volume estimation for convex bodies. It develops a transducer-based amortized quantum-walk framework to quantize the Cousins and Vempala approach, and proves a bounded-error quantum algorithm for volume estimation.

  • Problem

    The task is to estimate the volume of a convex body to a specified relative error, with the body containing the unit ball and lying inside a radius-R ball.

    Source: §1 · p. 3

  • Method

    The paper develops input-dependent transducer costs and quantum-walk reflection constructions to enable amortized analysis of quantum walks.

    Source: §1.1 · p. 4, §1.1.2 · p. 5, §1.2.2 · p. 8

  • Results

    A bounded-error quantum algorithm returns an ε-relative estimate of Vol(K) for d≥3 and R≥1.

    Source: §10.2 · p. 71

  • Takeaways & Limitations

    Input-dependent transducer complexity opens the door to amortizing quantum-walk costs.

    Source: §1.1 · p. 4

    Turning the uniform-sampling transducer into a quantum circuit incurs an O(1/ε^2) overhead.

    Source: §9.4 · p. 66

Abstract

from arXiv · show

The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many influential algorithmic techniques related to Markov Chain Monte Carlo and simulated annealing, and the problem connects to several important geometrical results, like the recently-resolved KLS conjecture. In this work, we quantize the state-of-the-art $\widetilde{O}(d^{3.5}+d^3/\varepsilon^2)$-query randomized algorithm developed by Cousins and Vempala, and obtain a $\widetilde{O}(d^{3.5} + d^{1.75}/\varepsilon)$-query quantum algorithm, improving over the $\widetilde{O}(d^{3.5} + d^{2.25}/\varepsilon)$ state-of-the-art bound. Our key technical contribution is a framework for amortizing the cost of a quantum walk. The framework is based on the recent transducer toolkit introduced by Belovs, Jeffery and Yolcu. It is this amortized quantum walk framework that allows us to exploit the amortized analysis of the ball walk by Cousins and Vempala, thus overcoming the key barrier that previously barred its quantum implementation.

1 Introduction

The section frames convex-body volume estimation and presents a bounded-error quantum algorithm for bodies between the unit ball and a radius-R ball. Its approach uses a transducer-based amortized quantum-walk framework to quantize the Cousins and Vempala algorithm.

1 Introduction

  • The volume-estimation task seeks an ε-precise relative estimate of Vol(K) for a convex body containing the unit ball and contained in a radius-R ball.The query model accesses K through membership queries.Source: §1 · p. 3
  • Cousins and Vempala estimate a partition function using Markov chain Monte Carlo and simulated annealing, with speedy-walk amortized analysis as a critical component.Source: §1 · p. 3
  • Earlier quantum algorithms quantize the hit-and-run approach, while the lack of suitable quantum amortized analysis had blocked quantization of.Source: §1 · p. 3
  • A bounded-error quantum algorithm estimates the volume of K when Bd⊆K⊆RBd.The theorem statement gives the setting but the supplied passage does not include its query bound.Source: §1 · p. 3
  • The new framework uses transducers, introduced by Belovs, Jeffery and Yolcu, to quantize.The paper identifies this framework as the basis of its algorithm.Source: §1 · p. 3

1.1 Main results: Transducers and amortized quantum walks

The section develops transducers as input-dependent quantum operations and uses them to build an amortized quantum-walk framework. It applies this framework to error-free amplitude amplification and quantum-walk reflection.

1.1 Main results: Transducers and amortized quantum walks

  • Input-dependent transduction complexity, unlike usual circuit complexity, opens the door to amortizing quantum-walk costs.A transducer can have different complexity on different input states, and it can be converted to a bounded-error quantum algorithm using O(W(U, |σ⟩)/ε^2) calls to U.Source: §1.1 · p. 4

1.1.1 Amplitude amplification transducer

  • The amplitude amplification construction yields transducers that construct and reflect around the amplified state without error.The approach does not produce garbage, a feature the authors say is necessary for their quantum-walk applications; compared with [ARZ26], it loses time efficiency but avoids garbage.Source: §1.1.1 · pp. 4–5
  • The amplitude amplification transducer supports transducer versions of quantum annealing, quantum rejection sampling, and quantum mean estimation, all used in the volume-estimation algorithm.The authors expect the technique to support porting further algorithmic primitives.Source: §1.1.1 · p. 4

1.1.2 Quantum walk reflection transducer

  • The quantum-walk reflection construction uses electric-flow edge weights to determine the catalyst for reflecting around a quantum version of the stationary distribution.It builds on an interpretation of states orthogonal to the stationary state as demand vectors on the Markov chain's electrical network.Source: §1.1.2 · p. 5
  • The reflection transducer amortizes the cost of preparing or reflecting around each star state over the relevant input distributions, but not the cost for orthogonal states.The authors say the non-amortized orthogonal-state cost is trivial in their algorithms.Source: §1.1.2 · p. 5

1.2 Main results: Quantum volume estimation

This section develops an amortized quantum-walk route to volume estimation by discretizing the speedy walk, implementing its reflections with transducers, and using them in quantum annealing. It also situates the approach among earlier classical and quantum algorithms.

1.2.1 State of the art

  • Before this work, Cornelissen and Hamoudi improved the construction by making mean estimation unbiased, obtaining the state-of-the-art quantum algorithm for volume estimation with eO(d^3.5 + d^2.25/ε) queries [CH23].Source: §1.2.1 · p. 7
  • Earlier randomized volume estimation combines rounding with partition-function estimation by sampling from Gibbs distributions along a cooling schedule.[CV18] uses the speedy walk to mix to those distributions.Source: §1.2.1 · p. 7

1.2.2 Quantum speedy walk

  • A sufficiently fine grid discretization relates the speedy walk's spectral gap and stationary distribution to those of the original walk, enabling the amortized quantum analysis.The grid spacing is used to make the state space finite and does not enter the final query complexity.Source: §1.2.2 · p. 8
  • A bipartite two-step walk separates proposal selection from the Metropolis transition, enabling efficient star-state and reflection transducers with one membership query each.The construction preserves the original speedy walk's spectral gap up to constant factors.Source: §1.2.2 · pp. 8–9

1.2.3 Quantum annealing transducer

  • Reflections between adjacent Gibbs states enable quantum annealing with constant amortized speedy-walk cost; the resulting transducer also improves uniform-superposition generation over a convex body.The paper presents this as a quantum analogue of [CV18, Theorem 1.2].Source: §1.2.3 · p. 9

1.2.4 Quantum volume estimation

  • eO(d^1.25/ε) is the quantum cost per temperature, with an additive eO(d^2) overhead from the longer annealing schedule.The resulting bounded-error estimator applies to convex bodies between the unit ball and a radius-R ball.Source: §1.2.4 · p. 10

1.3 Open questions

The open questions identify possible improvements to lower bounds, quantum rounding, walk amortization, and the analysis of the algorithm. They also outline alternative approaches and unresolved runtime questions.

Lower bounds

  • For constant precision, volume estimation requires at least eΩ(d^2) randomized membership queries, and the best-known upper and lower bounds remain separated.For fixed dimension, randomized and quantum query complexities are characterized separately.Source: §1.3 · p. 10

Hit-and-run walk

  • Recent hit-and-run analyses reduce uniform mixing to eO(d^2) steps; extending this to general logconcave distributions could let match 's randomized query bound.Quantizing that resulting algorithm could match this work's bound, but is unlikely to improve on it without additional ideas.Source: §1.3 · p. 10

Improving our analysis

  • Replacing the upper bound (δ′/δ)^d with a constant in Lemma 9.11 would remove the additive d^2 overhead from Theorem 1.8's complexity.The authors expect the annealing-cost bound can be tightened for bigger step-size updates.Source: §1.3 · p. 10
  • A further improvement to d^1.5/ε would require quadratically speeding up schedule-length dependence; the authors leave this approach for future work because it needs several new ideas.This would yield a full quadratic speed-up over the classical partition-function estimation algorithm.Source: §1.3 · pp. 10–11

Time complexity

  • The algorithm's time complexity remains unanalyzed; deriving some composition results directly from the adversary bound appears to forgo time-complexity considerations.Analyzing transducer-composition time efficiency is identified as future work.Source: §1.3 · p. 11

Quantum rounding

  • Quantum rounding remains open; its immediate technical bottleneck is non-destructive multivariate mean estimation, extending the univariate routine used here and in prior work.The proposed rounding approach quantizes.Source: §1.3 · p. 11

Quantum subroutine composition

  • For the speedy walk, the framework amortizes star-state generation, unlike [Jef22], which assumes that cost is unit and amortizes edge transitions.Amortizing edge-transition costs as well remains future work.Source: §1.3 · p. 11

Continuous-space quantum walks and transducers

  • Discretizing before quantization keeps the walks and transducers finite-dimensional; a continuous-space theory followed by discretization is an alternative whose impact is less clear.Quantum walks have already been treated to some extent in continuous space.Source: §1.3 · p. 11

1.4 Organization

The paper has two parts: the first develops a transducer-based amortized quantum-walk toolkit, and the second applies it to quantum volume estimation.

Part I

  • Part I develops the amortized quantum-walk toolkit: it introduces background, derives transducer amplitude amplification, and constructs a transducer reflecting through the stationary-distribution state.These topics appear in Sections 2–4.Source: §1.4 · p. 11

Part II

  • Part II applies the toolkit to volume estimation, developing discretization tools, an amortized quantum ball walk, and the quantum volume-estimation algorithm.The application spans Sections 5–10.Source: §1.4 · p. 11

2 Preliminaries: transducers and random walks

This section establishes the notation and preliminaries for the paper’s quantum-query, transducer, random-walk, electrical-network, and Markov-chain frameworks. It also presents a transducer result motivating a later reflection construction and relates effective resistance to a random walk’s spectral gap.

2.1 Notation

  • The notation section defines the unit ball, asymptotic bounds including eO, unitary operators, and probability distributions.It also fixes conventions for ± and ∓ and for graph neighborhoods.Source: §2.1 · p. 12

2.2 Quantum adversary bound for state conversion

  • State conversion asks an oracle algorithm to map input states to target states within precision η, and its query complexity is characterized using unidirectional and bidirectional adversary bounds.The bidirectional bound captures access to both forward and backward oracle queries [BY23].Source: §2.2 · pp. 12–13

2.3 Transducers

  • A canonical transducer’s catalyst gives a feasible unidirectional adversary solution, and feasible solutions yield canonical transducers; adversary bounds also characterize the query cost of state conversion.The paper additionally gives a route from a bidirectional adversary solution to a quantum algorithm using forward and backward oracle access.Source: §2.3 · pp. 15–16

2.4 Two-subspace transducer

  • A product of two reflections is a transducer on Ker(Π) with catalyst space Im(Π), and the paper uses this perspective to construct a transducer reflecting through a random walk’s stationary distribution.The two-subspace result is attributed to Apers, Roland and Zhang [ARZ26].Source: §2.4 · p. 16

2.5 Markov chains, random walks and electrical networks

  • An irreducible Markov process has a unique positive stationary distribution; walks on connected electrical networks are irreducible and reversible, with stationary probabilities proportional to inverse resistances.Conversely, every irreducible reversible Markov process can be represented as a walk on an electrical network [LP17].Source: §2.5 · pp. 16–17
  • For net-flow δ, effective resistance is δ^T L+δ, where L = BB^T is the weighted Laplacian.B is the resistance-weighted vertex-edge incidence matrix.Source: §2.5 · p. 17
  • The spectral gap is γ(P) = 1 − λ for the second-largest eigenvalue λ of an irreducible reversible Markov process; conductance is also defined.The section records a variational characterization of the gap and Cheeger inequalities relating gap and conductance [LP17, Lemma 13.7; LP17, Equation (13.6)].Source: §2.5 · p. 17
  • Since L = D(I − P), the spectrum of I − P equals that of D^-1/2 L D^-1/2, linking the walk’s spectral gap to effective resistance.The section states that the associated electrical-network theorem relates effective resistance for any net-flow to the spectral gap [Cor25, Lemma 3.2].Source: §2.5 · pp. 17–18

3 Amplitude amplification with transducers

This section develops transducer-level amplitude amplification, making the amplification step exact and extending transducer methods for state conversion, rejection sampling, quantile estimation, and mean estimation. It covers unbiased non-destructive mean estimation and its extension to approximate target distributions.

3.1 Base case

  • The base construction yields transducers for preparing an amplified state and reflecting through it; unlike [ARZ26, Theorem 6.1], it produces no garbage, though time-efficient implementation is unknown.Avoiding garbage is needed for the quantum walk operator developed in Section 4.Source: §3 · p. 18, §3.1 · pp. 20–21

3.2 Annealing transducer from two state-reflection transducers

  • Given transducers reflecting through two nonorthogonal states, the construction maps one state to the other, with cost depending on both reflection costs and their overlap.The theorem constructs a bidirectional canonical transducer for this state conversion.Source: §3.2 · p. 23

3.3 Rejection sampling and mean estimation with transducers

  • The rejection-sampling construction prepares and reflects through the q-sample of the posterior distribution proportional to π(ω)a(ω), assuming acceptance probabilities are computable without queries.The posterior normalizer is the average acceptance probability A.Source: §3.3 · pp. 24–25
  • When A is known, rebalancing can remove its dependence from the transduction complexity; when A is unknown, this rebalancing cannot be used.The construction also ports the unbiased, non-destructive bounded-variable mean-estimation routine from [CH23, Algorithm 3] to transducers.Source: §3.3 · p. 26
  • Fixed-point amplification for successful uncomputation can be made exact with transducers, removing a log(1/ε) factor from that step.The non-destructive coin flip is also implemented as a constant-cost transducer, and sequential composition yields a non-destructive transducer for the full algorithm.Source: §3.3 · p. 26
  • The quantile estimator returns q with P_{x~π}[X(x) ≤ q] ∈ [p − 3ε, p + 3ε] with probability at least 1 − ρ.It uses binary search over [0, M], estimating the threshold probability at each step.Source: §3.3 · p. 27
  • The section ports unbiased non-destructive mean estimation to transducers and generalizes it to a q-sample within total-variation distance η of the target distribution.The paper states that this generalization is needed for its volume-estimation algorithm.Source: §3.3 · p. 27

4 Reflection through the stationary state with transducers

This section develops transducers for reflecting through a random walk’s stationary distribution and introduces a bipartite Glauber walk to facilitate quantization, using parallel composition to amortize star-state reflection costs. It describes the walk’s relation to the original Glauber walk and outlines the adaptation and discretization of the classical speedy walk for quantum volume estimation.

4.1 Transducers for electrical networks

  • The stationary distribution is the intersection of two subspaces, enabling a transducer reflection that can be made canonical and input-independent.The initial construction uses spaces determined by the star states; the canonical construction depends on them only through three reflections, which can then be implemented canonically.Source: §4.1 · pp. 29–31

4.2 Amortized reflection through the stationary state

  • Parallel composition of vertex-specific star-state transducers amortizes reflection through the stationary distribution across vertices.For applications involving different walks and star states, the construction also uses transducers that construct the star states to act directly on the stationary state.Source: §4.2 · pp. 31–32

4.3 Metropolis filters via bipartite walks

  • The Glauber filter supports a bipartite walk with similar spectral properties, easily prepared star states, and no need for a filter, making it suitable for quantization.The construction is later used to quantize the speedy walk over a convex body.Source: §4.3 · pp. 33–34
  • For arbitrary graphs, the work generalizes a related bipartite construction for unweighted graphs and connects its spectral properties to those of the filtered walk.The cited construction was based on [Kos13, arXiv v2].Source: §4.3 · p. 34

4.3.1 Basic properties of Metropolis and Glauber filters

  • Metropolis and Glauber filtered transition probabilities are within a constant factor off the diagonal, so their conductances and spectral gaps are comparable.Both filtered chains have the same stationary distribution.Source: §4.3.1 · p. 34

4.3.2 Glauber filters via bipartite walks

  • The bipartite Glauber walk uses paired states so proposals in either direction yield the same outcome distribution, allowing the proposal to be forgotten.From a state x it samples y according to P(x,y) and outputs {x,y}; from the pair it outputs y with Glauber acceptance probability, and otherwise x.Source: §4.3.2 · pp. 34–35
  • The bipartite walk P′ satisfies (P′)^2|Ω = P_G and is reversible with respect to π′; if irreducible, it has a unique stationary distribution and spectral gap at least half that of P_G.Its eigenvalue −1 is also unique.Source: §4.3.2 · pp. 35–36
  • The volume-estimation algorithm follows Cousins and Vempala, discretizes their continuous-state speedy walk, and develops transducers to quantize it.The discretized walk is stated to retain a comparable spectral gap and similar stationary distribution when viewed as a function on R^d.Source: §4.3.2 · p. 37

5 Algorithm overview

The overview estimates volume through a telescoping product of partition-function ratios, using Gibbs sampling along a cooling schedule. It then combines random-walk mixing and annealing with amortized quantum walks to obtain the algorithm’s query bound.

5.1 Partition function estimation and cooling schedule

  • Volume estimation is reduced to estimating a telescoping product of partition-function ratios, with each factor estimated by sampling from a Gibbs distribution.The schedule is chosen so the random variables for its factors have bounded relative variance.Source: §5.1 · pp. 37–38
  • The inverse cooling schedule is shortened, while annealing uses intermediate temperatures to keep consecutive speedy-walk distributions warm.The classical algorithm’s total speedy-walk steps are eO((d^3 + d^2R^2)/ε^2), matching Cousins and Vempala.Source: §5.1 · p. 38, §5.3 · p. 39

5.2 Continuous space random walks: the ball walk and speedy walk

  • The ball walk has the Gibbs distribution as its stationary distribution but mixes poorly near corners; the speedy walk mixes rapidly, with a stationary distribution weighted by local conductance.Rejection sampling can recover an approximation to the Gibbs distribution from the speedy walk, and the body is clipped to use the conductance bound.Source: §5.2 · pp. 38–39

5.3 Annealing to obtain a warm start

  • Cousins and Vempala [CV18] use the speedy walk’s constant amortized step cost to bound the randomized algorithm’s total expected cost by eO(d^3/ε^2).A Markov inequality truncates the algorithm to a bounded-error Monte Carlo algorithm with worst-case cost eO(d^3/ε^2).Source: §5.3 · p. 40
  • The quantum query complexity is eO(d^2 + (d^(7/4) + d^(5/4)R)/ε), using an amortized quantum-walk framework.The framework yields two quadratic speedups over the corresponding expression for the randomized algorithm.Source: §5.3 · p. 40

6 Preliminaries: Markov chains on measurable spaces

This section sets up Markov chains on measurable spaces and explains how to relate them to finite-state chains. It also motivates controlling transition-probability perturbations when approximating walks.

6 Preliminaries: Markov chains on measurable spaces

  • A Markov kernel on a countably generated measurable space assigns measurable transition probabilities, and the paper restricts its results to Borel σ-algebras rather than general Lebesgue-measurable sets.The countable-generation condition is needed for results used in the work, including irreducibility results.Source: §6 · p. 40

6.1 Induced Markov chain

  • The induced finite chain preserves reversibility and irreducibility, and its conductance is at least that of the original continuous chain.These properties let the paper transfer conductance lower bounds from continuous processes to finite-state discretizations.Source: §6.1 · pp. 41–42

6.2 Perturbations of random walk transition probabilities

  • Directly implementing induced chains can be impractical because their transition probabilities may be hard to calculate, motivating approximations and analysis of their perturbations.The section examines the effects of such perturbations on stationary distributions and conductance.Source: §6.2 · pp. 42–43

7 Discretization of random walks over Rd

The section develops a grid-based approach for discretizing continuous random walks in Euclidean space. It uses smoothness assumptions to control approximation errors, while noting that conductance requires additional analysis.

7 Discretization of random walks over Rd

  • The discretization framework rounds points and functions to a grid and uses Jordan-measurable sets and piecewise Lipschitz-continuous functions to control approximation.The paper notes that the approach could extend to Riemannian manifolds, although it considers Euclidean space here.Source: §7 · p. 43, §7.1 · p. 44

7.1 Smoothness conditions on sets and functions

  • For piecewise Lipschitz-continuous functions, the paper establishes integral approximations by finite sums over the grid as the grid spacing decreases.The proof bounds boundary effects using the Jordan-measurability of the partition sets.Source: §7.1 · pp. 44–45, Figure 3 · p. 45

7.2 Discretization of walks with a Metropolis filter

  • For Metropolis walks with symmetric proposals and bounded piecewise-smooth densities, the naive grid discretization is reversible and has bounded perturbations from its continuous counterpart.The paper states that these conditions do not by themselves ensure similar conductances, so it requires an application-specific approach.Source: §7.2 · pp. 45–46

8 Speedy walk and discretization

This section develops continuous and grid versions of the speedy walk, showing how grid discretization approximates the continuous walk and yields a bipartite walk for the quantum algorithm. It also identifies an input-independent component of that walk and isolates star-state preparation and reflection as the remaining transducer task.

8.1 Properties of the continuous speedy walk

  • The continuous speedy walk has uniformly bounded, Lipschitz local conductance, and its conductance bound is extended to bodies contained in RBd.The stated step-size condition is δ ≤ min{1/(4βR), 1/√2β}.Source: §8.1 · p. 47

8.2 Discretization of the speedy walk

  • The discretization proof bounds conductance by starting from an enlarged convex body, then comparing the continuous, cube, induced, and final grid walks.For the final grid walk, proposals are chosen from grid points in the intersection of K with the step-size ball, followed by the same Metropolis filter.Source: §8.2 · p. 48, §8.2.3 · p. 51

8.2.1 Cube speedy walk

  • As ζ decreases, the cube speedy walk’s stationary distribution and transition kernel approach those of the continuous speedy walk, enabling conductance transfer for sufficiently small ζ.Source: §8.2.1 · pp. 49–50

8.2.2 Induced cube speedy walk

  • The induced cube walk aggregates the cube speedy walk onto grid points, and its stationary distribution and conductance bound follow from the cube-walk results.Source: §8.2.2 · pp. 50–51

8.2.3 Discretized speedy walk

  • For sufficiently small ζ, the discretized speedy walk has a conductance lower bound inherited through comparison with the induced cube walk.The grid walk is introduced because the induced cube walk’s transition probabilities cannot be efficiently implemented directly, but can be efficiently approximated.Source: §8.2.3 · pp. 51–52

8.3 The bipartite speedy walk

  • For sufficiently small ζ, the bipartite discretized speedy walk has spectral gap γ(P) ∈ Ω(δ^2β/d) when δ < min{1/(4βR), 1/√2β} and K ⊆ RBd.The construction replaces the Metropolis filter with a Glauber filter; this changes conductance and spectral gap by at most a factor of two.Source: §8.3 · p. 52
  • For the bipartite speedy walk, operations independent of input body K need no K queries (zero transduction complexity), leaving preparation and reflection of |∗x⟩ as the remaining transducer task.The walk is quantized by reflecting through star states associated with P.Source: §8.3 · pp. 52–53

9 Implementation of the speedy walk with transducers

This section develops transducer-based reflections for the discretized bipartite speedy walk and annealing between speedy-walk distributions with different parameters. It then implements annealing toward Gibbs distributions and a uniform superposition over a convex body, and explains the sampler’s usefulness as a subroutine despite a limitation relative to quantum circuits.

9 Implementation of the speedy walk with transducers

  • The section develops transducers that construct and reflect through stationary states of the discretized bipartite speedy walk.Source: §9 · p. 53

9.1 Reflections through stationary distributions of the speedy walk

  • Local star-state transducers are combined to implement reflection through the stationary distribution of the bipartite discretized speedy walk.Source: §9.1 · pp. 53–54

9.2 Annealing of speedy walk distributions

  • When speedy-walk parameters are sufficiently close, their distributions have constant overlap, enabling a transducer to map between them with constant overhead.The parameters include inverse temperature, step size, and clipping radius.Source: §9.2 · pp. 56, 58
  • The authors prove constant warmness for consecutive speedy-walk distributions, which Cousins and Vempala implicitly require but establish only for distributions arising from the ball walk.Source: §9.2 · p. 58
  • The speedy-walk distributions are annealed through successive δ_j values, with Theorem 9.12 applied iteratively to map between distributions.The passage defines δ_0 := δ and chooses k as the smallest integer with δ_k ≥ δ′.Source: §9.2 · p. 60

9.3 Mapping the speedy walk distribution to the Gibbs distribution

  • Following Cousins and Vempala [CV18, Section 6.4], rejection sampling removes an outer shell and scales the inner body to map speedy-walk distributions toward Gibbs distributions.The acceptance probability is at least 9/20; the reflection transducer is rebalanced using an input-independent constant α.Source: §9.3 · pp. 61–62
  • For β = 0, the usual transducer complexities blow up, so the construction switches to a different rejection-sampling routine.Source: §9.3 · p. 63

9.4 Uniform sampling from a convex body

  • Algorithm 1 constructs a bidirectional canonical transducer that outputs an ε-approximation to the uniform superposition over K.The theorem gives its transduction complexity, but the supplied passage does not include the complexity expression.Source: §9.4 · p. 65
  • Transducers incur an O(1/ε^2) overhead when converted to quantum circuits, but their composition properties let this sampler serve as a subroutine without that overhead.Source: §9.4 · p. 66

10 Quantum volume estimation

This section develops mean estimation over Gibbs distributions and ports Cousins and Vempala’s volume estimator to the quantum setting. It shows how Algorithm 2 approximates volume as a canonical transducer and can be turned into a quantum algorithm, while leaving time-complexity tracking for future work.

10.1 Mean estimation over Gibbs distributions

  • The mean-estimation component recovers [CH23, Algorithm 4] as a transducer and modifies [CH23, Algorithm 5] for the continuous setting using a known anti-concentration bound.The modification addresses the continuous energy levels in volume estimation, unlike the discrete setting considered in.Source: §10.1 · p. 68

10.2 Volume estimation

  • Because expectation and variance bounds are insufficient, the analysis adds anti-concentration for the squared norm under the Gibbs distribution to support median estimation during cooling.The analysis applies the anti-concentration bound to quantiles of the squared norm under the clipped Gibbs distribution.Source: §10.2 · pp. 70, 72
  • Algorithm 2 initializes a Gibbs state, follows an inverse-temperature schedule, estimates squared-norm medians and partition-function ratios, then multiplies the resulting estimates.Its input is a convex body accessible through a membership oracle, and its output is an ε-relative volume estimate.Source: §10.2 · p. 71
  • The quantum algorithm returns an ε-relative estimate of Vol(K) with success probability at least 2/3 using membership queries.The supplied theorem passage omits the query-complexity expression.Source: §10.2 · pp. 71, 73
  • Algorithm 2 is shown to be a canonical transducer that approximates the volume with the claimed success probability and transduction complexity W.The analysis then invokes Theorem 2.8 with K ∈ O(W) calls to U; because U makes a single query, the resulting quantum algorithm makes the claimed number of queries.Source: §10.2 · p. 74
  • The choice of sufficiently small ζ is left unspecified because it does not affect transduction or query complexity.Tracking time complexity requires determining ζ, and that analysis is left for future work.Source: §10.2 · p. 74

A Gaussian norm bounds

This section establishes bounds for Gaussian squared norms on a convex body and develops truncated-Gamma estimates used for radial bounds. It also verifies the logconcavity of a Gaussian normalization function used in the argument.

A Gaussian norm bounds

  • E[||x||^2] ≤ d/β for the Gaussian distribution on K, and the section also establishes upper bounds on its variance.The proof obtains the expectation bound from logconcavity of a rescaled integral and uses it to derive variance bounds.Source: A Gaussian norm bounds · p. 78
  • The normalization function z(a) is logconcave, correcting a gap in Cousins and Vempala’s stated justification.The passage notes that the claim does not follow from their earlier-stated Lemma 7.11, but is established above.Source: A Gaussian norm bounds · p. 78
  • For a truncated-Gamma random variable with α ≥ 2, β, L > 0, the passages state E[S] = Ω(L), ||p||∞ ≤ Cα/L, and E[S] = Ω(α/β), ||p||∞ ≤ Cβ/√α.Source: A Gaussian norm bounds · p. 79
  • The proof uses these truncated-Gamma properties to obtain bounds for the squared norm conditioned on a direction, then derives a bound for norm intervals.The radial parameter depends on the direction through the distance to the boundary of K.Source: A Gaussian norm bounds · pp. 78–80

B Proof of Lemma 9.9

The proof compares the volumes of S, H, and G using a reflection and a dilation inclusion. These steps provide the volume comparison used in Lemma 9.9.

B Proof of Lemma 9.9

  • Reflection across the hyperplane through x perpendicular to v maps S outside H injectively into H, giving Vol(S) ≤ 2 Vol(H).The reflection preserves volume.Source: B Proof of Lemma 9.9 · p. 80
  • The proof next seeks to bound Vol(H) in terms of Vol(G), claiming α(H \ G) ⊆ G; it then states that this proves the claim and continues.Source: B Proof of Lemma 9.9 · pp. 80–81
  • For y in H outside G, the scaled point αy lies in G, yielding the inclusion α(H \ G) ⊆ G.The proof uses convexity of K, 0 ∈ K, and the stated norm bounds on x and y.Source: B Proof of Lemma 9.9 · p. 80

Related papers

Loading 2609.40217v1…