Quantum circuits and low-degree polynomials over F₂
From MaRDI portal
Publication:2969880
DOI10.1088/1751-8121/AA565FzbMATH Open1360.81114arXiv1607.08473OpenAlexW2951887194WikidataQ58478259 ScholiaQ58478259MaRDI QIDQ2969880FDOQ2969880
Authors: Ashley Montanaro 
Publication date: 23 March 2017
Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1607.08473
Recommendations
Cites Work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Statistical Mechanics of Dimers on a Plane Lattice
- Title not available (Why is that?)
- Computational Complexity
- Dimer problem in statistical mechanics-an exact result
- The complexity of computing the permanent
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- How hard is it to approximate the Jones polynomial?
- Holographic Algorithms
- Quantum Complexity Theory
- On the computational complexity of the Jones and Tutte polynomials
- Polynomial-Time Approximation Algorithms for the Ising Model
- Reducing the number of variables of a polynomial
- PP is as Hard as the Polynomial-Time Hierarchy
- Simulating Quantum Computation by Contracting Tensor Networks
- A polynomial quantum algorithm for approximating the Jones polynomial
- Quantum computing and quadratically signed weight enumerators
- Concentration of measure for the analysis of randomized algorithms.
- Efficient algorithms for some special cases of the polynomial equivalence problem
- Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- Both Toffoli and Controlled-NOT need little help to universal quantum computing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Temporally unstructured quantum computation
- A simple PromiseBQP-complete matrix problem
Cited In (9)
- Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
- Towards large-scale functional verification of universal quantum circuits
- Title not available (Why is that?)
- Classical simulation of quantum circuits by half Gauss sums
- Algebraic and logical emulations of quantum circuits
- On the role of Hadamard gates in quantum circuits
- Generators and relations for the group \(\mathrm{O}_n(\mathbb{Z}[\frac{1}{2}])\)
- Designing quantum circuits for decoding binary linear codes
- Title not available (Why is that?)
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)
