A simple PromiseBQP-complete matrix problem

DOI10.4086/TOC.2007.V003A004MaRDI QIDQ3002780zbMATH OpenOpenAlexFDO

Authors Dominik Janzing, Pawel Wocjan

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2007.v003a004

zbMATH Keywords

BQPcompletenesscomplexitynon-quantum characterization of BQPPromiseBQPquantum computation

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A complete characterization of unitary quantum space
• A promiseBQP-complete string rewriting problem
• "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• Complexity of stoquastic frustration-free Hamiltonians
• Hermitian matrix definiteness from quantum phase estimation

Cited in

(6)

• Hermitian matrix definiteness from quantum phase estimation
• Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
• A promiseBQP-complete string rewriting problem
• A complete characterization of unitary quantum space
• The BQP-hardness of approximating the Jones polynomial
• The quantum complexity of computing Schatten p-norms

This page was built for publication: A simple PromiseBQP-complete matrix problem

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