Ziyi Guan - Succinctness Requires Probabilistic Checking in the Quantum World

Succinctness Requires Probabilistic Checking in the Quantum World

This seminar, given by Ziyi Guan, will happend on 08 June 2026, at 12:0. It will take place in Room 26-00/428.

Find a map of the campus here.

Abstract

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.