Polynomial-time Classical Simulation of Roetteler's Shifted Bent Function Algorithm
ACM SIGPLAN via YouTube
Overview
Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.
Syllabus
[PLanQC'24] Polynomial-time Classical Simulation of Roetteler’s Shifted Bent Function Algo...
Taught by
ACM SIGPLAN