Quantifying the remaining search space in analogue optimisation
Abstract
Benchmarking analogue optimisers requires certifying not only how close a returned energy is to the optimum, but also how many better configurations may remain. Semidefinite relaxations provide rigorous bounds on the ground-state energy and selected observables, yet reveal little about the size of this residual search space. We introduce a deterministic, instance-specific upper bound on the number of binary configurations whose energies improve upon a returned state by a prescribed margin. Combined with a semidefinite energy interval, this yields a complementary certificate of both the magnitude and multiplicity of any possible improvement. To judge an analogue optimiser's native performance, we provide a generalisation of the framework to obtain bounds on the Haar volume of the remaining continuous phase-space. To further characterise the remaining search space, we extend our bounds to resolve regions in configuration space in both the binary and continuous setting. Our approach couples a variational-Chernoff reduction with an elimination bound of the resulting partition function. Comparisons with exact enumeration and independent Haar sampling are consistent with the bounds on small instances. In numerical experiments at N=1000, even the largest family-median bound restricts the potentially improving binary configurations to less than 10−144 of the full configuration space, while the largest upper bound on the corresponding Haar volume is of order 10−499.
Related
- Elimination of René Peschmann's 968 Remaining Hard Fibers for the Perfect Cuboid Problem
- Statistical analysis of the remaining human life expectancy. Mathematical models of the type Gompertz-Makeham and others
- The Remaining K4-Free Case in the Multipartite Clique Problem
- Sharp comparison between the perimeter and its fractional analogue in two dimensions
- Modeling dependent degradation data considering inherent causal relationships for reliability analysis and remaining useful life prediction
BibTeX
@misc{nagerl2026quantifying,
title = {{Quantifying the remaining search space in analogue optimisation}},
author = {Jona Nagerl and Younes Naceur and Natalia G. Berloff},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07968},
eprint = {2611.07968},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07968},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantifying the remaining search space in analogue optimisation
AU - Jona Nagerl
AU - Younes Naceur
AU - Natalia G. Berloff
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07968
UR - https://arxiv.org/abs/2611.07968
AB - Benchmarking analogue optimisers requires certifying not only how close a returned energy is to the optimum, but also how many better configurations may remain. Semidefinite relaxations provide rigorous bounds on the ground-state energy and selected observables, yet reveal little about the size of this residual search space. We introduce a deterministic, instance-specific upper bound on the number of binary configurations whose energies improve upon a returned state by a prescribed margin. Combined with a semidefinite energy interval, this yields a complementary certificate of both the magnitude and multiplicity of any possible improvement. To judge an analogue optimiser's native performance, we provide a generalisation of the framework to obtain bounds on the Haar volume of the remaining continuous phase-space. To further characterise the remaining search space, we extend our bounds to resolve regions in configuration space in both the binary and continuous setting. Our approach couples a variational-Chernoff reduction with an elimination bound of the resulting partition function. Comparisons with exact enumeration and independent Haar sampling are consistent with the bounds on small instances. In numerical experiments at N=1000, even the largest family-median bound restricts the potentially improving binary configurations to less than 10^−144 of the full configuration space, while the largest upper bound on the corresponding Haar volume is of order 10^−499.
ER -