Separating quantum and classical computing: rigorous proof and practical application

Marshall, S.C. (2025)

Doctoral Thesis

This thesis probes under what conditions quantum computing presents an advantage over classical computing. Its first result is a proof of a stronger set of conditions that separate quantum and classical computing. Other key results focus on quantum machine learning (developing shadow models), circuit cutting (developing machine learning methods to make best use of it, and proving rigorous limitations), and bounded advice classes.

• Quantum computing
• Quantum advantage
• Circuit partitioning
• Quantum machine learning

• All authors: Marshall, S.C.
• Supervisor: Dunjko, V.; Bäck, T.H.W.
• Co-supervisor: Nieuwenburg, E.P.L. van
• Committee: Bonsangue, M.; Plaat, A.; Basold, H.; Jeffery, S.; Kerendis, I.
• Qualification: Doctor (dr.)
• Awarding Institution: Leiden Institute of Advanced Computer Science (LIACS), Faculty of Science, Leiden University
• Date: 2025-05-27