Quantum Advantage from One-Way Functions

Watch a technical conference presentation from TQC 2024 exploring quantum advantage through one-way functions (OWFs). Learn about inefficient-verifier proofs of quantumness (IV-PoQ) constructed from classical bit commitments, featuring a two-phase interactive protocol between verifier and quantum prover. Discover how the existence of one-way functions enables IV-PoQ, and how distributional collision-resistant hash functions allow for constant-round IV-PoQ. Explore auxiliary-input IV-PoQ (AI-IV-PoQ) and their construction from auxiliary-input commitments, demonstrating quantum advantage based on worst-case-hard assumptions. Presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography at OIST, Japan, this talk delves into theoretical aspects of quantum information science and cryptography.