Provable Advantage in Quantum PAC Learning

Watch a 24-minute conference talk from the 19th Theory of Quantum Computation, Communication and Cryptography Conference (TQC 2024) exploring groundbreaking research in quantum PAC learning. Delve into how researchers have discovered a generic quantum advantage in learning algorithms, demonstrating a square root improvement over classical learning sample complexity for any concept class with VC dimension d. Learn about their novel extension to quantum PAC learning definitions that achieves an O(1/√ε[d + log(1/δ)]log⁹(1/ε)) sample complexity, along with proof of its tightness through an Ω(d/√ε) lower bound. Presented by researchers Wilfred Salmon, Sergii Strelchuk, and Tom Gur at OIST Japan, this talk advances the theoretical understanding of quantum information science beyond the constant factor advantages previously established by Arunachalam and de Wolf.