A new sibling of BQP

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We present a new quantum complexity class, called MQ^2, which is contained in AWPP. This class has a compact and simple mathematical definition, involving only polynomial-time computable functions and a unitarity condition. It contains both Deutsch-Jozsa's and Shor's algorithm, while its relation to BQP is unknown. This shows that in the complexity class hierarchy, BQP is not an extraordinary isolated island, but has ''siblings'' which as well can solve prime-factorization.
extended abstract, submitted to UC'05

Keywords

Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/32870

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0507057
 http://arxiv.org/abs/cs/0507057

Collections

arXiv