Ziyi Guan - Succinctness Requires Probabilistic Checking in the Quantum World

Succinctness Requires Probabilistic Checking in the Quantum World

Ce séminaire, donné par Ziyi Guan, aura lieu le 08 June 2026, à 12:0. Il aura lieu en salle 26-00/428.

Vous trouverez un plan du campus ici.

Résumé

Succinct arguments are cryptographic proofs with small communication complexity (and sometimes small verifier size). Quantum succinct arguments extend this notion by allowing the prover and verifier to be quantum algorithms that exchange quantum messages. In this talk I will discuss our result showing that quantum succinct arguments in the random oracle model (ROM) is as hard as constructing quantum interactive oracle proofs (QIOPs). The proof gives an efficient transformation from quantum succinct arguments to QIOPs, showing that quantum succinctness implies quantum probabilistic checking. Along the way, we introduce a new proximity test for compressed oracles and adapt locality properties of perfect hash functions to the quantum setting.