Optimal Algorithms for Learning Quantum Phase States

Watch a conference talk from TQC 2023 exploring optimal algorithms for learning quantum phase states, where Arkopal Dutt presents groundbreaking research on analyzing the complexity of learning n-qubit quantum phase states. Discover the sample complexity analysis for learning degree-d phase states using both separable and entangled measurements, with findings showing Θ(nᵈ) complexity for separable measurements and Θ(nᵈ⁻¹) for entangled measurements. Learn about a novel polynomial-time algorithm using single-qubit Pauli X and Z basis measurements, making it suitable for near-term quantum devices. Explore extensions to complex-valued amplitudes, sparse Boolean polynomials, Fourier-degree bounded functions, and noisy quantum systems, culminating in applications for learning Clifford hierarchy diagonal unitaries and IQP circuits. The presentation covers key topics including graph states, Bell sampling, classical learning approaches, random partial derivative sampling, and pretty good measurements.