  Kernelized bandits, also known as Bayesian optimization (BO), has been a
prevalent method for optimizing complicated black-box reward functions. Various
BO algorithms have been theoretically shown to enjoy upper bounds on their
cumulative regret which are sub-linear in the number T of iterations, and a
regret lower bound of Omega(sqrt(T)) has been derived which represents the
unavoidable regrets for any classical BO algorithm. Recent works on quantum
bandits have shown that with the aid of quantum computing, it is possible to
achieve tighter regret upper bounds better than their corresponding classical
lower bounds. However, these works are restricted to either multi-armed or
linear bandits, and are hence not able to solve sophisticated real-world
problems with non-linear reward functions. To this end, we introduce the
quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. To the
best of our knowledge, our Q-GP-UCB is the first BO algorithm able to achieve a
regret upper bound of O(polylog T), which is significantly smaller than its
regret lower bound of Omega(sqrt(T)) in the classical setting. Moreover, thanks
to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear
kernel achieves a smaller regret than the quantum linear UCB algorithm from the
previous work. We use simulations, as well as an experiment using a real
quantum computer, to verify that the theoretical quantum speedup achieved by
our Q-GP-UCB is also potentially relevant in practice.
