A promiseBQP-complete string rewriting problem

zbMATH Open1234.81056arXiv0705.1180MaRDI QIDQ3172430FDOQ3172430

Dominik Janzing, Pawel Wocjan

Publication date: 5 October 2011

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

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

zbMATH Keywords

promiseBQPpromiseBQP-complete problems

Mathematics Subject Classification ID

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

Cited In (1)

• Complexity classes of equivalence problems revisited

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)