Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums

Matthew Amy, Lucas Shigeru Stinchcombe

Implementations of Roetteler's shifted bent function algorithm have in recent years been used to test and benchmark both classical simulation algorithms and quantum hardware. These…