The quantum monad: structuring quantum advantage
summary
Claims that a quantum monad on relational structures exactly captures when quantum resources give an advantage: a quantum perfect strategy for a homomorphism game is bijective with a quantum homomorphism, i.e. a projector-valued relation, and equivalently with a classical homomorphism A → Q_d(B). Construction uses projective measurements, maximally entangled states, and tensor-product composition so dimensions multiply; it yields genuine separations (magic square, quantum graph colorings with fewer colors). Monadic grading tracks qubit count; integrating with game comonads is promising but technically nontrivial.
AI-written summary · about
chapters (10)
- 0:00Quantum advantage and monads
- 2:16Quantum monad explained
- 7:18Quantizing relational structures
- 13:41Non-local games and strategies
- 19:47From games to homomorphisms
- 25:02Graded quantum monad
- 33:35Contextuality and advantage
- 49:03Combining quantum monads
- 53:18Future directions
- 55:22Q&A
related talks
30mGraph Isomorphism Via Non-Local Games
28mA type-theoretic account of quantum computation (Extended Abstract)
01h 20mA Quantum Data Structure For Classical Computers
01h 10mQuantum Advantage with Shallow Clifford Circuits
20mA Quantum Interpretation of Separating Conjunction for Local Reasoning of Quantu
24mQunity: A Unified Language for Quantum and Classical Computing
01h 07mTwo Tensor Optimization Problems From Quantum Information
22mQbC: Quantum Correctness by Construction