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

Researchers have demonstrated a polynomial-time classical simulation for Roetteler’s shifted bent function circuits, previously believed to resist efficient simulation. This breakthrough challenges assumptions about quantum advantage for this widely used benchmarking family. The team achieved this by developing a confluent rewriting system for symbolic sums, enabling reduction of the circuit’s path integral to its hidden shift in polynomial time. This resolves a long-standing open conjecture about the class’s simulability. Shifted bent function circuits were prized for benchmarking due to tunable non-Clifford resources and deterministic outputs, yet belonged to no known efficiently simulable class—until now. Their properties made them ideal testbeds for quantum hardware. The method leverages symbolic path integrals, a mathematical framework that bypasses traditional simulation bottlenecks. This approach could redefine how certain quantum circuits are analyzed classically. The findings, published in December 2025, underscore that even circuits designed to test quantum supremacy may yield to clever classical techniques, reshaping the boundary between quantum and classical computational power.