On the role of entanglement and statistics in learning

In this work we make progress in understanding the relationship between learning models when given access to entangled measurements, separable measurements and statistical measurements in the quantum statistical query (QSQ) model. To this end we prove the following results 1. For learning Boolean concept classes, we show that the entangled and separable sample complexity are polynomially related.