The disparate impact of noise on quantum learning algorithms

Quantum algorithms offer remarkable potential, promising to solve several computational problems exponentially faster than their classical counterparts. However, currently available quantum devices face significant limitations, including high levels of noise and limited entanglement capacity. As a result, the practical effectiveness of these devices remains uncertain.

Motivated by this situation, this thesis explores the profound impact of noise on quantum learning algorithms in three key dimensions.

Firstly, it examines the influence of noise on variational quantum algorithms, especially quantum kernel methods. Our results reveal marked disparities between unital and non-unital noise, challenging previous conclusions on these noisy algorithms.

Next, it addresses learning quantum dynamics with noisy binary measurements of the Choi-Jamiolkowski state, using quantum statistical queries. We prove that the Goldreich-Levin algorithm can be implemented in this way, and several unitaries are efficiently learnable in this model.

Finally, the thesis contributes to quantum differential privacy, showing how quantum noise can enhance statistical security. We propose a new definition of neighboring quantum states, capturing the structure of quantum encodings, thereby providing stricter privacy guarantees. Additionally, we establish an equivalence between quantum statistical queries and local quantum differential privacy, with applications to tasks such as asymmetric hypothesis testing.