AI summaryⓘ
The authors studied how a quantum effect called tunneling can help speed up certain quantum algorithms, specifically in a method known as Adiabatic Quantum Optimization (AQO). They focused on understanding the shape of the lowest energy state (ground state) for a broad class of mathematical models called discrete one-dimensional Schrödinger operators and proved these ground states often have a property called log-concavity. Using this property, they improved previous mathematical bounds related to energy gaps, which are important for AQO performance. They then extended earlier work on a specific problem (Hamming weight with a spike) from simple linear models to more complex quadratic ones, suggesting that tunneling may benefit a wider range of problems with convex potentials and spikes.
Quantum tunnelingAdiabatic Quantum OptimizationHamming weight with a spike (HWS)Discrete Schrödinger operatorLog-concavityGround stateSpectral gapConvex potentialPerturbative analysis
Authors
Arthur Braida, Elie Bermot, Simon Apers
Abstract
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 ('76). We demonstrate the utility of our result by establishing new spectral gap bounds, going beyond related results by Jarret and Jordan ('14) 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 ('04) 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