A promiseBQP-complete string rewriting problem

MaRDI QIDQ3172430zbMATH OpenFDO

Authors Dominik Janzing, Pawel Wocjan

Publication date 5 October 2011

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

zbMATH Keywords

promiseBQPpromiseBQP-complete problems

Mathematics Subject Classification ID

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

Recommendations

• A simple PromiseBQP-complete matrix problem
• Quantum computing and quadratically signed weight enumerators
• Reconstructing strings from substrings with quantum queries
• Promise problems solved by quantum and classical finite automata
• "NON-IDENTITY-CHECK" IS QMA-COMPLETE

Cited in

(2)

• Complexity classes of equivalence problems revisited
• A simple PromiseBQP-complete matrix problem

This page was built for publication: A promiseBQP-complete string rewriting problem

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