Complexity classes as mathematical axioms. II

DOI10.4171/QT/75MaRDI QIDQ259630zbMATH OpenFDO

Authors Zhenghan Wang, Shawn X. Cui, Michael Freedman

Publication date 17 March 2016

Published in Quantum Topology (Search for Journal in Brave)

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

zbMATH Keywords

complexity separation conjectureJones polynomialknot theorylink diagramquantum complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: The second author previously discussed how classical complexity separation conjectures, we call them "axioms", have implications in three manifold topology: polynomial length stings of operations which preserve certain Jones polynomial evaluations cannot produce exponential simplifications of link diagrams. In this paper, we continue this theme, exploring now more subtle separation axioms for quantum complexity classes. Surprisingly, we now find that similar strings are unable to effect even linear simplifications of the diagrams.

Recommendations

• Complexity classes as mathematical axioms
• scientific article; zbMATH DE number 3885883
• Logical and schematic characterization of complexity classes
• Dimension and the structure of complexity classes
• The recursion-theoretic structure of complexity classes
• scientific article; zbMATH DE number 4075030
• Qualitative relativizations of complexity classes
• Complexity classes defined by counting quantifiers
• scientific article; zbMATH DE number 4011940
• A uniform approach to define complexity classes

Cites work

• scientific article; zbMATH DE number 5573021 (Why is no real title available?)
• A modular functor which is universal for quantum computation
• A polynomial quantum algorithm for approximating the Jones polynomial
• Congruence and quantum invariants of 3-manifolds
• Congruence subgroups and generalized Frobenius-Schur indicators
• Estimating Jones polynomials is a complete problem for one clean qubit
• Fox's congruence classes and the quantum-\(SU(2)\) invariants of links in 3-manifolds
• How hard is it to approximate the Jones polynomial?
• Invariants of 3-manifolds via link polynomials and quantum groups
• Representation of links by braids: A new algorithm
• Simulation of topological field theories by quantum computers
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• Topological quantum computation

Cited in

(4)

• Complexity classes as mathematical axioms
• scientific article; zbMATH DE number 5772857 (Why is no real title available?)
• Mathematics of topological quantum computing
• Topological quantum computation is hyperbolic

This page was built for publication: Complexity classes as mathematical axioms. II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q259630)