Quantum Boosting using Domain-Partitioning Hypotheses
  Boosting is an ensemble learning method that converts a weak learner into a
strong learner in the PAC learning framework. Freund and Schapire gave the
first classical boosting algorithm for binary hypothesis known as AdaBoost, and
this was recently adapted into a quantum boosting algorithm by Arunachalam et
al. Their quantum boosting algorithm (which we refer to as Q-AdaBoost) is
quadratically faster than the classical version in terms of the VC-dimension of
the hypothesis class of the weak learner but polynomially worse in the bias of
the weak learner.
  In this work we design a different quantum boosting algorithm that uses
domain partitioning hypotheses that are significantly more flexible than those
used in prior quantum boosting algorithms in terms of margin calculations. Our
algorithm Q-RealBoost is inspired by the "Real AdaBoost" (aka. RealBoost)
extension to the original AdaBoost algorithm. Further, we show that Q-RealBoost
provides a polynomial speedup over Q-AdaBoost in terms of both the bias of the
weak learner and the time taken by the weak learner to learn the target concept
class.
