How to hack reality with quantum computers (if complexity theory lets you)

You’ve heard of cryptography. Perhaps quantum cryptography too. Maybe even post-quantum cryptography. But what about *quantum post-quantum cryptography*?! When this came up in conversation with Oxford computer scientist Matthew Gray recently, I’d never heard of it. I wanted to know more, so I invited him for a podcast. Turns out, there’s a whole world of layers to unravel linking quantum and cryptography — or even multiple worlds… In this discussion, we dip into those, and how this all relates to “metacomplexity” problems: the hardness of figuring out the hardness of a problem. This episode will change how you think about quantum computing and cryptography, pushing both to their limits through the lens of fundamental assumptions about computation, quantum physics and reality. *Background* 00:00 Coming Up 01:35 Intro 02:07 Matthew's journey into quantum 07:40 Quantum computers breaking RSA 11:59 Proving secure cryptography 17:07 Post-quantum cryptography 23:24 Breaking crypto means solving new math *The five worlds of complexity vs crypto* 26:22 A world with no crypto 29:22 Metacomplexity problems 32:24 (Meta) complexity theory intro 41:14 Worst case vs average difficulty 45:15 Quantum post-quantum crypto 54:20 Quantum cryptography 1:05:37 Quantum post-quantum crypto vs quantum crypto *The practicalities of quantum post-quantum crypto* 1:09:47 Hardware for quantum post-quantum crypto 1:12:56 Is "learning with errors" secure? *Current research & future* 1:18:58 How is the field evolving? 1:23:07 Matthew's research 1:28:36 Could post-quantum physics affect crypto? 1:34:34 Should we switch to post-quantum crypto? 1:45:22 Recap 1:49:00 Wrap up & final words 1:51:13 Behind the Scenes *If you enjoyed this...* ...like, subscribe, comment & share with your friends! If you'd like to support my content, you can *buy me a coffee* here: https://buymeacoffee.com/mariaviolaris. For larger donations, support via my Fellow profile on the Conjecture Institute website: Profile link - https://www.conjectureinstitute.org/#maria-violaris Donation link - https://www.every.org/conjecture-institute-inc?designation=Maria+Violaris&utm_campaign=donate-link#/donate/card All support much appreciated & will help keep my content going and push it to new levels. *Podcast Background* I'm Maria, I'm a quantum physicist and science communicator. I recently completed my DPhil in the foundations of quantum information at Oxford, and I now work on quantum computing at Oxford Quantum Circuits. I enjoy day-to-day conversations that change my perspective on what our best theories tell us about reality. This podcast aims to share these conversations and up-to-date research insights more widely. ____________________ *Matthew Gray's online profiles* - Personal website: https://www.graytmatter.com/ - LinkedIn: https://www.linkedin.com/in/graytmatter/ - Google Scholar: https://scholar.google.com/citations?user=MO847GEAAAAJ&hl=en *Maria Violaris' online profiles* - Personal website: https://www.mariaviolaris.com - Twitter / X: https://twitter.com/maria__violaris - Bluesky: https://app.bsky.cz/profile/mariaviolaris.bsky.social - LinkedIn: https://www.linkedin.com/in/maria-violaris/ - Instagram: @maria.violaris - Substack: https://mariaviolaris.substack.com - Google Scholar: https://scholar.google.com/citations?user=wD2Yk8kAAAAJ&hl=en&oi=sra