New Approaches to Complexity via Quantum Graphs

Explore a conference talk from TQC 2024 that delves into novel approaches for studying complexity through quantum graphs. Learn how researchers tackle the challenges of defining decision problems for quantum graphs - an operator system generalization of classical graphs - by establishing connections between quantum graphs and quantum channels. Discover how the clique problem for quantum graphs is formulated using quantum channels induced by circuits, leading to significant complexity theory findings. Understand how this research demonstrates that quantifying over all channels makes the problem QMA(2)-complete, while specific restrictions to entanglement-breaking channels, deterministic channels, or classical noisy channels correspond to QMA, NP, and MA completeness respectively. Follow the innovative self-testing inspired methods used to prove QMA(2)-completeness and grasp the new proof for reducing QMA(k) to QMA(2). Examine the parallel investigation of the independent set problem for quantum graphs and its potentially different complexity implications compared to classical cases. Presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography at OIST, Japan, this 24-minute presentation bridges fundamental concepts in classical complexity with quantum information theory.