Quantum learning speed-up in binary classification task

Recent trend in attempt to hybridize the two science fields, machine learning and quantum information, 
is of keen interest. In the line of this research, our main question is: Can ¡°quantum¡± improve machine
 learning? Answering to this question, we consider a specific problem, called ¡°binary classification¡±,
 which is to learn a targeting N-bit Boolean function. To solve this problem, we design two learning
 machines: One is able to use quantum, and the other is not. Our main task is to compare these two
 learning machines. As a fundamental step, we introduce a concept of acceptable region defined as a
 localized region of the parameter space including the approximate solutions. We then show that the
 quantum machine can learn faster, as it can extend the acceptable region assisted with quantum
 superposition. We also argue that such a quantum speedup is enabled by the appropriately arranged
 phases in the quantum machine. To make this analysis more explicit, we analyze further by using a
 primitive learning model, called random search, often used as a standard model for learning
 performance analysis. In the analysis, we validate that the quantum is better. Taking into account a
 realistic circumstance, we also consider more practical learning model, called differential evolution,
 where the quantum speedup is still observed.