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