Polynomial-time Classical Simulation of Roetteler’s Shifted Bent Function Algo...
summary
Claims a polynomial-time classical simulation of Roetteler’s shifted-bent hidden-shift circuit when implemented via the Bravyi–Gosset construction, by converting the circuit to a sum-over-paths expression and applying a confluent rewrite system of simple HH reductions that always terminates with the hidden shift. The procedure runs in time polynomial in circuit volume (each expression remains polynomial-size because Z controls are bounded, previously M=2 benchmarks produce degree ≤ n+1 bent functions). polynomial-time sum-over-paths
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:04Classical simulation
- 3:10Bent functions
- 5:01Oracle implementations
- 7:09Sum over paths
- 9:17Simple HH rewrite rule
- 12:51Rewrite system confluence
- 16:44Polynomial-time algorithm
- 17:47Open questions
- 18:30Q&A
related talks
33mSpoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
22mClassical Simulation of Quantum Circuits with Partial Interference Effects
30mSymbolic Execution of Hadamard-Toffoli Quantum Circuits
32mA Finite Alternation Result for Reversible Boolean Circuits
01h 05mVerifiable quantum advantage: old and new ideas
51mOn constant T-depth circuits
15mScalable Equivalence Checking and Verification of Shallow Quantum Circuits
29mEfficiently Verifying Quantum Programs with Few T Gates