Testing Classical Properties from Quantum Data

Explore quantum algorithms for testing Boolean function properties using quantum data in this conference talk from QTML 2025. Learn how quantum approaches can recover computational speedups that are lost when classical property testers are restricted to random samples rather than adaptive queries. Discover new quantum testing algorithms for three fundamental properties: monotonicity, symmetry, and triangle-freeness, which demonstrate quantum advantages over classical sample-based methods. Examine why techniques beyond quantum Fourier sampling are necessary, including proof that constant-complexity symmetry testing cannot rely solely on Fourier sampling and random classical samples. Understand the fundamental relationship between classical queries and quantum data through examples showing maximal incomparability between these resources, including problems solvable with O(1) classical queries but requiring Ω(2^{n/2}) quantum function state copies. Investigate the challenges of establishing lower bounds for quantum data testing, particularly how classical exponential lower bound techniques fail to provide meaningful bounds in the quantum setting, highlighting the need for new quantum-specific analytical approaches.