Graph Isomorphism Via Non-Local Games
summary
Defines quantum isomorphism by an N by N block matrix whose blocks are orthogonal projectors satisfying (A_G ⊗ I_d) P = P (A_H ⊗ I_d) and shows a perfect quantum strategy for the GH isomorphism game exists iff such a P exists. Proves classical perfect strategies coincide with ordinary isomorphism and non‑signaling perfect strategies coincide with fractional isomorphism, so isomorphism ⇒ quantum isomorphism ⇒ fractional isomorphism with both implications strict. Builds nonisomorphic but quantum‑isomorphic pairs from BCS to graph construction using quantum satisfiable but classically unsatisfiable linear binary constraint systems.
AI-written summary · about
chapters (10)
- 0:00Introduction and overview
- 1:27Graph isomorphism basics
- 3:22Defining quantum isomorphism
- 6:00Non-local game frameworks
- 9:41The isomorphism game
- 12:11Classical strategy proof
- 16:00Quantum and non-signaling
- 19:41Hierarchy of relations
- 22:20Separating the concepts
- 27:53Conclusion and Q&A
related talks
01h 02mThe quantum monad: structuring quantum advantage
01h 10mQuantum Advantage with Shallow Clifford Circuits
48mGames to Establish Structure in an Unknown Hilbert Space
48mThe Quantum Games PCP: Results and Confessions
39mDelegated Quantum Computation from Sequential Games
22mTopological Quantum Programming in TED-K
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
44mQuantum Complexity of Clique Homology