Quantum circuits and low-degree polynomials over F₂
From MaRDI portal
Publication:2969880
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 5320307 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1335894 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- A polynomial quantum algorithm for approximating the Jones polynomial
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A simple PromiseBQP-complete matrix problem
- Both Toffoli and Controlled-NOT need little help to universal quantum computing
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
- Computational Complexity
- Concentration of measure for the analysis of randomized algorithms.
- Dimer problem in statistical mechanics-an exact result
- Efficient algorithms for some special cases of the polynomial equivalence problem
- Holographic Algorithms
- How hard is it to approximate the Jones polynomial?
- On the computational complexity of the Jones and Tutte polynomials
- PP is as Hard as the Polynomial-Time Hierarchy
- Polynomial-Time Approximation Algorithms for the Ising Model
- Quantum Complexity Theory
- Quantum computing and quadratically signed weight enumerators
- Reducing the number of variables of a polynomial
- Simulating Quantum Computation by Contracting Tensor Networks
- Statistical Mechanics of Dimers on a Plane Lattice
- Temporally unstructured quantum computation
- The complexity of computing the permanent
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(9)- Towards large-scale functional verification of universal quantum circuits
- On the role of Hadamard gates in quantum circuits
- scientific article; zbMATH DE number 5320307 (Why is no real title available?)
- Generators and relations for the group \(\mathrm{O}_n(\mathbb{Z}[\frac{1}{2}])\)
- Algebraic and logical emulations of quantum circuits
- Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
- Classical simulation of quantum circuits by half Gauss sums
- scientific article; zbMATH DE number 7699974 (Why is no real title available?)
- Designing quantum circuits for decoding binary linear codes
This page was built for publication: Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969880)
