  Variational quantum-classical hybrid algorithms are seen as a promising
strategy for solving practical problems on quantum computers in the near term.
While this approach reduces the number of qubits and operations required from
the quantum machine, it places a heavy load on a classical optimizer. While
often under-appreciated, the latter is a computationally hard task due to the
barren plateau phenomenon in parameterized quantum circuits. The absence of
guiding features like gradients renders conventional optimization strategies
ineffective as the number of qubits increases. Here, we introduce the
fast-and-slow algorithm, which uses Bayesian Learning to identify a promising
region in parameter space. This is used to initialize a fast local optimizer to
find the global optimum point efficiently. We illustrate the effectiveness of
this method on the Bars-and-Stripes (BAS) quantum generative model, which has
been studied on several quantum hardware platforms. Our results move
variational quantum algorithms closer to their envisioned applications in
quantum chemistry, combinatorial optimization, and quantum simulation problems.
