  Preparing the ground state of a Hamiltonian is a problem of great
significance in physics with deep implications in the field of combinatorial
optimization. The adiabatic algorithm is known to return the ground state for
sufficiently long preparation times which depend on the a priori unknown
spectral gap. Our work relates in a twofold way. First, we propose a method to
obtain information about the spectral profile of the adiabatic evolution.
Second, we present the concept of a variational quantum adiabatic algorithm
(VQAA) for optimized adiabatic paths. We aim at combining the strengths of the
adiabatic and the variational approaches for fast and high-fidelity ground
state preparation while keeping the number of measurements as low as possible.
Our algorithms build upon ancilla protocols which we present that allow to
directly evaluate the ground state overlap. We benchmark for a non-integrable
spin-1/2 transverse and longitudinal Ising chain with $N=53$ sites using tensor
network techniques. Using a black box, gradient-based approach, we report a
reduction in the total evolution time for a given desired ground state overlap
by a factor of ten, which makes our method suitable for the limited decoherence
time of noisy-intermediate scale quantum devices.
