Quantum circuits and low-degree polynomials over F_2

Abstract

In this work we explore a correspondence between quantum circuits and low-degree polynomials over the finite field F_2. Any quantum circuit made up of Hadamard, Z, controlled-Z and controlled-controlled-Z gates gives rise to a degree-3 polynomial over F_2 such that calculating quantum circuit amplitudes is equivalent to counting zeroes of the corresponding polynomial. We exploit this connection, which is especially clean and simple for this particular gate set, in two directions. First, we give proofs of classical hardness results based on quantum circuit concepts. Second, we find efficient classical simulation algorithms for certain classes of quantum circuits based on efficient algorithms for classes of polynomials.

16 pages, 4 figures

References in corpus (13)

• Improved Simulation of Stabilizer Circuits
• On the Power of One Bit of Quantum Information
• Simulating quantum computation by contracting tensor networks
• Entanglement and the Power of One Qubit
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Trading classical and quantum computational resources
• Average-case complexity versus approximate simulation of commuting quantum computations
• Instantaneous Quantum Computation
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• A Linear-Optical Proof that the Permanent is #P-Hard
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• A simple encoding of a quantum circuit amplitude as a matrix permanent

Cited by in corpus (19)

• Computational advantage of quantum random sampling
• Towards Large-scale Functional Verification of Universal Quantum Circuits
• How many qubits are needed for quantum computational supremacy?
• On the CNOT-complexity of CNOT-PHASE circuits
• Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• Classical simulation of quantum circuits by half Gauss sums
• A Case for Synthesis of Recursive Quantum Unitary Programs
• Explicit lower bounds on strong quantum simulation
• FeynmanDD: Quantum Circuit Analysis with Classical Decision Diagrams
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
• Symbolic Synthesis of Clifford Circuits and Beyond
• Lower T-count with faster algorithms
• Generators and Relations for the Group On(Z[1/2])
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Generalized Boolean Functions and Quantum Circuits on IBM-Q
• On the role of coherence for quantum computational advantage
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums