Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$

DOI10.1088/1751-8121/aa565fzbMath1360.81114arXiv1607.08473OpenAlexW2951887194WikidataQ58478259 ScholiaQ58478259MaRDI QIDQ2969880

Ashley Montanaro

Publication date: 23 March 2017

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.08473

zbMATH Keywords

computational complexityquantum computingquantum circuits

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Unnamed Item, Classical simulation of quantum circuits by half Gauss sums

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Quantum computing and quadratically signed weight enumerators
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A linear-optical proof that the permanent is # P -hard
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Polynomial-Time Approximation Algorithms for the Ising Model
• Statistical Mechanics of Dimers on a Plane Lattice
• PP is as Hard as the Polynomial-Time Hierarchy
• Holographic Algorithms
• Temporally unstructured quantum computation
• Simulating Quantum Computation by Contracting Tensor Networks
• Quantum Complexity Theory
• On the computational complexity of the Jones and Tutte polynomials
• Computational Complexity
• Dimer problem in statistical mechanics-an exact result
• Concentration of Measure for the Analysis of Randomized Algorithms
• A polynomial quantum algorithm for approximating the Jones polynomial