- 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
Thank you for addressing my questions. The new results resolve my main concerns, and I’ll maintain my positive score.
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.