Cojocaru, Alexandru

Lewis, Laura

Marshall Scholarship

Forum on Graduate Student Affairs (FGSA): Graduate Research Excellence Award

Diversity in Quantum Travel Grant

2025-10-16T15:08:30Z

2025-10-16T15:08:30Z

2025-10-08

Quantum learning theory is a burgeoning field at the intersection of quantum information and machine learning theory. However, current research for learning quantum objects typically focuses on efficiency with respect to sample complexity, rather than computational complexity. In this thesis, we study classes of quantum processes and classical functions for which computationally efficient quantum learning is achievable. On the other hand, it is known that there exist classes of quantum states that are provably hard to learn in polynomial time, under standard cryptographic assumptions. We consider the converse: can we design useful cryptography from a given class of quantum states that is hard to learn efficiently? We answer this question affirmatively by constructing fundamental cryptographic primitives from the computational hardness of learning. This reflects the deep connection between learning and cryptography in the classical world, which has been widely unexplored in the quantum setting. First, as an example of a computationally efficient quantum learning algorithm, we prove a rigorous quantum advantage against classical gradient methods for learning periodic neurons. Next, we develop a more general formalism, called agnostic process tomography, for approximating an unknown quantum channel by a simpler one in a given class. In this setting, we prove that the correct measure of efficiency is computational complexity and design efficient quantum algorithms for learning a wide variety of processes. Finally, having understood when quantum algorithms can learn efficiently, we study the hardness of learning classes of quantum states and its applications to cryptography.

https://hdl.handle.net/1842/44070

http://dx.doi.org/10.7488/era/6596

en

The University of Edinburgh

Daiwei Zhu, Gregory D Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, et al. Interactive protocols for classically-verifiable quantum advantage. arXiv preprint arXiv:2112.05156, 2021

Laura Lewis, Daiwei Zhu, Alexandru Gheorghiu, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, et al. Experimental implementation of an efficient test of quantumness. Physical Review A, 109(1):012610, 2024

Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C Caro. Learning quantum states and unitaries of bounded gate complexity. PRX Quantum, 5(4):040306, 2024

Laura Lewis, Hsin-Yuan Huang, Viet T Tran, Sebastian Lehner, Richard Kueng, and John Preskill. Improved machine learning algorithm for predicting ground state properties. nature communications, 15(1):895, 2024

Marc Wanner, Laura Lewis, Chiranjib Bhattacharyya, Devdatt Dubhashi, and Alexandru Gheorghiu. Predicting ground state properties: Constant sample complexity and deep learning algorithms. Advances in Neural Information Processing Systems, 37:33962–34024, 2025

Marc Wanner, Laura Lewis, Chiranjib Bhattacharyya, Devdatt Dubhashi, and Alexandru Gheorghiu. Predicting ground state properties: Constant sample complexity and deep learning algorithms. arXiv preprint arXiv:2405.18489, 2024

Viet T Tran, Laura Lewis, Hsin-Yuan Huang, Johannes Kofler, Richard Kueng, Sepp Hochreiter, and Sebastian Lehner. Using shadows to learn ground state properties of quantum hamiltonians. Machine Learning and Physical Sciences Workshop at the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022

Laura Lewis, Dar Gilboa, and Jarrod R McClean. Quantum advantage for learning shallow neural networks with natural data distributions. arXiv preprint arXiv:2503.20879, 2025

Jerry Huang, Laura Lewis, Hsin-Yuan Huang, and John Preskill. Predicting adaptively chosen observables in quantum systems. arXiv preprint arXiv:2410.15501, 2024

Quantum learning theory

Computational complexity

Quantum states

Cryptography

Quantum algorithms

Computational complexity in quantum learning tasks

Thesis or Dissertation

Masters

MSc(R) Master of Science by Research