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

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 circuits have many favorable properties, including a tunable amount of non-Clifford resources and a deterministic output, and moreover do not belong to any class of quantum circuits that is known to be efficiently simulable. We show that this family of circuits can in fact be simulated in polynomial time via symbolic path integrals. We do so by endowing symbolic sums with a confluent rewriting system and show that this rewriting system suffices to reduce the circuit’s path integral to the hidden shift in polynomial time. We hence resolve an open conjecture about the efficient simulability of this class of circuits.