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

Abstract

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.

29 pages, 2 figures; To appear in Quantum

References in corpus (22)

• Improved Simulation of Stabilizer Circuits
• Benchmarking an 11-qubit quantum computer
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Novel constructions for the fault-tolerant Toffoli gate
• Application-Oriented Performance Benchmarks for Quantum Computing
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Towards Large-scale Functional Verification of Universal Quantum Circuits
• Scalable randomized benchmarking of non-Clifford gates
• A Deductive Verification Framework for Circuit-building Quantum Programs
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Improved upper bounds on the stabilizer rank of magic states
• Fast estimation of outcome probabilities for quantum circuits
• Quantum circuits and low-degree polynomials over F_2
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Superpolynomial speedups based on almost any quantum circuit
• Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes
• New techniques for bounding stabilizer rank
• Speedy Contraction of ZX Diagrams with Triangles via Stabiliser Decompositions
• Symbolic Synthesis of Clifford Circuits and Beyond