Post by Maria Violaris, DPhil

Change the way you think about quantum computing, cryptography & the limits of mathematics, in 110 minutes. Earlier this year I was chatting with Oxford computer scientist Matthew Gray over lunch before a seminar, and he mentioned that he's working on "quantum post-quantum cryptography". I'd never heard of this field before. Turns out it's an unusual mix of (meta)complexity theory, quantum computing and cryptography, where researchers imagine worlds in which different complexity-theoretic assumptions hold, leading to different kinds of cryptography and mathematics being possible. Interestingly, you can use quantum computers for cryptography that's secure against attacks from quantum computers, assuming certain properties of complexity theory that we believe to hold. But what if it turns out that no cryptography is possible at all? Such a world might sound bleak, but it's actually very exciting — it means you can do lots of great maths and machine learning! In this episode of the Quantum Foundations Podcast, Matthew explains the rapid recent progress and interesting implications of work in this field, as well as a broader outlook on how complexity theory, computation, cryptography and fundamental laws of physics are intertwined. Some things we cover: - The threat to security from quantum computers - Post-quantum cryptography & quantum cryptography - Encryption using quantum computers - Metacomplexity (the hardness of figuring out the hardness of a problem) & connections to quantum computing - Worlds with different levels of cryptography - Links between physics & computability - Quantum computers as a novel form of cognition Watch on YouTube: https://lnkd.in/ebXztgYy Spotify: https://lnkd.in/e9q8uKwc Apple Podcasts: https://lnkd.in/eMstNiRg