Polynomial-time Classical Simulation of Roetteler's Shifted Bent Function Algorithm

Explore a 20-minute conference talk from ACM SIGPLAN that delves into the polynomial-time classical simulation of Roetteler's shifted bent function algorithm. Learn how Lucas Stinchcombe and Matthew Amy demonstrate the algorithm's simulability when implemented using Bravyi and Gosset's construction. Discover the classical simulation procedure based on symbolic rewriting of a circuit's sum-over-paths, and understand how every sequence of rewrites terminates with the hidden shift in polynomial time relative to the circuit's volume. Gain insights into the intersection of quantum algorithms and classical simulation techniques in this concise yet informative presentation.