
Quantum Foundations Podcast Quantum, cryptography & metacomplexity with Oxford Computer Scientist Matthew Gray
17 snips
Dec 10, 2025 In this discussion, Matthew Gray, an Oxford Computer Science PhD student, explores the intriguing intersection of quantum computing and cryptography. He unpacks quantum post-quantum cryptography, revealing how layers of complexity can be navigated. The conversation delves into the dangers posed by quantum adversaries to classical systems and highlights innovative crypto proposals like isogeny-based schemes. Matthew also discusses fundamental concepts of metacomplexity and what potential new physics might imply for computing and security. Prepare for a mind-bending journey!
AI Snips
Chapters
Transcript
Episode notes
Talk Amid LWE Break Claim
- Matthew recalled giving a talk just after a paper claimed to break Learning With Errors (LWE) but before the mistake was found.
- That timing made his 'assuming LWE is secure' talk feel unusually precarious.
Quantum Doesn’t Beat Uncomputability
- Quantum computers cannot solve uncomputable problems like the halting problem.
- They provide speedups but do not overcome fundamental limits set by computability theory.
Quantum Meta‑Complexity Would Undo Classical Crypto
- If quantum machines could solve meta-complexity, they would break all classical crypto.
- That would make classical post-quantum schemes ineffective unless communicants also use quantum resources.
