  As more practical and scalable quantum computers emerge, much attention has
been focused on realizing quantum supremacy in machine learning. Existing
quantum ML methods either (1) embed a classical model into a target Hamiltonian
to enable quantum optimization or (2) represent a quantum model using
variational quantum circuits and apply classical gradient-based optimization.
The former method leverages the power of quantum optimization but only supports
simple ML models, while the latter provides flexibility in model design but
relies on gradient calculation, resulting in barren plateau (i.e., gradient
vanishing) and frequent classical-quantum interactions. To address the
limitations of existing quantum ML methods, we introduce Quark, a gradient-free
quantum learning framework that optimizes quantum ML models using quantum
optimization. Quark does not rely on gradient computation and therefore avoids
barren plateau and frequent classical-quantum interactions. In addition, Quark
can support more general ML models than prior quantum ML methods and achieves a
dataset-size-independent optimization complexity. Theoretically, we prove that
Quark can outperform classical gradient-based methods by reducing model query
complexity for highly non-convex problems; empirically, evaluations on the Edge
Detection and Tiny-MNIST tasks show that Quark can support complex ML models
and significantly reduce the number of measurements needed for discovering
near-optimal weights for these tasks.
