2026-08-25T17:34:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27246 2026-08-25T13:18:19Z ddc:004 open_access

Log-Concavity and Tunneling: Quantum Adiabatic Algorithm for Convex Functions (With a Spike) Braida, Arthur Bermot, Elie Apers, Simon Quantum adiabatic computing Convex optimization Quantum tunneling is expected to provide a computational speedup in quantum computing, a phenomenon that Adiabatic Quantum Optimization (AQO) aims to leverage. While some academic proofs of concept have been studied, such as the "Hamming weight with a spike" (HWS) problem, the algorithmic gains of this effect remain underexplored. In this work we extend the analysis underlying HWS to more general potentials. In the first half of the work, we establish (discrete) log-concavity of the ground state as a key structural property in this context. We devise a framework for establishing log-concavity of the ground state for a large family of discrete, 1-dimensional Schrödinger operators. The family includes convex potentials, but also certain potentials with local minima. In the convex case, this provides a discrete version of a continuous result by Brascamp and Lieb [Brascamp and Lieb, 1976]. We demonstrate the utility of our result by establishing new spectral gap bounds, going beyond related results by Jarret and Jordan [Jarret and Jordan, 2014] for convex potentials. In the second half of the work, we use our results on log-concavity to extend the perturbative analysis of HWS by Reichardt [Reichardt, 2004] to the larger family of potentials with log-concave ground state. As a concrete instantiation, we use our result to extend the HWS analysis from a linear potential (which is exactly solvable) to a quadratic potential (which is no longer solvable). Our result strongly suggests the broader applicability of tunneling to convex potentials with spikes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arthur Braida and Elie Bermot and Simon Apers 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.110 urn:nbn:de:0030-drops-272465 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.110 eng https://creativecommons.org/licenses/by/4.0/legalcode