Projected Stochastic Gradient Descent with Quantum Annealed Binary
  Gradients
Maximilian Krahn Michelle Sasdelli Fengyi Yang Vladislav Golyanik Juho Kannala Tat-Jun Chin Tolga Birdal
We present, QP-SBGD, a novel layer-wise stochastic optimiser tailored towards
training neural networks with binary weights, known as binary neural networks
(BNNs), on quantum hardware. BNNs reduce the computational requirements and
energy consumption of deep learning models with minimal loss in accuracy.
However, training them in practice remains to be an open challenge. Most known
BNN-optimisers either rely on projected updates or binarise weights
post-training. Instead, QP-SBGD approximately maps the gradient onto binary
variables, by solving a quadratic constrained binary optimisation. Under
practically reasonable assumptions, we show that this update rule converges
with a rate of $\mathcal{O}(1 / \sqrt{T})$. Moreover, we show how the
$\mathcal{NP}$-hard projection can be effectively executed on an adiabatic
quantum annealer, harnessing recent advancements in quantum computation. We
also introduce a projected version of this update rule and prove that if a
fixed point exists in the binary variable space, the modified updates will
converge to it. Last but not least, our algorithm is implemented layer-wise,
making it suitable to train larger networks on resource-limited quantum
hardware. Through extensive evaluations, we show that QP-SBGD outperforms or is
on par with competitive and well-established baselines such as BinaryConnect,
signSGD and ProxQuant when optimising the Rosenbrock function, training BNNs as
well as binary graph neural networks.