Speaker: John (Can) Bostanci , Columbia University 10:30 am, Monday, Nov. 24, 2025 Computer Science Building, Room 105 Host: Prof. Alex Lombardi, CS “A computational lens on quantum information” Abstract: Quantum information is known to behave in ways completely unlike its classical counterpart. For example, quantum information can be entangled across long distances, and in general cannot be cloned. This discrepancy leads to fundamental differences between quantum and classical provers, cryptographic primitives, and transformations. In this talk I will discuss recent advances in our understanding of the ways that these properties can affect the nature of computation itself. My focus will be on our work giving the first classical oracle separation between QMA and QCMA, providing strong evidence that quantum proofs confer genuine computational advantages over classical ones. The result, surprisingly, identifies the reusability of classical proofs as the reason they must be less useful than quantum proofs. Our proof introduces new ideas in quantum query complexity, including a bosonic compressed oracle framework, which provides a structured way to reason about verifiers that process quantum states. I will also discuss broader themes connecting quantum verification, unclonable cryptography, and the complexity of quantum transformations.