A Simple Quantum Sketch With Applications to Graph Algorithms

Explore a quantum sketch for set theory and its applications in graph algorithms in this 57-minute lecture by John Kallaugher from Sandia National Laboratories. Delve into the sketch's ability to determine how many pairs from a partitioned universal set are present in a given subset, and discover its origins in communication complexity. Learn how this quantum technique offers significant advantages in space efficiency for graph problems, including polynomial improvements for triangle counting and exponential gains for Max-Dicut algorithms. Gain insights into the intersection of quantum computing, sketching techniques, and algorithm design for tackling complex graph-related challenges.