Quantum Algorithms and the Power of Forgetting - The Welded Tree Problem

Watch a 25-minute conference talk from TQC 2023 (Theory of Quantum Computation, Communication and Cryptography Conference) where Amin Shiraz Gilani explores the welded tree problem and its implications for quantum algorithms. Discover why finding paths between entrance and exit vertices in certain quantum walk problems remains challenging even for quantum computers, despite their ability to solve related problems exponentially faster than classical algorithms. Learn about a groundbreaking proof demonstrating that a natural class of efficient quantum algorithms cannot find these paths, suggesting that quantum computational advantages may sometimes require "forgetting" the path taken to reach a solution. Delve into technical aspects including address trees, classical simulation, and the structure of rooted algorithms while exploring the broader implications for quantum computing theory and algorithm design.