  We present a new optimization method for small-to-intermediate scale
variational algorithms on noisy near-term quantum processors which uses a
Gaussian process surrogate model equipped with a classically-evaluated quantum
kernel. Variational algorithms are typically optimized using gradient-based
approaches however these are difficult to implement on current noisy devices,
requiring large numbers of objective function evaluations. Our scheme shifts
this computational burden onto the classical optimizer component of these
hybrid algorithms, greatly reducing the number of queries to the quantum
processor. We focus on the variational quantum eigensolver (VQE) algorithm and
demonstrate numerically that such surrogate models are particularly well suited
to the algorithm's objective function. Next, we apply these models to both
noiseless and noisy VQE simulations and show that they exhibit better
performance than widely-used classical kernels in terms of final accuracy and
convergence speed. Compared to the typically-used stochastic gradient-descent
approach for VQAs, our quantum kernel-based approach is found to consistently
achieve significantly higher accuracy while requiring less than an order of
magnitude fewer quantum circuit evaluations. We analyse the performance of the
quantum kernel-based models in terms of the kernels' induced feature spaces and
explicitly construct their feature maps. Finally, we describe a scheme for
approximating the best-performing quantum kernel using a classically-efficient
tensor network representation of its input state and so provide a pathway for
scaling these methods to larger systems.
