Simple Information Processing Tasks with Unbounded Quantum Advantage

In this lecture, Leevi Leppäjärvi from the University of Jyväskylä, Finland, explores simple information processing tasks that demonstrate unbounded quantum advantage. Discover how communication scenarios between two parties reveal significant advantages of quantum systems over classical ones. Learn about a constructed family of operationally meaningful communication tasks that can be implemented with just a single qubit but require unboundedly larger classical systems for implementation. Understand how, even with shared randomness as an additional resource, the number of coordinated actions needed for classical implementation grows unboundedly, making it impossible to store all coordinated actions needed for quantum communication tasks in finite storage. The lecture explains why shared randomness cannot be considered a free resource in this context. This presentation is part of the Quantum Information and Quantum Computing Seminars series at Centrum Fizyki Teoretycznej PAN, delivered on March 5, 2025.