Quantum Algorithm for Path-Edge Sampling
Squid: Schools for Quantum Information Development via YouTube
Overview
Watch a 24-minute conference talk from TQC 2023 (Theory of Quantum Computation, Communication and Cryptography Conference) where Shelby Kimmel presents a quantum algorithm for sampling edges on paths between nodes in a graph. Learn about a novel approach that achieves query complexity matching path detection, with applications to pathfinding and cut-finding problems. Explore the technical details of generating quantum states proportional to span program positive witness vectors. Follow along as the presentation covers path detection fundamentals, edge sampling techniques, bottleneck identification in graphs, complete path discovery methods, implementation details, and concludes with open research questions. Delivered at the University of Aveiro as part of the 18th annual TQC conference, which brings together theoretical quantum information science researchers to share cutting-edge advances in the field.
Syllabus
Introduction
Motivation
Path Detection and Pathfinding
Problem Setup
PathEdge Sampling
Finding bottlenecks and graphs
Finding the whole path
Under the hood
Open questions
Conclusion
Runtime Circuit Depth
Question
Taught by
Squid: Schools for Quantum Information Development