acceptodds
Under review as a conference paper at ICLR 2027

Quantum Global Smooth Nonconvex Optimization under Weak Localization

Abstract

We develop a fully discrete quantum simulated-annealing framework for global optimization of smooth non-convex functions under a weak localization assumption: a known bounded region contains an -optimal solution of the original problem. This assumption is strictly weaker than the dissipativity conditions commonly imposed in Langevin-based analyses. Unlike continuous-space formulations that defer discretization to implementation, our algorithm is defined end-to-end on a finite discrete space and can be implemented with finite registers using only function and gradient access. We provide an explicit spectral-gap lower bound for the underlying discrete walk, which in turn gives a computable phase-gap guarantee for the quantum walk and makes the resulting complexity fully quantifiable under weak localization. While a polynomial gap cannot be guaranteed uniformly over this broad problem class without additional structural assumptions, we derive an unconditional and computable lower bound that can be supplied directly to the algorithm. This yields a complexity guarantee without requiring stronger structural assumptions. Overall, our framework makes the spectral-gap limitations of weakly localized non-convex optimization explicit while reducing the annealing costs through adaptive temperature selection.

Primary area:
optimization
Keywords:
Quantum computing, Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_AzCKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies quantum global optimization of smooth nonconvex functions under a weak localization assumption: a known bounded region contains an approximately globally optimal solution. This assumption is strictly weaker than the dissipativity conditions commonly used in Langevin-based optimization. The authors propose algorithms and provide explicit complexity guarantees for them.

Critical strengths
  • Global optimization under weaker assumptions. The paper extends quantum Langevin-based nonconvex optimization beyond the commonly imposed dissipativity condition by introducing a strictly weaker localization assumption. This broadens the class of objectives.

  • Rigorous discrete construction with explicit complexity guarantees. Their technical strength of the theoretical bounds looks strong to me.

Critical weaknesses
  • Limited efficiency guarantees and unclear quantum advantage. Although the paper derives an explicit spectral-gap lower bound, this bound can be exponentially small in the dimension and inverse temperature, leading to potentially undesirable query complexity.
Questions for authors

See the weakness part.

2 comments

We thank the reviewer for recognizing the broader scope enabled by weak localization and the rigor of our discrete construction. Our contribution is an end-to-end quantum optimization guarantee under smoothness and weak localization, with discretization and implementation errors explicitly controlled. The explicit gap certificate makes this guarantee computable without imposing additional mixing assumptions.

To address the concern about efficiency, we have sharpened the spectral-gap analysis, reducing the inverse-temperature dependence in the resulting query bound. Moreover, Theorem~13 accommodates any valid uniform gap bound along the annealing path, so stronger instance-specific mixing estimates directly improve the optimization guarantee. We will incorporate the sharper analysis and clarify when the resulting query bound improves on classical grid search.

Thank you for addressing my questions. The new results resolve my main concerns, and I’ll maintain my positive score.

Reviewer_E1KwOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies global minimization of a smooth non-convex functions from a quantum sampling perspective. They assume that an approximate optimum lies in a known ball B(0,R)B(0,R). The authors call this assumption "weak localization" a strictly relaxed assumption than dissipativity used in previous sampling papers. The idea is to propose an end-to-end optimization algorithm using quantum MALA (equipped with adaptive annealing schedule) and then perform the sampling at sufficiently large β\beta values. The main motivation of the paper seems to give an algorithm that takes the discretization into account end-to-end.

Critical strengths
  • The motivation of the paper is relevant and implementation of the continuous algorithms on a quantum computer is an issue that is repeatedly encountered in the field.

  • Earlier quantum Langevin and MALA algorithms (Childs et al., 2022; Ozgul et al., 2024) are formulated with continuous-space walks, and Ozgul et al. defer the digitization error to the analysis of Chakrabarti et al. (2023). This paper instead builds the digitization into the chain and defines the whole pipeline on a finite grid. The analyzed chain is therefore exactly the implemented one.

  • Lemma 4 bounds the discrete-to-continuous total-variation error with a clean scaling argument at the boundary. Lemma 15 prepares the uniform state on the admissible cells of a ball to any precision, without computing ball–cell intersection volumes. Lemma 21 lower-bounds sublevel volumes even when the minimizer lies on the boundary. Much of this machinery can be reused for quantum sampling/optimization.

  • Working on a compact domain avoids the full-space normalizability and tail conditions of earlier analyses. The reduction from Gibbs sampling to optimization is fully explicit, including the choice of β\beta.

  • As far as I know the adaptive schedule is used for the first time in the context of nonlogconcave sampling although it was proposed by Harrow, Wei.

Critical weaknesses
  • While I understand the motivation, I don't find analyzing the spectral gap of the discrete chain as a feasible route to resolve the issue the paper is pointing at. The reason is that the discrete chain can have very bad spectral gap introduced by the discretization even though the spectral gap of the continuous one is good (apologies, I could not find a proper reference but the same issue appears frequently in classical algorithms as pointed below and also hamiltonian simulation problems). Here, I am not criticizing that that spectral gap bound is exponentially bad for general nonconvex functions. This is expected, however the authors' bound is very loose beyond the ladscape of the function.

  • To show this point for example, the spectral gap bound contains a factor e−2βD^Re^{-2\beta\hat D_R}. With the choices of Theorem 13, in particular h≤ϵˉ/(2GRd)h\le\bar\epsilon/(2G_R\sqrt d), this gives the factor eβD^Re^{\beta\hat D_R} alone is at least (8RGR/ϵˉ)8dRGR/ϵˉ(8RG_R/\bar\epsilon)^{8dRG_R/\bar\epsilon}. Quantum minimum finding over a uniform grid of mesh ϵˉ/(2GRd)\bar\epsilon/(2G_R\sqrt d) uses about (4d RGR/ϵˉ)d/2(4\sqrt d\,RG_R/\bar\epsilon)^{d/2} queries to OfO_f and no gradients. Unless dimension is astronomically huge, the bound of Theorem 13 is even larger than the cost of classical exhaustive search over that grid.

  • Similarly Lemma 19 loses a factor 10−3d10^{-3d} for the nearest-neighbour walk on a discretized ball, whose true gap is polynomial in h/Rh/R and dd and Lemma 18 compares with single-step moves only and loses a factor (h/4σθ)d(h/4\sigma_\theta)^d which is a very big loss.

  • Digitization is analyzed for the stationary distribution (Lemma 4) and for the implementation (Proposition 9), but the gap of the digitized chain is never related to the gap of continuous MALA (analyzed independently). The comparison in Lemma 18 does not use the drift, so it applies equally to a gradient-free random-walk Metropolis chain, and the resulting bound is exponentially small even for f(x)=∥x∥2/2f(x)=\|x\|^2/2. Remark 17 notes that truncating the noise can reduce the gap further. Mixing guarantees known for continuous MALA, for example in the log-concave case, therefore do not carry over to the digital algorithm. That transfer is what would make the end-to-end construction useful.

  • A rigorous digitization of a continuous-space quantum walk, including a conductance bound for the digitized chain, already appears in Chakrabarti et al. (2023) for hit-and-run walks; that work is not cited.

Overall, I think the authors pressed on an important problem yet their bounds do not achieve results that could have been achieved via simpler routes. I am not even sure such sufficient machinery exists yet to do this properly. Instead, as Ozgul et al. (2024) do for the unadjusted chain, digitization can be treated as a per-step perturbation of continuous MALA. Their bounds control the walk operator by the distance between transition rows. A lattice much finer than the proposal width then costs only logarithmically many extra bits and keeps the gap of the continuous chain. Comparing the two chains on one space and handling MALA's rejection step need care, but neither is a real obstacle.

Similar problems also are encountered in classical algorithms. For example, nobody knows how to analyze the gap of discrete version ULA (either time discretization or space). A nontrivial bound would probably allow analyzing SGD from this lens as well but unfortunately similar perturbation type bounds are too loose. Therefore, digitization.discretization are typically treated as errors/perturbations as a feasible route.

Questions for authors
  1. How does Theorem 13 compare quantum minimum finding, and with classical grid search, over the same grid? In which parameter regime, if any, does the proposed algorithm have the better guarantee? Am I missing something in the gap estimate above?
  2. Can the 10−3d10^{-3d} loss in Lemma 19 and the (h/4σθ)d(h/4\sigma_\theta)^d loss in Lemma 18 be removed, for example with known polynomial bounds for grid walks in convex bodies?
  3. Under which natural assumptions on ff does the framework give polynomial complexity? Poincaré or log-Sobolev inequalities for the intermediate Gibbs laws are natural candidates. How would it then compare with Childs et al. (2022) and Ozgul et al. (2024)?
  4. When hh is small compared with σθ\sigma_\theta, can the gap or conductance of the digitized chain be bounded below by a constant times that of continuous MALA? Classical grid walks were analyzed through isoperimetry of the target distribution (Dyer, Frieze & Kannan, 1991; Applegate & Kannan, 1991). Such a transfer would let existing mixing results carry over to digital algorithm. Alternatively, why not treat digitization as a perturbation of continuous MALA, as Ozgul et al. (2024) treat the unadjusted chain?

I am happy to increase my score if the authors present a convincing case how their gap estimate is useful. Currently it seems to me it produces results that are even worse than brute force search over a grid I mentioned above, so I give a tentative clear reject score.

8 comments
AuthorsOpenReview ↗

Critical Weaknesses Rebuttal

Q1: The digitized chain can have a poor gap even when the continuous chain has a good gap, and the explicit bound appears loose beyond the difficulty of the objective landscape.

A: We thank the reviewer for highlighting these two issues. We address both concerns with two new comparison results. First, a same-target Metropolis comparison removes the (h/σθ)d(h/\sigma_\theta)^d loss at an admissible step size and improves the oscillation factor from e−2βD^Re^{-2\beta\widehat D_R} to e−βD^Re^{-\beta\widehat D_R}. Second, under explicit conditions on the grid spacing, proposal cutoff, and gradient precision, we prove δθ≥Gap(Kθc)/6\delta_\theta \ge \mathrm{Gap}(K_\theta^c)/6 for the specified continuous MALA reference chain. The first result sharpens the explicit certificate, and the second transfers a continuous MALA gap under a finer-mesh condition. They apply in different step-size regimes and are not combined. Neither adds assumptions on ff. Details are given in our responses to Questions For Authors in Q2 and 4 below.

 

Q2: The factor e−2βD^Re^{-2\beta\widehat D_R} makes the bound in Theorem 13 worse than quantum minimum finding and even classical exhaustive search over a covering grid in the relevant regimes. How is this guarantee useful?

A: On the same grid with N=∣Ωh∣N=\lvert\Omega_h\rvert, quantum minimum finding uses O(N)O(\sqrt N) function queries at fixed success probability. Theorem 13 exploits the instance's mixing properties through the adaptive bound O~((1+βD^R)/δ‾)\widetilde{O}((1+\sqrt{\beta\widehat D_R})/\sqrt{\underline\delta}). Suppressing logarithmic factors, this gives a better guarantee when δ‾≫(1+βD^R)/N\underline\delta\gg(1+\beta\widehat D_R)/N. Our framework connects such mixing guarantees to global optimization on the finite grid actually implemented, with discretization and implementation errors explicitly controlled.

We have strengthened this connection in two ways. First, comparing with the nearest-neighbour Metropolis walk on the same Gibbs target, with ηθ=θh2\eta_\theta=\theta h^2, removes the (h/σθ)d(h/\sigma_\theta)^d factor and replaces e−2βD^Re^{-2\beta\widehat D_R} by e−βD^Re^{-\beta\widehat D_R}, reducing the corresponding query-bound factor from eβD^Re^{\beta\widehat D_R} to eβD^R/2e^{\beta\widehat D_R/2}. Second, our new constant-factor comparison transfers gap estimates from the specified continuous MALA reference chain to the finite-grid chain under explicit discretization conditions. These complementary results sharpen the explicit certificate and allow instance-specific mixing estimates to enter Theorem 13 directly.

Finally, we will add a smooth localized-depression construction yielding classical and quantum query lower bounds of Ω((ck)d/2)\Omega((ck)^{d/2}) and Ω((ck)d/4)\Omega((ck)^{d/4}), respectively, even with gradient access, where k=RGR/εˉk=RG_R/\bar\varepsilon, c>0c>0 is universal, and kk is sufficiently large. This establishes the intrinsic worst-case difficulty of the problem class, complementing the framework's instance-dependent guarantees.

 

Q3: A rigorous digitization of a continuous-space quantum hit-and-run walk, including a conductance bound, already appears in Chakrabarti et al. (2023), but is not cited.

A: We thank the reviewer and will cite Chakrabarti et al. (2023), who rigorously digitize quantum hit-and-run and establish discretization-error and conductance bounds. Their analysis concerns a line-sampling kernel in a convex-body volume-estimation setting, whereas ours concerns a local Gaussian-proposal Metropolis kernel with potentially non-log-concave Gibbs targets. Their conductance bounds therefore do not directly apply to our chain. We will make this distinction explicit and acknowledge their prior digitization results.

AuthorsOpenReview ↗

Questions For Authors Rebuttal

Q1: How does Theorem 13 compare with quantum minimum finding and classical grid search over the same grid? In which parameter regime, if any, does the proposed algorithm have the better guarantee? Is anything missing in the gap estimate above?

A: The key distinction is between the gap-dependent optimization guarantee in Theorem 13 and the explicit worst-case gap certificate in Proposition 12. Theorem 13 accepts any certified uniform gap bound along the annealing path, making its comparison with grid search depend on the mixing properties of the instance.

We summarize the search baselines and relevant sampling methods below.

MethodGoalAssumptionsDigitizationGuarantee
Classical searchGrid minimumFinite gridDirectO(N)O(N)
Quantum minimum findingGrid minimumFinite gridDirectO(N)O(\sqrt N)
Childs et al., Q-MALASamplingSmooth, strong log-concavityContinuous formulationO~(dκ)\widetilde{O}(d\sqrt\kappa)
Ozgul et al., Q-ULASamplingSmoothness, dissipativity; LSIDeferredO~(βd3/2ϵsρcLSI)\widetilde{O}\left(\frac{\beta d^{3/2}}{\epsilon_{\rm s}\rho c_{\rm LSI}}\right)
Chakrabarti et al., hit-and-runVolume estimationConvex bodyRigorousConductance bounds
OursGlobal optimizationSmoothness + weak localizationFully discreteO~(1+βD^Rδ‾)\displaystyle\widetilde{O}\left(\frac{1+\sqrt{\beta\widehat D_R}}{\sqrt{\underline\delta}}\right)

Here N=∣Ωh∣N=\lvert\Omega_h\rvert, κ=L/μ\kappa=L/\mu, ϵs\epsilon_{\rm s} is the sampling TV error, and ρ,cLSI\rho,c_{\rm LSI} are Cheeger and log-Sobolev constants. The search bounds use fixed success probability. Search uses function queries, Q-ULA uses gradient queries, and the Q-MALA and our bounds apply to each oracle. Our guarantee also covers objectives without a normalizable full-space Gibbs law. The parameter δ‾\underline\delta certifies the spectral gaps throughout the queried annealing path. Suppressing logarithmic factors, our query bound is smaller than that of classical exhaustive search when

δ‾≫1+βD^RN2,\displaystyle \underline\delta \gg \frac{1+\beta\widehat D_R}{N^2},

and smaller than that of quantum minimum finding when

δ‾≫1+βD^RN.\displaystyle \underline\delta \gg \frac{1+\beta\widehat D_R}{N}.

For example, consider

f(x)=μ2∥x∥2+a∑i=1dcos⁡(ωxi),0<a≤12βd.\displaystyle f(x)=\frac{\mu}{2}\lVert x\rVert^2+a\sum_{i=1}^d\cos(\omega x_i), \qquad 0<a\le\frac{1}{2\beta d}.

This family can be nonconvex when aω2>μa\omega^2>\mu, while the perturbation has oscillation at most 2ad2ad. Writing g0g_0 for a uniform gap lower bound of the nearest-neighbour Metropolis reference walks for c(x)=μ∥x∥2/2c(x)=\mu\lVert x\rVert^2/2, our bounded-perturbation and chain comparisons give, with ηθ=θh2\eta_\theta=\theta h^2,

δ‾≥e−1Cdg0,Cd=2de−1/4(1+2π)−d.\displaystyle \underline\delta\ge e^{-1}C_d g_0, \qquad C_d=2d e^{-1/4}(1+2\sqrt{\pi})^{-d}.

Thus, whenever

Cdg0≫1+βD^RN,\displaystyle C_d g_0\gg\frac{1+\beta\widehat D_R}{N},

the resulting query guarantee improves on both classical grid search and quantum minimum finding, up to logarithmic factors.

Proposition 12 supplies an explicit certificate under smoothness and weak localization alone. Introduced in our answer below, our new comparison transfers gap estimates from a specified continuous MALA reference chain to the finite-grid chain under explicit discretization conditions, allowing sharper mixing estimates to enter the same optimization guarantee.

AuthorsOpenReview ↗

Questions For Authors Rebuttal

 

Q2: Lemma 19 loses a factor 10−3d10^{-3d} for the nearest-neighbour walk on a discretized ball, while Lemma 18 loses (h/4σθ)d(h/4\sigma_\theta)^d by comparing only single-step moves. Can these losses be removed, for example with known polynomial bounds for grid walks in convex bodies?

A: We thank the reviewer for pointing out these losses.

Lemma 18. We have removed the (h/4σθ)d(h/4\sigma_\theta)^d loss through a revised comparison and step-size choice. The original restriction forced the proposal width to be much larger than the grid spacing, making the probability of an individual nearest-neighbour move very small. By relaxing this algorithmic restriction to allow ηθ=θh2\eta_\theta=\theta h^2, the proposal width becomes proportional to the grid spacing. At this step size the rounded drift vanishes, so the certificate applies to a gradient-free random-walk Metropolis chain. Theorem 13 remains valid for every admissible step size. Comparing with a nearest-neighbour Metropolis walk on the same Gibbs target then removes this scale-dependent loss, although a dimension-dependent comparison factor remains. No additional assumption on ff is required. The revised comparison also improves the oscillation factor from e−2βD^Re^{-2\beta\widehat D_R} to e−βD^Re^{-\beta\widehat D_R}. We appreciate the reviewer’s observation and will incorporate these changes into Lemma 18, Proposition 12, and the resulting complexity bound.

Lemma 19. The 10−3d10^{-3d} factor is specific to the canonical-path certificate in Lemma 19 and remains in that estimate. The cited convex-body mixing results concern different boundary-cell conventions and do not directly supply a spectral-gap bound for our fully contained-cell walk. In our answer to Q4 below, we provide a complementary certificate that does not use Lemma 19.

The revised analysis thus provides two complementary improvements: a) a sharper explicit certificate that removes the scale-dependent loss in Lemma 18 and reduces the query-bound factor from eβD^Re^{\beta\widehat D_R} to eβD^R/2e^{\beta\widehat D_R/2}; b) under the explicit mesh, precision, and cutoff conditions given in Q4, a constant-factor transfer from the specified continuous MALA reference chain that bypasses Lemma 19.

Reviewer_tsNkOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers the problem of developing a quantum algorithm computing an eps global optimal solution for non-convex optimization under a weak localization.

In particular, let f: R^d --> R be a non-convex function. It is assumed that f(.) is L-smooth. Moreover, the authors assume that eps_loc > 0 is given and we are also given R>0 such that f*_R = min{f(x) : ||x||<=R} <= f* + eps_loc, where f* = inf_x f(x) is the global optimal value. The objective is to study the query complexity of returning x' such that ||x'||<=R such that P(f(x') <= f*+eps) >= 1-p_f for any eps > eps_loc. The query complexity model is reasonable, see Childs et al. Below we will use bar{eps}=eps-eps_loc.

The authors emphasize that their results are shown without necessarily imposing any dissipativity assumption. They produce a finite-grid Metropolis-adjusted Langevin chains whose stationary distributions are a discrete distribution proportional to exp(-beta*f(x)). Thus, increasing beta concentrates these distribution on points with small objective values. The chains are implemented to construct quantum walks, which prepare successive Gibbs states along an adaptive annealing schedule.

The authors' analysis accounts for spatial discretization, finite-precision implementation, and sampling errors. They also supply an explicit lower bound on the spectral gaps of the prescribed chains (although it can be exponentially small). The resulting optimization guarantee is also not polynomial in eps even at fixed dimension.

Critical strengths

The paper provides global complexity analysis using the supplied ball which is assumed to contain an approximate global optimizer, without grow conditions. The whole analysis provides an explicit bound in terms of problem primitives (in particular in terms of R, p_f, and eps-eps_loc) of the query complexity required to compute the eps-global optimizer x'.

Critical weaknesses

Unfortunately, although I appreciate the detailed and explicit analysis, the optimization guarantee does not establish a computational advantage. The bound for the query complexity grows like (for fixed dimension) exp(O(log(1/bar{eps})/bar{eps}))), which is clearly worse than what just a simple classical exhaustive search bound guarantees. I don't want to be obtuse and I understand that there may be sampling benefits of the construction, but then why not write a paper that focuses on those parts. I believe that this limitation substantially calls into question if the contribution is sufficiently significant.

Also, as the authors point out, Prop. 9 follows the MALA construction in Childs et al., and the inverse-square-root-spectral gap dependence appears available already through quantum annealing methods; Harrow & Wei also give the principal adaptive-annealing dependence. The finite ball-grid constructions and corresponding spectral-gap estimates (e.g. Lemma 19 & Prop 12) do not seem to help the paper ultimately improve on existing bounds under similar assumptions, and their significance in sampling is not sufficiently established.

Questions for authors
  1. Can the authors identify a regime in which their method yields a better query-complexity guarantee vs classical exhaustive search over a covering grid?
  2. Can the authors provide a comparison under similar assumptions that isolates an improvement in sampling complexity (or regularity requirements, dimension dependence, etc.) on their finite-ball grid constructions?

Math questions 3) How does the uncomputation in Appendix D.6 erase proposal and acceptance registers entangled with the output, particularly when multiple rejected proposals map to the same self-loop? 4) Could the authors justify how the coordinate precision specified in lines 939–944 controls the state-preparation error in Step 1, particularly near the boundary where the conditional radius R_j becomes small?

3 comments
AuthorsOpenReview ↗

Critical Weaknesses Rebuttal

Q1:\textbf{Q1:} The optimization guarantee is worse than classical exhaustive search at fixed dimension, which calls the significance of the contribution into question. If the construction has sampling benefits, why not focus on those?

A:\textbf{A:} We thank the reviewer for the question. We focus on optimization because locating a near-optimal point does not require sampling a full-space Gibbs distribution. Our assumption supplies a bounded region containing an approximately global minimizer, but imposes no growth condition outside that region. The full-space Gibbs distribution may therefore fail to exist, while the optimization problem remains well defined. Sampling from the Gibbs distribution restricted to the supplied region is an intermediate step. Our analysis then connects localization, temperature, discretization, and sampling accuracy to a guarantee for the original optimization problem.

Our contribution is a fully discrete optimization framework under weak localization, with a quantified complexity guarantee. In the responses below, we compare its query complexity with classical grid search and discuss the conditions under which the instance-dependent bound would be smaller.

 

Q2:\textbf{Q2:} Proposition 9 follows Childs et al., the inverse-square-root spectral-gap dependence is already available through quantum annealing, and Harrow--Wei provide the principal adaptive-annealing dependence. What is the significance of the finite-ball grid constructions and gap estimates if they do not improve existing bounds or establish sampling benefits?

A:\textbf{A:} We thank the reviewer. Our framework builds on quantum MALA and annealing techniques developed by Childs et al. and Harrow--Wei. Our contribution is to formulate and analyze the MALA-based optimization procedure directly on a finite grid under weak localization. The ideal finite-grid chain has exactly the discrete Gibbs law as its stationary distribution, and the analysis connects grid approximation, finite-precision implementation, and sampling errors to the final optimization guarantee. The construction also handles the boundary of the supplied ball, including uniform state preparation over admissible cells without computing ball--cell intersection volumes, and a sublevel-volume bound that remains valid when the minimizer lies on the boundary. The explicit gap certificate makes the resulting complexity bound computable.

We will revise the contribution statements and the discussion of Proposition~9 to make these attributions explicit and distinguish our finite-grid construction and error analysis from the sampling and annealing ingredients inherited from prior work.

AuthorsOpenReview ↗

Questions For Authors Rebuttal

Q1: Can the authors identify a regime in which their method yields a better query-complexity guarantee versus classical exhaustive search over a covering grid?

A: For a covering grid of NN points, the adaptive query bound in Theorem 13 improves on classical exhaustive search whenever

δ‾≫1+βD^RN2,\displaystyle \underline{\delta}\gg\frac{1+\beta\widehat D_R}{N^2},

up to logarithmic factors. Here δ‾\underline{\delta} is a uniform spectral-gap lower bound, supplied by our explicit worst-case estimate in Proposition 12 or by a sharper estimate for the instance. The corresponding complexity is

O~(1+βD^Rδ‾)\displaystyle \widetilde{O}\left(\frac{1+\sqrt{\beta\widehat D_R}}{\sqrt{\underline{\delta}}}\right)

queries to each of the function and gradient oracles, compared with O(N)O(N) function queries for exhaustive search.

Theorem 13 accommodates any such gap bound, and Proposition 12 supplies an explicit certificate under smoothness and weak localization alone, while stronger estimates for structured objectives translate directly into improved optimization guarantees.

A structured regime where this comparison applies is f=c+wf=c+w on the supplied ball, with a rapidly mixing reference nearest-neighbour Metropolis lattice walk for cc. Define the oscillation of the perturbation on the grid by

osc⁡Ωh(w):=max⁡x∈Ωhw(x)−min⁡x∈Ωhw(x).\displaystyle \operatorname{osc}_{\Omega_h}(w):=\max_{x\in\Omega_h}w(x)-\min_{x\in\Omega_h}w(x).

This quantity measures the range of perturbation values on the grid. Our nearest-neighbour Metropolis comparison gives

Gap⁡(PM,θ)≥e−θosc⁡Ωh(w)Gap⁡(PM,θ0),0≤θ≤β,\displaystyle \operatorname{Gap}(P_{M,\theta})\ge e^{-\theta\operatorname{osc}_{\Omega_h}(w)}\operatorname{Gap}(P^{0}_{M,\theta}),\qquad 0\le\theta\le\beta,

where PM,θP_{M,\theta} and PM,θ0P^{0}_{M,\theta} are the nearest-neighbour Metropolis walks targeting e−θ(c+w)e^{-\theta(c+w)} and e−θce^{-\theta c}, respectively. Thus, if βosc⁡Ωh(w)=O(1)\beta\operatorname{osc}_{\Omega_h}(w)=O(1), the perturbation reduces the reference gap by at most a constant factor throughout annealing. Combining this stability estimate with our comparison to the implemented MALA chain gives a gap certificate that can be used directly in Theorem 13, linking reference-chain mixing guarantees to the search-comparison criterion above. We will include this criterion and comparison in our revision.

 

Q2: Can the authors provide a comparison under similar assumptions that isolates an improvement in sampling complexity, regularity requirements, dimension dependence, or other aspects of their finite-ball grid constructions?

A: We build on the quantum MALA framework of Childs et al. and the adaptive annealing tools of Harrow and Wei to obtain a fully discrete optimization guarantee under weak localization. The advance lies in the finite-grid construction, its explicit error accounting, and a computable spectral-gap certificate, without requiring dissipativity or functional inequalities.

We summarize the relevant guarantees below, using the quantum MALA sampling results of Childs et al. and Ozgul et al.

MethodGoalAssumptionsImplementationQuery bound
Childs et al. (2022)SamplingSmoothness + strong log-concavityContinuous-space formulationO~(dκ)\widetilde{O}(d\sqrt{\kappa})
Ozgul et al. (2024)SamplingSmoothness + dissipativityContinuous-space formulationO~(βdρcLSI)\displaystyle \widetilde{O}\left(\frac{\beta d}{\rho c_{\mathrm{LSI}}}\right)
Classical grid searchGlobal optimizationsame localized setting as belowFinite enumerationO(N)O(N)
OursGlobal optimizationSmoothness + weak localizationFully discrete; explicit error controlO~(1+βD^Rδ‾)\displaystyle \widetilde{O}\left(\frac{1+\sqrt{\beta\widehat D_R}}{\sqrt{\underline{\delta}}}\right)

Here κ=L/μ\kappa=L/\mu, ρ\rho is the Cheeger constant, cLSIc_{\mathrm{LSI}} is the log-Sobolev constant, and N=∣Ωh∣N=\lvert\Omega_h\rvert. The sampling bounds concern total-variation accuracy; our optimization bound uses the temperature prescribed in Theorem 13 and a certified uniform gap δ‾\underline{\delta}. Grid search uses function queries only, while our bound counts queries to each of the function and gradient oracles. Our framework also covers objectives whose full-space Gibbs distributions do not exist.

The ideal finite-grid kernel P‾θ\overline{P}_{\theta} has stationary law exactly πθ,Rh\pi^{h}_{\theta,R}, and our analysis explicitly accounts for grid approximation, finite-precision implementation, and sampling errors in the final optimization guarantee. Our revised construction handles rejected proposal labels through a symmetric walk encoding and provides explicit precision control for state preparation near the ball boundary.

AuthorsOpenReview ↗

Questions For Authors Rebuttal

Q3: How does the uncomputation in Appendix D.6 erase proposal and acceptance registers entangled with the output, particularly when multiple rejected proposals map to the same self-loop?

A: We handle rejected proposal labels using the controlled-SWAP symmetric encoding of Claudon et al. (2026, Appendix A, Proposition 11), which retains distinct rejected proposals in orthogonal branches. This corrects the uncomputation construction in Appendix D.6 without requiring proposal labels to be erased. Let Tθ(x,y)T_{\theta}(x,y) be the proposal distribution and Aθ(x,y)A_{\theta}(x,y) half the Metropolis acceptance probability for admissible non-self moves, zero otherwise. With the proposal unitary OTO_T, acceptance unitary OAO_A and controlled swap ScS^c we set Uθ=OT†OA†ScOAOTU_{\theta}=O_T^{\dagger}O_A^{\dagger}S^cO_AO_T. With □∣x⟩=∣x,0,0⟩\Box\lvert x\rangle=\lvert x,0,0\rangle one has □†Uθ□=Dθ\Box^{\dagger}U_{\theta}\Box=D_{\theta}, the discriminant of our lazy MALA chain; in particular Dθ(x,x)=∑yTθ(x,y)(1−Aθ(x,y))=P‾θ(x,x)D_{\theta}(x,x)=\sum_y T_{\theta}(x,y)(1-A_{\theta}(x,y))=\overline{P}_{\theta}(x,x). Rejected proposals thus contribute to the self-loop through orthogonal branches without merging or erasing their labels; this covers proposals outside the domain and those with zero reverse-proposal probability. The walk has phase gap Δθ=arccos⁡(1−δθ)=Θ(δθ)\Delta_{\theta}=\arccos(1-\delta_{\theta})=\Theta(\sqrt{\delta_{\theta}}) and each application uses O(1)O(1) function and gradient queries, so the asymptotic query bounds are unchanged. We will update Prop. 9 and its proof accordingly.

 

Q4: Could the authors justify how the coordinate precision specified in lines 939–944 controls the state-preparation error in Step 1, particularly near the boundary where the conditional radius RjR_j becomes small?

A: We provide explicit precision control near the boundary by treating small conditional radii separately. Let hh be the algorithm’s grid spacing and use an aligned auxiliary grid of spacing Δ\Delta, with h/Δh/\Delta a power of two. At each prefix, coordinate probabilities are obtained from the conditional CDF in Step 1, integrated over bins defined by rounding toward zero. If Rj<τR_j < \tau, we set the remaining coordinates to zero.

For Rj≥τR_j\ge\tau, a Riemann-sum estimate gives conditional ℓ1\ell_1 error O(Δd/τ)O(\Delta\sqrt{d}/\tau) relative to the unnormalized discrete density. On paths whose conditional radii remain at least τ\tau, the product of these unnormalized lattice densities telescopes to Δd/Vol⁡(BR)\Delta^d/\operatorname{Vol}(B_R). Combining this comparison with a discrete boundary-shell bound gives total ℓ1\ell_1 error

O(d3/2Δ/τ+dτ2/R2+d3/2Δ/R),\displaystyle O\left(d^{3/2}\Delta/\tau+d\tau^2/R^2+d^{3/2}\Delta/R\right),

including the small-radius branches. Thus, choosing

τ=Θ(Rt/d),Δ≤min⁡{h,Θ(Rt3/d2)}\displaystyle \tau=\Theta(Rt/\sqrt{d}),\qquad \Delta\le\min\{h,\Theta(Rt^3/d^2)\}

gives ℓ1\ell_1 error O(t2)O(t^2), hence O(t)O(t) in state norm. CDF and rotation errors are also budgeted to contribute O(t)O(t) across the O(dp)O(dp) rotation levels, including low-probability nodes.

Every admissible cell contains the same number of auxiliary points, so ideal projection gives ∣Π0⟩\lvert\Pi_0\rangle and an independent uniform offset register, reset by Hadamard gate. Taking t=Θ(ϵst/(1+log⁡(1/ϵst)))t=\Theta(\epsilon_{\mathrm{st}}/(1+\log(1/\epsilon_{\mathrm{st}}))) controls error accumulation through amplification. The largest aligned Δ\Delta satisfying the above bound requires

p=O(1+log⁡(R/h)+log⁡(d/ϵst)),\displaystyle p=O\left(1+\log(R/h)+\log(d/\epsilon_{\mathrm{st}})\right),

preserving the stated scaling and polynomial gate complexity. We will include this argument and state the coherent guarantee ∥U0∣0⟩−∣Π0⟩∣0⟩anc∥≤ϵst\lVert U_0\lvert 0\rangle-\lvert\Pi_0\rangle\lvert 0\rangle_{\mathrm{anc}}\rVert\le\epsilon_{\mathrm{st}}, with the amplification residual included, yielding the corresponding 2ϵst2\epsilon_{\mathrm{st}} reflection bound.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.