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!
Ask episode
AI Snips
Chapters
Transcript
Episode notes
ANECDOTE

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.
INSIGHT

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.
INSIGHT

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.
Get the Snipd Podcast app to discover more snips from this episode
Get the app