Online Locality Meets Distributed Quantum Computing

Explore a 29-minute conference talk from the 19th Theory of Quantum Computation, Communication and Cryptography Conference (TQC 2024) that investigates the extension of locally checkable labeling problems from classical LOCAL models to various quantum computing frameworks. Discover groundbreaking findings on finitely-dependent processes' advantages over classical LOCAL models, including solutions for regular tree coloring problems. Learn about the limitations of distributed quantum computing models through the introduction of randomized online-LOCAL model, which demonstrates that quantum-LOCAL algorithms, non-signaling distributions, and other advanced approaches ultimately achieve similar complexity bounds as classical deterministic LOCAL models when solving certain problems in trees. Presented by researchers Amirreza Akbari, Xavier Coiteux Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, and Darya Melnyk at OIST, Japan, this talk represents cutting-edge research in theoretical quantum information science, supported by industry leaders including JPMorgan Chase, Google Quantum AI, and Quantinuum.